Stacks and Queues
A stack is a kind of list where items are always added to the front and removed from the front. Thus, a stack is a First In, Last Out (FILO) structure. A stack can be thought of a structure that resembles a stack of trays. Each time a new piece of data is added to the stack, it is placed on the top. Each time a piece of data is removed it also must be removed from the top. Typically only the top item is visible. You cannot remove something from the middle.
Queues like stacks are a special kind of list. In the case of a queue, items are added to the back and removed from the front. In other words a queue is a First In First Out (FIFO) structure. A queue is essentially a line up.
The idea of front, back, and top in stacks and queues have absolutely nothing to do with their positions within the data structures used to implement them. It is up to the implementer to make that decision on where to put the frontmost, topmost and backmost items and maintain order.
Operations
Typically stacks and queues have the ability to do the following:
- add an item
- remove an item
- access the "next" item to be removed
There are various names that we attribute to these operations for these:
| Operation | Stack | Queue |
|---|---|---|
| add an item | push | enqueue |
| remove an item | pop | dequeue |
| access the "next" item to be removed | top | front |
The most important thing to remember about stacks and queues is that its all about the ordering. This absolutely must be tracked and maintained. When you add an item it must be positioned as the newest item. When you remove an item the one you remove is always the newest item for stacks or the oldest item for queues. You can't put something into the middle of a stack or queue. When you remove there is only one item that you can remove. Access is typically only granted to the item that is at the top/front of the stack/queue.
Stacks and Queues are NOT for general storage. They are used to track ordering. Any other features other than the 3 above must be secondary.
Applications
Applications of stacks and queues typically involve tracking the ordering of a set of values. The question is whether the application is interested in the data in the same order as it was received or reverse. Note that this is not as straight forward as it may seem. We are not talking about encountering all the data in one go. It will typically involve continuous adding and removing of data to the Stack or Queue.
Some examples:
- bracket checking (stack)
- breadthfirst tree traversals (queue)
- infix to postfix expression (stack)
- postfix expression calculation (stack)
Stack Implementation
There are two general ways to implement a stack. As a stack is essentially a list with a restriction on the operations of a list, we can use either an array or a linked list to implement a stack. The key to understanding how to do this efficiently is to understand the nature of a stack.
A stack is a FILO (first in last out) structure. Thus, the most important thing to remember about it is that when you remove an item from the stack, you want to remove the newest item, where ever that may be. How it is stored internally (which end of the list do you insert into for example) does not matter as long as you always remove the newest item. Thus, the question of how to implement a stack comes down to choosing an algorithm such that the operations can be completed as quickly as possible.
Recall that the operations are as follows:
- push - add a new item to the stack
- pop - removes top item from the stack
- initialize - create an empty stack
- isEmpty - tests for whether or not stack is empty
- isFull - tests to see if stack is full and cannot grow (not always needed)
- top - looks at value of the top item but do not remove it
Array Implementation
With a list that implemented as an array we typically start by creating an array that is bigger than what we need. To add a value to the end of an array is a constant time operation as long as we track where the end is. If we were to do that, the most recently added item will be at the back of the array. Removing that item simply involves decreasing the end of array tracker by one.
Check out this animation for details:
http://cathyatseneca.github.io/DSAnim/web/arraystack.html
Linked List Implementation
To implement a stack using a linked list, we have to consider the type of linked list we would use and which end of the list we would want to insert to.
The simplest linked list is a singly list. If this linked list was implemented with just a pointer to the first node, insertion would be O(1) at front of list, O(n) at back of list. removal is O(1) at front of list and O(n) at back of list. If we added an end pointer to the list, then insertion to back of list can be O(1) also, however removing from the back of the list will still be O(n).
If we were to insert always at front of list, then the most recently added item would be at the front of the list. Thus, removal must occur from the front as we always remove the most recently added item. Since we can do both quickly with a simple singularly linked list, that is all we will need to do.
Check out this animation for details:
http://cathyatseneca.github.io/DSAnim/web/llstack.html
Queue Implementation
This section will look at how to efficiently implement a queue using both an array and a linked list. Like a stack, a queue is also a special type of list. While a queue is a "line up" the ideas of front and back are not meant to be taken literally. The key is to understand that a Queue is a FIFO (first in first out) structure. That is the item to be removed is the oldest item in the list. as long as this is true, it doesn't matter where exactly the items get put into the queue or where it is removed.
Linked List implementation
To implement a queue using a linked list, we have to consider the type of linked list we would use and which end of the list we would want to insert to.
The simplest linked list is a singly list. If this linked list was implemented with just a pointer to the first node, insertion would be O(1) at front of list, O(n) at back of list. removal is O(1) at front of list and O(n) at back of list. If we added an end pointer to the list, then insertion to back of list can be O(1) also, however removing from the back of the list will still be O(n).
Now, if we perform enqueue by inserting at the front of the list, the oldest item would be at the back of the list and thus, dequeue would have to be done there. enqueue would be quick O(1) but dequeue would be slow O(n). However, if we enqueue by inserting to the end of the list using a linked list that tracks the last node, then the oldest item would be at the front of the linked list. This will allow us to perform enqueue and dequeue in O(1) time.
Checkout this animation for details:
http://cathyatseneca.github.io/DSAnim/web/llqueue.html
Array Implementation
Implementing a queue with an array is a bit more complicated than implementing a stack using an array.
Consider the typical way we implement a list using an array. To insert a value to the front of the list, we would move all existing values to an element that is one index higher in the array then add the new value to the first element. To remove a value we would move all values in the array to element one index lower, overwriting the first element. Both the removal and insertion are O(n) operations.
Thus, if we were to use this list, and performed enqueues at the front of the list, the enqueue function would be O(n). Enqueuing in this manner would mean that the oldest item would be at the back of the array. Removing from back of list is fast so we can accomplish this in O(1) time as long as we track where the last item is.
Now... if we were to enqueue to the end of the list, the oldest item would be at the front, and thus removal would have to be done to the front of the list. In this case, enqueue would be fast O(1) but dequeue would be slow O(n).
So clearly we need to come up with a better way to handle this.
One way that we can handle this is to track two indices instead of one. The first is the index of the element at the front of the list. The second is the index of the element at the back of the list. When you insert, insert to the index of the back element and increment the index for back. When you remove, remove by incrementing the index of the front. The second part of the implementation is that we need to treat the array as if it is a ring. That is, the next element of the last element is the first element and the previous element of the first element is the last element. If we do not, we will quickly create a list with lots of unused space at the front of the list and run out of space.
Check out this animation for details: