Note: Check out the entire supplemental source code for this blog series.
Stacks
The stack and the queue are really just specialized forms of the Dynamic Array discussed in the previous blog post. There are several different variations of the stack, but they all contain two essential operations: insertion (usually called push) and deletion (usually called pop). A stack is a data structure in which you can push an element onto the top of the stack and pop the topmost element off of the stack. It is very much analogous to a stack of papers or a line of cars in a single lane garage. The last one in must be the first one out. This is often represented with the acronym (LIFO).
Queues
Queues work much the same was as stacks, except they operate on a first-in-first-out priority (FIFO). Also, the insertion and deletion methods are usually called enqueue and dequeue.
Implementation
Here we can see a simple implementation of a stack and a queue that implement our IDynamicSet<T> interface we defined in the first blog post of this series.
The stack keeps track of its current size to facilitate deleting nodes. When a node is inserted, the size is incremented, and when a node is deleted, the size is decremented.
The queue keeps track of a head and a tail. When a node is inserted, the tail is incremented, and when a node is deleted, the head is incremented. The head and the tail will both “wrap around” if they exceed the length of the underlying array.
Because these data structures a highly specialized, they don’t entirely implement the interface. The Insert and Delete methods will throw exceptions if you try to insert or delete an invalid node according to the LIFO or FIFO rules of stacks and queues.
Because stacks and queues are just a specialized form of dynamic arrays, the pros and cons are much the same, with a few important distinctions.
Pros
Like dynamic arrays, stacks and queues can perform insertions in Θ(1) time (unless the underlying array is full and needs to be rebuilt).
Like dynamic arrays, stacks and queues require only Θ(n) space. Essentially, they don’t use any more space than is necessary (in theory).
Like dynamic arrays, because stacks and queues store elements in sequential memory, they will experience improved performance on most hardware and operating systems.
Like dynamic arrays, stacks and queues can easily be adapted to provide Θ(1) random access (accessing the nth element).
Unlike dynamic arrays, stacks and queues can perform all deletions in Θ(1) time because they never require the array to be rebuilt.
Cons
Like dynamic arrays, if the capacity of the data structure changes significantly, the underlying array will likely need to be rebuilt many times which is a costly operation.
Like dynamic arrays, although most insertions take only Θ(1) time, if the underlying array is full and needs to be rebuilt, the insertion will take Θ(n) time.
Like dynamic arrays, even though on the surface stacks and queues don’t use any extra space, in practice this is often not the case. Often times it makes sense to grow the underlying array to a larger size than is needed to prevent the costly rebuilding should new elements be added.
Unlike dynamic arrays, stacks and queues are optimized for particular use cases and have no flexibility. Elements must be added to the very end and only the first or last elements can be deleted.
Use Cases
- A stack or a queue will perform well anytime you need to store data in a last-in-first-out (LIFO) or first-in-first-out (FIFO) approach. One example where a stack would be ideal is parsing a string of code to ensure that the braces are valid (i.e., every opening brace has a corresponding closing brace). And if you needed to keep track of customers waiting on hold at a call center, a queue would handle that very well.
Dynamic Arrays in C#
- The built-in C# generic implementation of the stacks and queues are System.Collections.Generic.Stack<T> and System.Collections.Generic.Queue<T> respectively.
Performance
| Name | Average Case Time Complexity | Worst Case Time Complexity |
|---|---|---|
| Insert | Θ(1) | Θ(n) |
| Delete | Θ(1) | Θ(n) |
| Search | Θ(n) | Θ(n) |
| Minimum | Θ(n) | Θ(n) |
| Maximum | Θ(n) | Θ(n) |