Version: 0.3.38

6. Stacks, Queues, and Deques#

Lectures:

Lecture 2.6 (slides)

Objectives:

Know other useful ADT, including Stacks, Queues, and Deques

Concepts:

ADT, Sequences (ADT), Queue (ADT), Stack (ADT), Deque (ADT)

Sequences (See module seq) has been our first example of ADT. In practice however, there are several variations around sequences that are very convenient: Stacks, Queues and Deques. We will present them using ADT only here.

6.1. Stacks#

See also

  • Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java. 6th edition. John Wiley & Sons. Section 6.1, p. 226

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. 2nd edition. MIT press. Section 10.1, p. 200

  • Skiena, S. S. (2020). The Algorithm Design Manual. : Springer International Publishing. Section 3.2, p. 75

A stack is a simple variation of sequences, which behaves just like a stack of dining plates: We can only add or take plates on top of the stack. No insertion or look up in the middle of the stack. Fig. 6.8 illustrates this idea.

../_images/stacks.svg

Fig. 6.8 The stack is a constrained sequence, where insertions and removals always happen on a single end.#

Important

Stacks embody the concept of “last-in, first-out” (LIFO). This is behavior we observe when we “stack” dining plates for instance. The top of the stack always contains the last item added. The “oldest” item is the one that is at the very bottom.

stack.create() → Stack#

Create a new empty stack.

Post-conditions:

  • The stack is initially empty.

    \[length(s') = 0\]
stack.top(s: Stack) → Item#

Return the item on the top of the stack or raises an error is the stack is empty.

Pre-conditions:

  • The stack is not empty.

    \[length(s) > 0\]
Post-conditions:

None

stack.length(s: Stack) → Natural#

Return the number of items in the stack

Pre-conditions:

None

Post-conditions:

None:

stack.push(s: Stack, i: Item) → Stack#

Add a new item on top of the stack

Pre-conditions:

None

Post-conditions

  • The length of the resulting stack \(s'\) has increased by one.

    \[length(s') = length(s) + 1\]

  • The new item \(i\) is now on top of the stack

    \[top(s') = i\]

  • The rest of the stack is left unchanged

    \[pop(s') = s\]
stack.pop(s: Stack) → Stack#

Remove the top item from the stack

Pre-conditions:

  • The stack \(s\) is not empty.

    \[length(s) > 0\]
Post-conditions:

  • The length of the resulting stack \(s'\) has decreased by one.

    \[length(s') = length(s) - 1\]

6.2. Queues#

See also

  • Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java. 6th edition. John Wiley & Sons. Section 6.2, p. 238

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. 2nd edition. MIT press. Section 10.1, p. 201

  • Skiena, S. S. (2020). The Algorithm Design Manual. : Springer International Publishing. Section 3.2, p. 75

Intuitively, a queue is what we see in a supermarket when we wait at the cashier. The customers form a queue where the first arrived is the first one being served. In Computer Science, the data type that embodies this behavior is the Queue.

../_images/queues.svg

Fig. 6.9 With a queue, items are added at the back, whereas they are removed from the front.#

Fig. 6.9 illustrates the behavior of such a queue. Note that, a queue does not enable insertion or deletion in the middle. Insertions happen at the back, whereas deletion at the front.

Important

Queues embodies the concept of “first-in, first-out” (FIFO). The first item that enters the queue, is the first one that exits it. Note the contrast with stacks.

queue.create() → Queue#

Create a new empty queue.

Post-conditions:

  • The queue is initially empty.

    \[length(q') = 0\]
queue.length(q: Queue) → Natural#

Return the number of items in the queue

Pre-conditions:

None

Post-conditions:

None:

queue.enqueue(q: Queue, i: Item) → Queue#

Add a new item at the back of the queue

Pre-conditions:

None

Post-conditions

  • The length of the resulting queue \(q'\) has increased by one.

    \[length(q') = length(q) + 1\]

  • If we dequeue all the items, the last one we dequeue is Item i, which we originally enqueued.

    \[length(q') = n \implies dequeue^n(q') = i\]
queue.dequeue(q: Queue) → [Queue, Item]#

Remove the front item. It returns both a new queue, and the item that was extracted.

Pre-conditions:

  • The queue \(q\) is not empty.

    \[length(q) > 0\]
Post-conditions:

  • The length of the resulting queue \(s'\) has decreased by one.

    \[length(q') = length(q) - 1\]

6.3. Deques#

See also

  • Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java. 6th edition. John Wiley & Sons. Section 6.3, p. 248

Sometimes we need the capacity to add and remove from both ends of the queue. For instance when working with “sliding windows”, or to implement undo/redo processes. Neither the stacks of queues ADTs apply and we need a dedicated ADT called double-ended queue (or DQ), which is has been shortened as deque.

../_images/deques.svg

Fig. 6.10 Deques (double-ended queue) enable insertion and deletion from both ends.#

deque.create() → Deque#

Create a new empty deque.

Post-conditions:

  • The new deque \(d'\) is initially empty.

    \[length(d') = 0\]
deque.length(d: Deque) → Natural#

Return the number of items in the deque

Pre-conditions:

None

Post-conditions:

None:

deque.enqueueFront(d: Deque, i: Item) → Deque#

Add a new item at the front of the deque

Pre-conditions:

None

Post-conditions

  • The length of the resulting deque \(d'\) has increased by one.

    \[length(d') = length(d) + 1\]

  • If dequeue the item we just enqueue, we get the item we just enqueued.

    \[d' = enqueueFront(d, i) \implies dequeueFront(d') = (d, i)\]

  • If we dequeue all the items from the back, the last one we dequeue is Item i, which we originally enqueued in front.

    \[length(d') = n \implies dequeueBack^n(d') = i\]
deque.dequeueFront(d: Deque) → [Deque, Item]#

Remove the front item. It returns both a new deque, and the item that was extracted.

Pre-conditions:

  • The deque \(d\) is not empty.

    \[length(d) > 0\]
Post-conditions:

  • The length of the resulting deque \(d'\) has decreased by one.

    \[length(d') = length(d) - 1\]
deque.enqueueBack(d: Deque, i: Item) → Deque#

Add a new item at the back of the deque

Pre-conditions:

None

Post-conditions

  • The length of the resulting deque \(d'\) has increased by one.

    \[length(q') = length(q) + 1\]

  • If dequeue the item we just enqueue, we get the item we just enqueued.

    \[d' = enqueueBack(d, i) \implies dequeueBack(d') = (d, i)\]

  • If we dequeue all the items from the back, the last one we dequeue is Item i, which we originally enqueued in front.

    \[length(d') = n \implies dequeueFront^n(d') = i\]
deque.dequeueBack(d: Deque) → [Deque, Item]#

Remove the back item. It returns both a new deque, and the item that was extracted.

Pre-conditions:

  • The deque \(d\) is not empty.

    \[length(d) > 0\]
Post-conditions:

  • The length of the resulting deque \(d'\) has decreased by one.

    \[length(d') = length(d) - 1\]