So far we’ve looked at collections that provide very basic data storage, essentially abstractions over an array. In this section, we’re going to look at what happens when we add a few very basic behaviors that entirely change the utility of the collections.
Stack
A stack is a collection that returns objects to the caller in a Last-In-First-Out (LIFO) pattern. What this means is that the last object added to the collection will be the first object returned.
Stacks differ from list and array-like collections. They cannot be indexed directly, objects are added and removed using different methods, and their contents are more opaque than lists and arrays. What I mean by this is that while a list-based collection provides a Contains method, a stack does not. Additionally, a stack is not enumerable. To understand why this is, let’s look at what a stack is and how the usage of a stack drives these differences.
One of the most common analogies for a stack is the restaurant plate stack. This is a simple spring-loaded device onto which clean plates are stacked. The spring ensures that regardless of how many plates are in the stack, the top plate can be easily accessed. Clean plates are added to the top of the stack, and when a customer removes a plate, he or she is removing the top-most plate (the most recently added plate).
We start with an empty plate rack.
And then we add a red, a blue, and a green plate to the rack in that order.
The key point to understand here is that as new plates are added, they are added to the top of the stack. If a customer retrieves a plate, he or she will get the most recently added plate (the green plate). The next customer would get the blue plate, and finally the red plate would be removed.
Now that we understand how a stack works, let’s define a few new terms. When an item is added to the stack, it is “pushed” on using the Push method. When an item is removed from the stack, it is “popped” off using the Pop method. The top item in the stack, the most recently added, can be “peeked” at using the Peek method. Peeking allows you to view the item without removing it from the stack (just like the customer at the plate rack would be able to see the color of the top plate). With these terms in mind, let’s look at the implementation of a Stack class.
Class Definition
The Stack class defines Push, Pop, and Peek methods, a Count property, and uses the LinkedList<T> class to store the values contained in the stack.
public class Stack
{
LinkedList _items = new LinkedList();
public void Push(T value)
{
throw new NotImplementedException();
}
public T Pop()
{
throw new NotImplementedException();
}
public T Peek()
{
throw new NotImplementedException();
}
public int Count
{
get;
}
}
Push
| Behavior | Adds an item to the top of the stack. |
| Performance | O(1) |
Since we’re using a linked list as our backing store, all we need to do is add the new item to the end of the list.
public void Push(T value)
{
_items.AddLast(value);
}
Pop
| Behavior | Removes and returns the last item added to the stack. If the stack is empty, an InvalidOperationException is thrown. |
| Performance | O(1) |
Push adds items to the back of the list, so we will “pop” them from the back. If the list is empty, an exception is thrown.
public T Pop()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("The stack is empty");
}
T result = _items.Tail.Value;
_items.RemoveLast();
return result;
}
Peek
| Behavior | Returns the last item added to the stack but leaves the item on the stack. If the stack is empty, an InvalidOperationException is thrown. |
| Performance | O(1) |
public T Peek()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("The stack is empty");
}
return _items.Tail.Value;
}
Count
| Behavior | Returns the number of items in the stack. |
| Performance | O(1) |
Since the stack is supposed to be an opaque data structure, why do we have a Count property? Knowing whether a stack is empty (Count == 0) is very useful, especially since Pop throws an exception when the stack is empty.
public int Count
{
get
{
return _items.Count;
}
}
Example: RPN Calculator
The classic stack example is the Reverse Polish Notation (RPN) calculator.
RPN syntax is quite simple. It uses:
<operand> <operand> <operator>
rather than the traditional:
<operand> <operator> <operand>.
In other words, instead of saying “4 + 2,” we would say “4 2 +.” If you want to understand the historical significance of RPN syntax, I encourage you to head to Wikipedia or your favorite search engine.
The way RPN is evaluated, and the reason that a stack is so useful when implementing an RPN calculator, can be seen in the following algorithm:
for each input value if the value is an integer push the value on to the operand stack else if the value is an operator pop the left and right values from the stack evaluate the operator push the result on to the stack pop answer from stack.
So given the input string “4 2 +,” the operations would be:
push (4) push (2) push (pop() + pop())
Now the stack contains a single value: six (the answer).
The following is a complete implementation of a simple calculator that reads an equation (for example, “4 2 +”) from console input, splits the input at every space ([“4”, “2”, and “+”]), and performs the RPN algorithm on the input. The loop continues until the input is the word “quit”.
void RpnLoop()
{
while (true)
{
Console.Write("> ");
string input = Console.ReadLine();
if (input.Trim().ToLower() == "quit")
{
break;
}
// The stack of integers not yet operated on.
Stack values = new Stack();
foreach (string token in input.Split(new char[] { ' ' }))
{
// If the value is an integer...
int value;
if (int.TryParse(token, out value))
{
// ... push it to the stack.
values.Push(value);
}
else
{
// Otherwise evaluate the expression...
int rhs = values.Pop();
int lhs = values.Pop();
// ... and pop the result back to the stack.
switch (token)
{
case "+":
values.Push(lhs + rhs);
break;
case "-":
values.Push(lhs - rhs);
break;
case "*":
values.Push(lhs * rhs);
break;
case "/":
values.Push(lhs / rhs);
break;
case "%":
values.Push(lhs % rhs);
break;
default:
throw new ArgumentException(
string.Format("Unrecognized token: {0}", token));
}
}
}
// The last item on the stack is the result.
Console.WriteLine(values.Pop());
}
}
Queue
Queues are very similar to stacks—they provide an opaque collection from which objects can be added (enqueued) or removed (dequeued) in a manner that adds value over a list-based collection.
Queues are a First-In-First-Out (FIFO) collection. This means that items are removed from the queue in the same order that they were added. You can think of a queue like a line at a store checkout counter—people enter the line and are serviced in the order they arrive.
Queues are commonly used in applications to provide a buffer to add items for future processing or to provide orderly access to a shared resource. For example, if a database is capable of handling only one connection, a queue might be used to allow threads to wait their turn (in order) to access the database.
Class Definition
The Queue, like the Stack, is backed by a LinkedList. Additionally, it provides the methods Enqueue (to add items), Dequeue (to remove items), Peek, and Count. Like Stack, it will not be treated as a general purpose collection, meaning it will not implement ICollection<T>.
public class Queue
{
LinkedList _items = new LinkedList();
public void Enqueue(T value)
{
throw new NotImplementedException();
}
public T Dequeue()
{
throw new NotImplementedException();
}
public T Peek()
{
throw new NotImplementedException();
}
public int Count
{
get;
}
}
Enqueue
| Behavior | Adds an item to the end of the queue. |
| Performance | O(1) |
This implementation adds the item to the start of the linked list. The item could just as easily be added to the end of the list. All that really matters is that items are enqueued to one end of the list and dequeued from the other (FIFO). Notice that this is the opposite of the Stack class where items are added and removed from the same end (LIFO).
Public void Enqueue(T value)
{
_items.AddFirst(value);
}
Dequeue
| Behavior | Removes and returns the oldest item from the queue. An InvalidOperationException is thrown if the queue is empty. |
| Performance | O(1) |
Since Enqueue added the item to the start of the list, Dequeue must remove the item at the end of the list. If the queue contains no items, an exception is thrown.
public T Dequeue()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("The queue is empty");
}
T last = _items.Tail.Value;
_items.RemoveLast();
return last;
}
Peek
| Behavior | Returns the next item that would be returned if Dequeue were called. The queue is left unchanged. An InvalidOperationException is thrown if the queue is empty. |
| Performance | O(1) |
public T Peek()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("The queue is empty");
}
return _items.Tail.Value;
}
Count
| Behavior | Returns the number of items currently in the queue. Returns 0 if the queue is empty. |
| Performance | O(1) |
public int Count
{
get
{
return _items.Count;
}
}
Deque (Double-Ended Queue)
A double-ended queue, or deque, extends the queue behavior by allowing items to be added or removed from both sides of the queue. This new behavior is useful in several problem domains, specifically task and thread scheduling. It is also generally useful for implementing other data structures. We’ll see an example of using a deque to implement another data structure later.
Class Definition
The Deque class is backed by a doubly linked list. This allows us to add and remove items from the front or back of the list and access the First and Last properties. The main changes between the Queue class and the Deque class are that the Enqueue, Dequeue, and Peek methods have been doubled into First and Last variants.
public class Deque
{
LinkedList _items = new LinkedList();
public void EnqueueFirst(T value)
{
throw new NotImplementedException();
}
public void EnqueueLast(T value)
{
throw new NotImplementedException();
}
public T DequeueFirst()
{
throw new NotImplementedException();
}
public T DequeueLast()
{
throw new NotImplementedException();
}
public T PeekFirst()
{
throw new NotImplementedException();
}
public T PeekLast()
{
throw new NotImplementedException();
}
public int Count
{
get;
}
}
Enqueue
EnqueueFirst
| Behavior | Adds the provided value to the head of the queue. This will be the next item dequeued by DequeueFirst. |
| Performance | O(1) |
public void EnqueueFirst(T value)
{
_items.AddFirst(value);
}
EnqueueLast
| Behavior | Adds the provided value to the tail of the queue. This will be the next item dequeued by DequeueLast. |
| Performance | O(1) |
public void EnqueueLast(T value)
{
_items.AddLast(value);
}
Dequeue
DequeueFirst
| Behavior | Removes and returns the first item in the deque. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T DequeueFirst()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("DequeueFirst called when deque is empty");
}
T temp = _items.Head.Value;
_items.RemoveFirst();
return temp;
}
DequeueLast
| Behavior | Removes and returns the last item in the deque. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T DequeueLast()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("DequeueLast called when deque is empty");
}
T temp = _items.Tail.Value;
_items.RemoveLast();
return temp;
}
PeekFirst
| Behavior | Returns the first item in the deque but leaves the collection unchanged. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T PeekFirst()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("PeekFirst called when deque is empty");
}
return _items.Head.Value;
}
PeekLast
| Behavior | Returns the last item in the deque but leaves the collection unchanged. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T PeekLast()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("PeekLast called when deque is empty");
}
return _items.Tail.Value;
}
Count
| Behavior | Returns the number of items currently in the deque, or 0 if the deque is empty. |
| Performance | O(1) |
public int Count
{
get
{
return _items.Count;
}
}
Example: Implementing a Stack
Deques are often used to implement other data structures.
We’ve seen a stack implemented using a LinkedList, so now let’s look at one implemented using a Deque.
You might wonder why I would choose to implement a Stack using a Deque rather than a LinkedList. The reason is one of performance and code reusability. A linked list has the cost of per-node overhead and reduced data locality—the items are allocated in the heap and the memory locations may not be near each other, causing a larger number of cache misses and page faults at the CPU and memory hardware levels. A better performing implementation of a queue might use an array as the backing store rather than a list. This would allow for less per-node overhead and could improve performance by addressing some locality issues.
Implementing a Stack or Queue as an array is a more complex implementation, however. By implementing the Deque in this more complex manner and using it as the basis for other data structures, we can realize the performance benefits for all structures while only having to write the code once. This accelerates development time and reduces maintenance costs.
We will look at an example of a Deque as an array later in this section, but first let’s look at an example of a Stack implemented using a Deque.
public class Stack
{
Deque _items = new Deque();
public void Push(T value)
{
_items.EnqueueFirst(value);
}
public T Pop()
{
return _items.DequeueFirst();
}
public T Peek()
{
return _items.PeekFirst();
}
public int Count
{
get
{
return _items.Count;
}
}
}
Notice that all of the error checking is now deferred to the Deque and any optimization or bug fix made to the Deque will automatically apply to the Stack class. Implementing a Queue is just as easy and as such is left as an exercise to the reader.
Array Backing Store
As mentioned previously, there are benefits to using an array rather than a linked list as the backing store for the Deque<int> (a deque of integers). Conceptually this seems simple, but there are actually several issues that need to be addressed for this to work.
Let’s look at some of these issues graphically and then see how we might deal with them. Along the way, keep in mind the growth policy issues discussed in the ArrayList section and that those same issues apply here.
When the collection is created, it is a 0-length array. Let’s look at how some actions affect the internal array. As we go through this, notice that the green “h” and red “t” in the figures refer to “head” and “tail,” respectively. The head and tail are the array indexes that indicate the first and last items in the queue. As we add and remove items, the interaction between head and tail will become clearer.
Deque deq = new Deque(); deq.EnqueueFirst(1);
deq.EnqueueLast(2);
deq.EnqueueFirst(0);
Notice what has happened at this point. The head index has wrapped around to the end of the array. Now the first item in the deque, what would be returned by DequeueFirst, is the value at array index three (zero).
deq.EnqueueLast(3);
At this point, the array is filled. When another item is added, the following will occur:
- The growth policy will define the size of the new array.
- The items will be copied from head to tail into the new array.
- The new item will be added.
-
EnqueueFirst- The item is added at index zero (the copy operation leaves this open). -
EnqueueLast- The item is added to the end of the array.
-
deq.EnqueueLast(4);
Now let’s see what happens as items are removed from the Deque.
deq.DequeueFirst();
deq.DequeueLast();
The critical point to note is that regardless of the capacity of the internal array, the logical contents of the Deque are the items from the head index to the tail index, taking into account the need to wrap around at the end of the array. An array that provides the behavior of wrapping around from the head to the tail is often known as a circular buffer.
With this understanding of how the array logic works, let’s dive right into the code.
Class Definition
The array-based Deque methods and properties are the same as the list-based, so they will not be repeated here. However, the list has been replaced with an array and there are now three properties to contain the size, head, and tail information.
public class Deque
{
T[] _items = new T[0];
// The number of items in the queue.
int _size = 0;
// The index of the first (oldest) item in the queue.
int _head = 0;
// The index of the last (newest) item in the queue.
int _tail = -1;
...
}
Enqueue
Growth Policy
When the internal array needs to grow, the algorithm to increase the size of the array, copy the array contents, and update the internal index values needs to run. The Enqueue method performs that operation and is called by both EnqueueFirst and EnqueueLast. The startingIndex parameter is used to determine whether to leave the array slot at index zero open (in the case of EnqueueFirst).
Pay specific attention to how the data is unwrapped in cases where the walk from head to tail requires going around the end of the array back to zero.
private void allocateNewArray(int startingIndex)
{
int newLength = (_size == 0) ? 4 : _size * 2;
T[] newArray = new T[newLength];
if (_size > 0)
{
int targetIndex = startingIndex;
// Copy the contents...
// If the array has no wrapping, just copy the valid range.
// Else, copy from head to end of the array and then from 0 to the tail.
// If tail is less than head, we've wrapped.
if (_tail < _head)
{
// Copy the _items[head].._items[end] -> newArray[0]..newArray[N].
for (int index = _head; index < _items.Length; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
// Copy _items[0].._items[tail] -> newArray[N+1]..
for (int index = 0; index <= _tail; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
}
else
{
// Copy the _items[head].._items[tail] -> newArray[0]..newArray[N]
for (int index = _head; index <= _tail; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
}
_head = startingIndex;
_tail = targetIndex - 1; // Compensate for the extra bump.
}
else
{
// Nothing in the array.
_head = 0;
_tail = -1;
}
_items = newArray;
}
EnqueueFirst
| Behavior | Adds the provided value to the head of the queue. This will be the next item dequeued by DequeueFirst. |
| Performance | O(1) in most cases; O(n) when growth is necessary. |
public void EnqueueFirst(T item)
{
// If the array needs to grow.
if (_items.Length == _size)
{
allocateNewArray(1);
}
// Since we know the array isn't full and _head is greater than 0,
// we know the slot in front of head is open.
if (_head > 0)
{
_head--;
}
else
{
// Otherwise we need to wrap around to the end of the array.
_head = _items.Length - 1;
}
_items[_head] = item;
_size++;
}
EnqueueLast
| Behavior | Adds the provided value to the tail of the queue. This will be the next item dequeued by DequeueLast. |
| Performance | O(1) in most cases; O(n) when growth is necessary. |
public void EnqueueLast(T item)
{
// If the array needs to grow.
if (_items.Length == _size)
{
allocateNewArray(0);
}
// Now we have a properly sized array and can focus on wrapping issues.
// If _tail is at the end of the array we need to wrap around.
if (_tail == _items.Length - 1)
{
_tail = 0;
}
else
{
_tail++;
}
_items[_tail] = item;
_size++;
}
Dequeue
DequeueFirst
| Behavior | Removes and returns the first item in the deque. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T DequeueFirst()
{
if (_size == 0)
{
throw new InvalidOperationException("The deque is empty");
}
T value = _items[_head];
if (_head == _items.Length - 1)
{
// If the head is at the last index in the array, wrap it around.
_head = 0;
}
else
{
// Move to the next slot.
_head++;
}
_size--;
return value;
}
DequeueLast
| Behavior | Removes and returns the last item in the deque. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T DequeueLast()
{
if (_size == 0)
{
throw new InvalidOperationException("The deque is empty");
}
T value = _items[_tail];
if (_tail == 0)
{
// If the tail is at the first index in the array, wrap it around.
_tail = _items.Length - 1;
}
else
{
// Move to the previous slot.
_tail--;
}
_size--;
return value;
}
PeekFirst
| Behavior | Returns the first item in the deque but leaves the collection unchanged. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T PeekFirst()
{
if (_size == 0)
{
throw new InvalidOperationException("The deque is empty");
}
return _items[_head];
}
PeekLast
| Behavior | Returns the last item in the deque but leaves the collection unchanged. An InvalidOperationException is thrown if the deque is empty. |
| Performance | O(1) |
public T PeekLast()
{
if (_size == 0)
{
throw new InvalidOperationException("The deque is empty");
}
return _items[_tail];
}
Count
| Behavior | Returns the number of items currently in the deque or 0 if the deque is empty. |
| Performance | O(1) |
public int Count
{
get
{
return _size;
}
}
Comments