Question:
Though I’ve been programming in C/C++ for several years now, I’ve never understood how to build a queue or stack. I used to resort to some of the included libraries in Borland C++. But things have changed… I’m going to be moving over to a new O/S, and I want to build a template or class that for both queues and stacks so that I can both learn how they work as well as become overly dependant on the classes. :-)Any ideas would be greatly appreciated.Thank you,Raymond
Answer:
Queues and stacks are both implemented quite easily in C/C++. The are particularly well suited to C++, which allows you to encapsulate the implementation behind a simple interface.
I won’t write them for you, there are plenty of books around that will do that, but try to give you some ideas to get started. First, both classes could store the data in a simple array. You’ll need to allocate memory from your array, perhaps using malloc, realloc, etc. so that you can resize the array as needed.
In the case of a stack, when an item is “pushed,” expand the array by one and add the pushed item to the end of the array. When it gets “popped,” return the last item and shorten the array by one.
In the case of a queue, the size of the array will probably be fixed. You’ll need two indexes to signify the head and tail of the data. Upon initialization, both indexes will be equal. When an item is added to the queue, put it where the tail points, and increment the tail. When an item is read from the queue, return the value where the head points and increment the head. Be sure to test for the end of the array when incrementing pointers. When a pointer is incremented past the end of the array, just set it to the beginning of the array.
