Stacks, Queues, and Deques
Contents
- Stacks
- Queues
- Deques
Time Complexity
| Stack ADT | Push | Pop | Top |
|---|---|---|---|
| Dynamic Array / SLL / CLL / DLL | $\Theta(1)$ | $\Theta(1)$ | $\Theta(1)$ |
| Queue ADT | Enqueue | Dequeue | Front |
|---|---|---|---|
| Circular Dynamic Array / SLL / CLL / DLL | $\Theta(1)$ | $\Theta(1)$ | $\Theta(1)$ |
| Deque ADT | AddFirst | AddLast | RemoveFirst | RemoveLast |
|---|---|---|---|---|
| Circular Dynamic Array / DLL | $\Theta(1)$ | $\Theta(1)$ | $\Theta(1)$ | $\Theta(1)$ |
| SLL / CLL | $\Theta(1)$ | $\Theta(1)$ | $\Theta(1)$ | $\Theta(n)$ |
Stacks
- A stack is a one-ended linear data structure.
- A stack uses the last in, first out (FIFO) principle.
- A stack has two major operations: push and pop, meaning insert and delete respectively.
Applications
- Function calls in computer programs (recursion trace or stack trace)
- Undo mechanism in all text editors
- Back button in all web browsers
- Evaluation of arithmetic expressions
Stack ADT
| Method | Functionality |
|---|---|
| push(e) | Adds element e to the top of the stack. |
| pop() | Removes and returns the top element from the stack (or null if the stack is empty). |
| top() | Returns the top element of the stack, without removing it (or null if the stack is empty). |
| size() | Returns the number of elements in the stack. |
| isEmpty() | Returns a boolean indicating whether the stack is empty |
Operations
| Method | Return value | Stack contents |
|---|---|---|
| push(5) | - | (5) |
| push(3) | - | (5, 3) |
| size() | 2 | (5, 3) |
| pop() | 3 | (5) |
| isEmpty() | false | (5) |
| pop() | 5 | () |
| isEmpty() | true | () |
| pop() | null | () |
| push(7) | - | (7) |
| push(9) | - | (7, 9) |
| top() | 9 | (7, 9) |
| push(4) | - | (7, 9, 4) |
| size() | 3 | (7, 9, 4) |
| pop() | 4 | (7, 9) |
| push(6) | - | (7, 9, 6) |
| push(8) | - | (7, 9, 6, 8) |
| pop() | 8 | (7, 9, 6) |
java.util.Stack class
| Our Stack ADT | Class java.util.Stack |
|---|---|
| size() | size() |
| isEmpty() | empty() |
| push(e) | push(e) |
| pop() | pop() |
| top() | peek() |
Stack ADT Interface
public interface Stack {
// Returns the number of elements in the stack.
int size();
// Tests whether the stack is empty.
boolean isEmpty();
// Inserts an element at the top of the stack.
void push(E e);
// Returns, but does not remove, the element at the top of the stack.
E top();
// Removes and returns the top element from the stack.
E pop();
}
Stack ADT $\rightarrow$ Array Implementation (0-indexed)
- Stack top index = $t$
- Stack top element = $data[t]$
- Stack size (or number of elements) = $t + 1$
public class ArrayStack implements Stack {
/** Default array capacity. */
public static final int CAPACITY=1000; // default array capacity
/** Generic array used for storage of stack elements. */
private E[] data; // generic array used for storage
/** Index of the top element of the stack in the array. */
private int t = -1; // index of the top element in stack
/** Constructs an empty stack using the default array capacity. */
public ArrayStack() { this(CAPACITY); } // constructs stack with default capacity
/**
* Constructs and empty stack with the given array capacity.
* @param capacity length of the underlying array
*/
@SuppressWarnings({"unchecked"})
public ArrayStack(int capacity) { // constructs stack with given capacity
data = (E[]) new Object[capacity]; // safe cast; compiler may give warning
}
/**
* Returns the number of elements in the stack.
* @return number of elements in the stack
*/
@Override
public int size() { return (t + 1); }
/**
* Tests whether the stack is empty.
* @return true if the stack is empty, false otherwise
*/
@Override
public boolean isEmpty() { return (t == -1); }
/**
* Inserts an element at the top of the stack.
* @param e the element to be inserted
* @throws IllegalStateException if the array storing the elements is full
*/
@Override
public void push(E e) throws IllegalStateException {
if (size() == data.length) throw new IllegalStateException("Stack is full");
data[++t] = e; // increment t before storing new item
}
/**
* Returns, but does not remove, the element at the top of the stack.
* @return top element in the stack (or null if empty)
*/
@Override
public E top() {
if (isEmpty()) return null;
return data[t];
}
/**
* Removes and returns the top element from the stack.
* @return element removed (or null if empty)
*/
@Override
public E pop() {
if (isEmpty()) return null;
E answer = data[t];
data[t] = null; // dereference to help garbage collection
t--;
return answer;
}
/**
* Produces a string representation of the contents of the stack.
* (ordered from top to bottom). This exists for debugging purposes only.
*
* @return textual representation of the stack
*/
public String toString() {
StringBuilder sb = new StringBuilder("(");
for (int j = t; j >= 0; j--) {
sb.append(data[j]);
if (j > 0) sb.append(", ");
}
sb.append(")");
return sb.toString();
}
/** Demonstrates sample usage of a stack. */
public static void main(String[] args) {
Stack S = new ArrayStack<>(); // contents: ()
S.push(5); // contents: (5)
S.push(3); // contents: (5, 3)
System.out.println(S.size()); // contents: (5, 3) outputs 2
System.out.println(S.pop()); // contents: (5) outputs 3
System.out.println(S.isEmpty()); // contents: (5) outputs false
System.out.println(S.pop()); // contents: () outputs 5
System.out.println(S.isEmpty()); // contents: () outputs true
System.out.println(S.pop()); // contents: () outputs null
S.push(7); // contents: (7)
S.push(9); // contents: (7, 9)
System.out.println(S.top()); // contents: (7, 9) outputs 9
S.push(4); // contents: (7, 9, 4)
System.out.println(S.size()); // contents: (7, 9, 4) outputs 3
System.out.println(S.pop()); // contents: (7, 9) outputs 4
S.push(6); // contents: (7, 9, 6)
S.push(8); // contents: (7, 9, 6, 8)
System.out.println(S.pop()); // contents: (7, 9, 6) outputs 8
}
} Data Overflow Problem
Problem: Stack array is of fixed size. If capacity is low, the program throws exception when there is overflow. If capacity is high, a lot of memory is wasted.
Solution: Use a dynamic array or a linked list.
Stack ADT $\rightarrow$ SLL Implementation
SLL or CLL or DLL?
- Which list to choose: SLL, CLL, DLL? SLL. Why?
- Should SLL head be stack top or stack bottom? Stack top. Why?
| Stack method | SLL method |
|---|---|
| size() | list.size() |
| isEmpty() | list.isEmpty() |
| push(e) | list.addFirst(e) |
| pop() | list.removeFirst() |
| top() | list.first() |
public class LinkedStack implements Stack {
private SinglyLinkedList list = new SinglyLinkedList<>(); // an empty list
public LinkedStack() { } // new stack relies on the initially empty list
public int size() { return list.size(); }
public boolean isEmpty() { return list.isEmpty(); }
public E top() { return list.first(); }
public void push(E element) { list.addFirst(element); }
public E pop() { return list.removeFirst(); }
}
Queues
- A queue is a two-ended linear data structure.
- A queue uses the first in, first out (FIFO) principle.
- A queue has two major operations: enqueue and dequeue, meaning insert and delete respectively.
Applications
- Client/customer requests severed
- Movie tickets, bus tickets, plane tickets, etc
- Process scheduling in operating systems
Queue ADT
| Method | Functionality |
|---|---|
| enqueue(e) | Adds element e to the back of queue. |
| dequeue() | Removes and returns the first element from the queue (or null if the queue is empty). |
| first() | Returns the first element of the queue, without removing it (or null if the queue is empty). |
| size() | Returns the number of elements in the queue. |
| isEmpty() | Returns a boolean indicating whether the queue is empty |
Queue ADT Interface
public interface Queue {
/** Returns the number of elements in the queue. */
int size();
/** Tests whether the queue is empty. */
boolean isEmpty();
/** Inserts an element at the rear of the queue. */
void enqueue(E e);
/** Returns, but does not remove, the first element of the queue. */
E first();
/** Removes and returns the first element of the queue. */
E dequeue();
}
Operations
| Method | Return value | first $\rightarrow$ Q $\rightarrow$ last |
|---|---|---|
| enqueue(5) | – | (5) |
| enqueue(3) | – | (5, 3) |
| size() | 2 | (5, 3) |
| dequeue() | 5 | (3) |
| isEmpty() | false | (3) |
| dequeue() | 3 | () |
| isEmpty() | true | () |
| dequeue() | null | () |
| enqueue(7) | – | (7) |
| enqueue(9) | – | (7, 9) |
| first() | 7 | (7, 9) |
| enqueue(4) | – | (7, 9, 4) |
java.util.Queue Interface
| Our Queue ADT | Interface java.util.Queue | |
|---|---|---|
| throws exceptions | returns special value | |
| enqueue(e) | add(e) | offer(e) |
| dequeue() | remove() | poll() |
| first() | element() | peek() |
| size() | size() | |
| isEmpty() | isEmpty() | |
Queue ADT $\rightarrow$ Array Implementation (0-indexed)
Queue front at index 0 always. Is there a problem?
Queue front at $f$. Is there a problem?
Queue front at $f$ in circular array.
Enqueue
An element will be enqueued at location $availability$.
$availability = (front + n) \bmod N$
Example: If $front = 5$, size $n = 3$, capacity $N = 10$, then $availability = (5 + 3) \bmod 10 = 8$
Dequeue
An element will be dequeued at location $front$.
$front = (front + 1) \bmod N$
Example: If $front = 3$, capacity $N = 10$, then an element will be dequeued at location $front$ and then $front = (3 + 1) \bmod 10 = 4$
public class ArrayQueue implements Queue {
// instance variables
/** Default array capacity. */
public static final int CAPACITY = 1000; // default array capacity
/** Generic array used for storage of queue elements. */
private E[] data; // generic array used for storage
/** Index of the top element of the queue in the array. */
private int f = 0; // index of the front element
/** Current number of elements in the queue. */
private int sz = 0; // current number of elements
// constructors
/** Constructs an empty queue using the default array capacity. */
public ArrayQueue() {this(CAPACITY);} // constructs queue with default capacity
/**
* Constructs and empty queue with the given array capacity.
* @param capacity length of the underlying array
*/
@SuppressWarnings({"unchecked"})
public ArrayQueue(int capacity) { // constructs queue with given capacity
data = (E[]) new Object[capacity]; // safe cast; compiler may give warning
}
// methods
/**
* Returns the number of elements in the queue.
* @return number of elements in the queue
*/
@Override
public int size() { return sz; }
/** Tests whether the queue is empty. */
@Override
public boolean isEmpty() { return (sz == 0); }
/**
* Inserts an element at the rear of the queue.
* This method runs in O(1) time.
* @param e new element to be inserted
* @throws IllegalStateException if the array storing the elements is full
*/
@Override
public void enqueue(E e) throws IllegalStateException {
if (sz == data.length) throw new IllegalStateException("Queue is full");
int avail = (f + sz) % data.length; // use modular arithmetic
data[avail] = e;
sz++;
}
/**
* Returns, but does not remove, the first element of the queue.
* @return the first element of the queue (or null if empty)
*/
@Override
public E first() {
if (isEmpty()) return null;
return data[f];
}
/**
* Removes and returns the first element of the queue.
* @return element removed (or null if empty)
*/
@Override
public E dequeue() {
if (isEmpty()) return null;
E answer = data[f];
data[f] = null; // dereference to help garbage collection
f = (f + 1) % data.length;
sz--;
return answer;
}
/**
* Returns a string representation of the queue as a list of elements.
* This method runs in O(n) time, where n is the size of the queue.
* @return textual representation of the queue.
*/
public String toString() {
StringBuilder sb = new StringBuilder("(");
int k = f;
for (int j=0; j < sz; j++) {
if (j > 0)
sb.append(", ");
sb.append(data[k]);
k = (k + 1) % data.length;
}
sb.append(")");
return sb.toString();
}
}
Queue ADT $\rightarrow$ SLL Implementation
/** Realization of a FIFO queue as an adaptation of a SinglyLinkedList. */
public class LinkedQueue implements Queue {
private SinglyLinkedList list = new SinglyLinkedList<>(); // an empty list
public LinkedQueue() { } // new queue relies on the initially empty list
public int size() { return list.size(); }
public boolean isEmpty() { return list.isEmpty(); }
public void enqueue(E element) { list.addLast(element); }
public E first() { return list.first(); }
public E dequeue() { return list.removeFirst(); }
}
Circular Queue ADT $\rightarrow$ CLL Implementation
public interface CircularQueue extends Queue {
/** Rotates the front element of the queue to the back of the queue.
This does nothing if the queue is empty. */
void rotate();
}
- Circular queues are useful for multiplayer, turn-based games, or round-robin scheduling of computing processes.
- LinkedCircularQueue class = CircularQueue interface + CircularlyLinkedList class.
Deques (Double-Ended Queues)
- A double-ended queue or deque is a double-ended linear data structure that is more general than stack and queue.
- A deque has four major operations:
addfirst, addlast, removefirst, and removelast.
Deque ADT
| Method | Functionality |
|---|---|
| addFirst(e) | Insert a new element e at the front of the deque. |
| addLast(e) | Insert a new element e at the back of the deque. |
| removeFirst() | Remove and return the first element of the deque (or null if the deque is empty). |
| removeLast() | Remove and return the last element of the deque (or null if the deque is empty). |
| first() | Returns the first element of the deque without removing (or null if the deque is empty). |
| last() | Returns the last element of the deque without removing (or null if the deque is empty). |
| size() | Returns the number of elements in the deque. |
| isEmpty() | Returns a boolean indicating whether the deque is empty. |
Deque ADT Interface
public interface Deque {
/** Returns the number of elements in the deque. */
int size();
/** Tests whether the deque is empty. */
boolean isEmpty();
/** Returns (but does not remove) the first element of the deque. */
E first();
/** Returns (but does not remove) the last element of the deque. */
E last();
/** Inserts an element at the front of the deque. */
void addFirst(E e);
/** Inserts an element at the back of the deque. */
void addLast(E e);
/** Removes and returns the first element of the deque. */
E removeFirst();
/** Removes and returns the last element of the deque. */
E removeLast();
}
Operations
| Method | Return value | Deque |
|---|---|---|
| addLast(5) | – | (5) |
| addFirst(3) | – | (3, 5) |
| addFirst(7) | – | (7, 3, 5) |
| first() | 7 | (7, 3, 5) |
| removeLast() | 5 | (7, 3) |
| size() | 2 | (7, 3) |
| removeLast() | 3 | (7) |
| removeFirst() | 7 | () |
| addFirst(6) | – | (6) |
| last() | 6 | (6) |
| addFirst(8) | – | (8, 6) |
| isEmpty() | false | (8, 6) |
| last() | 6 | (8, 6) |
java.util.Deque Interface
| Our Deque ADT | Interface java.util.Deque | |
|---|---|---|
| throws exceptions | returns special value | |
| first() | getFirst() | peekFirst() |
| last() | getLast() | peekLast() |
| addFirst(e) | addFirst(e) | offerFirst(e) |
| addLast(e) | addLast(e) | offerLast(e) |
| removeFirst() | removeFirst() | pollFirst() |
| removeLast() | removeLast() | pollLast() |
| size() | size() | |
| isEmpty() | isEmpty() | |
Deque ADT $\rightarrow$ Array Implementation
Use circular dynamic array.removeFirst
Element is removed at $front$.
Then $front = (front + 1) \bmod N$.
removeLast
Element is removed at $(front + n - 1) \bmod N$.
No change to $front$.
addLast
Element is added at $(front + n) \bmod N$.
No change to $front$.
addFirst
Element is added at $(front - 1 + N) \bmod N$.
No change to $front$.
Why don't we simply add element at $(front - 1) \bmod N$? Mathematically this is perfect. However, in Java, when $front = 0$, we get $(front - 1) \bmod N = -1 \bmod N = -1$. Therefore, to avoid negative integers, we add $N$ before taking mod.
Deque ADT $\rightarrow$ DLL Implementation
public class LinkedDeque implements Deque