Stacks, Queue and Lists

A stack is a Last-In-First-Out (LIFO) list, a queue is a First-In-First-Out (FIFO) list, and a list is an Any-In-Any-Out list meaning elements can added to the beginning, middle or end of a list and elements can be removed from the beginning, middle or end of the list.  Stacks inside the computer are essentially implemented as an array with an index pointing to the top of the stack, growing as large as needed given available memory.  To implement this in a higher level language like C++, this type of implementation would need a fixed size of memory allocated.  Changing the size during run time, while not impossible, is not practical or efficiently.

A better way to implement a stack in C++ is as a linked list, because memory does not need to be allocated ahead of time for the stack whose size is not yet known.  To add a new element to the top of the stack, a single element is allocated from the free memory heap, then linked into the current list.  To remove the element from the top of the stack, it is simply de-linked from the stack and the item is deallocated back to the free memory heap.  This method requires an overhead of a link with each item (that points to the next item on the stack) and the stack would contain a pointer to the top element (or a NULL pointer if the stack is empty).

However, as will be explained, there will be occasions where it will be necessary to read a stack from the bottom to the top.  And there will be occasions where it will be necessary to pop an item from the middle and remove it.

Using the single link method, a stack cannot be read from the bottom to the top or read and removed items from the middle.  In order to support this, a double link method will be needed, which is required for an AIAO list.  One link points to the next item in the list, the other link points to the previous item in the list.  A list class will be implemented to support lists, stacks and queues.