# 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)\).