Stacks, Queues and Deques

Often there are data structures that only require a limited number of interactions. For example, this is the case when only the first and last elements added matter. Sacrificing unnecessary functionality can dramatically increase the efficiency of routines if the right implementation of these data structures is used. We apply this philosophy below when talking about stacks, queues and deques.

Stacks

A stack is a data structure similar to a list, except operations are only performed on the element that is most recently added. In other words, it is first-in last-out (FILO). In particular, stacks use the following routines.

  • push(a)

    Pushes element a onto the top of the stack.

  • peek()

    Returns the element on the top of the stack. Throws an exception if the stack is empty.

  • pop()

    Removes the top element from the stack and returns that element. Throws an exception if the stack is empty.

Any good implementation of a stack would be designed to allow these routines to be as efficient as possible. We present one such efficient way: using an array implementation.

Array implementation

Reading from an array is fast, and having subsequent elements in a stack be adjacent in memory makes the implementation cache efficient. Therefore, we usually want to implement a data structure using an array rather than a linked list.

One way to do this for a stack is to allocate an array of size capacity. The initial size capacity is chosen to be large enough to handle most use cases but small enough to be memory efficient. The stack would not use the entire allocated array. Rather, the size of the stack would be tracked.

import numpy as np

##  Array implementation of a stack using numpy.
Class Stack():
   def __init__(self,capacity=100):
      self.store = np.empty(capacity)
      self.capacity = capacity
      self.size = 0

Now when the stack is popped, the size of the array is just reduced.

##  Removes and returns the top element of the stack.
   def pop(self):
      try:
         self.size -= 1
         return self.store[self.size]
      except IndexError:
         self.size = 0
         raise ValueError

Peeking works similarly. Adding to the array is straightforward unless self.size grows larger than self.capacity. Then the storage needs to somehow expand in size. One common way to do this is to use the doubling trick, where the array size is doubled when the total capacity is full. Unfortunately, this requires copying all the existing elements to the new array.

##  Pushes an element onto the top of the stack.
   def push(self,a):
      try:
         self.store[self.size] = a
      except IndexError:
         new_store = np.empty(2*self.capacity)
         new_store[:self.capacity] = self.store[:self.capacity]

         self.store = new_store
         self.capacity *= 2

         self.store[self.size] = a

      finally:
         self.size += 1

Complexity analysis

For push and peek, the analysis is relatively straightforward: the time complexity is \(O(1)\). For push, the only difficulty comes when the array needs to be doubled, and copying takes a linear amount of time. However, when performing an amortized time analysis, this extra time can be “spread out” over the number of push operations where the doubling is not required. Therefore, pushing an element onto the stack takes \(O(1)\) time.

In terms of memory, the analysis might seem stranger at first. But since doubling the size the stack implies doubling the size of the array capacity, we can conclude that the memory usage is \(O(n)\).

All of these complexity results are as good as anyone can expect for an implentation of a stack.

Queues

A queue is similar to a stack, except elements are handled in a first-in first-out (FIFO) manner. Queues have the following routines.

  • push(a)

    Adds element a to the queue.

  • peek()

    Returns element in queue that was least recently added. Throws an exception if the queue is empty.

  • pop()

    Removes and returns element in queue that was least recently added. Throws an exception if the queue is empty.

Again, we outline an array implementation of a queue below.

Array implementation

The implementation of a queue is similar to that of a stack. The push routine would be nearly identical (including the doubling trick), and peek would instead return the first inserted element of the queue. The only complication is efficiently implementing pop. A naive way to do this would require shifting all elements in the array to the left so that the first element of the array corresponds to the first element in the queue. This naive solution requires a linear amount of time for every pop operation.

But who says the first element of the array needs to correspond to the first element in the queue? Instead of requiring a shift after every pop, it is more efficient to keep track of where the queue starts in the array. At a first glace, this may seem space-inefficient because the portion of the array before the first element in the queue is not being used. To prevent doubling the array with a queue size less than capacity, one can implement a circular buffer. Essentially, if there is enough space in the array, the queue “wraps around”. In other words, a new element is added at the \((a + s) \mod c\) position of the array, where \(a\) is the starting position of the queue, \(s\) is the new size, and \(c\) is the array capacity. This only works if \(s < c\); otherwise elements in the queue will get overwritten. If that is the case, then doubling the array size and copying is necessary.

This implementation will lead to all three operations taking \(O(1)\) time (amortized), and the queue taking \(O(n)\) space, which is as efficient as possible (ignoring constants).

Priority queues

The priority queue is similar to a queue, except each element has a numerical priority associated with it. The pop operation removes and returns the element with the highest priority, rather than the least recently added element.

An efficient implementation for this is a max-heap.

Deques

A deque is a combination of a queue and a stack, where one can push and pop from both the left and right sides. In particular, deques implement the following routines.

  • push_left(a)

    Pushes an element a to the left side of the deque.

  • push_right(a)

    Pushes an element a to the right side of the deque.

  • peek_left()

    Returns the leftmost element in the deque. Throws an exception if the deque is empty.

  • peek_right()

    Returns the rightmost element in the deque. Throws an exception if the deque is empty.

  • pop_left()

    Removes and returns the leftmost element in the deque. Throws an exception if the deque is empty.

  • pop_right()

    Removes and returns the rightmost element in the deque. Throws an exception if the deque is empty.

This is common in multi-server job scheduling, where each server has its own deque of jobs to complete. Jobs may be enqueued by pushing left, while a server might pop right to start jobs. When a server’s own deque is empty, it might start jobs other servers have not started by popping left.

Using the same approach as a queue, all the above operations can be performed in \(O(1)\) amortized time while using a memory footprint of \(O(n)\).