Card 05/ 09
Stack and Queue in Python, Java and TypeScript
The built-ins to use for each, and the one-line mistakes to avoid.
Each of the three languages has a built-in that works as a stack with O(1) operations, Python and Java have one for a queue as well, and TypeScript's queue takes a few lines. This card covers what to use in each language, the same operations run in all three, and what each does when asked to remove from an empty structure.
In Python a list is the stack: append pushes, pop() pops and items[-1] peeks, all at the end of the list. The queue is collections.deque, a double-ended queue that adds and removes at either end in O(1): append enqueues and popleft dequeues. In Java, ArrayDeque is both. push, pop and peek use its front as the top of a stack, and offer, poll and peek make it a queue. A TypeScript array is the stack, with push and pop. For the queue, the class ArrayQueue keeps an array and head, the index of the front item: a dequeue reads the item at head and moves head on by one rather than removing anything, and the array is replaced by an empty one once every item has been read.
Each listing prints the stack from its top and the queue from its front, and the highlighted lines are the ones that add and remove items.
A stack and a queue from each language's built-ins
from collections import deque
def top_first(stack: list[int]) -> str:
return " ".join(str(value) for value in reversed(stack))
def front_first(queue: deque[int]) -> str:
return " ".join(str(value) for value in queue)
stack: list[int] = []
for value in [1, 2, 3]:
stack.append(value)
print(f"stack after push 1, 2, 3: {top_first(stack)} (top first)")
print(f"peek: {stack[-1]}")
print(f"pop: {stack.pop()}, leaving {top_first(stack)}")
queue: deque[int] = deque()
for value in [1, 2, 3]:
queue.append(value)
print(f"queue after enqueue 1, 2, 3: {front_first(queue)} (front first)")
print(f"peek: {queue[0]}")
print(f"dequeue: {queue.popleft()}, leaving {front_first(queue)}")
empty: list[int] = []
try:
empty.pop()
except IndexError as error:
print(f"pop on an empty list raises IndexError: {error}")stack after push 1, 2, 3: 3 2 1 (top first)
peek: 3
pop: 3, leaving 2 1
queue after enqueue 1, 2, 3: 1 2 3 (front first)
peek: 1
dequeue: 1, leaving 2 3
pop on an empty list raises IndexError: pop from empty listimport java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
import java.util.StringJoiner;
public class StacksAndQueues {
static String inOrder(Deque<Integer> items) {
StringJoiner joined = new StringJoiner(" ");
for (int value : items) {
joined.add(String.valueOf(value));
}
return joined.toString();
}
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
for (int value : new int[] {1, 2, 3}) {
stack.push(value);
}
System.out.println("stack after push 1, 2, 3: " + inOrder(stack) + " (top first)");
System.out.println("peek: " + stack.peek());
System.out.println("pop: " + stack.pop() + ", leaving " + inOrder(stack));
Deque<Integer> queue = new ArrayDeque<>();
for (int value : new int[] {1, 2, 3}) {
queue.offer(value);
}
System.out.println("queue after enqueue 1, 2, 3: " + inOrder(queue) + " (front first)");
System.out.println("peek: " + queue.peek());
System.out.println("dequeue: " + queue.poll() + ", leaving " + inOrder(queue));
Deque<Integer> empty = new ArrayDeque<>();
System.out.println("poll on an empty ArrayDeque returns " + empty.poll());
try {
empty.pop();
} catch (NoSuchElementException error) {
System.out.println("pop on an empty ArrayDeque throws NoSuchElementException");
}
}
}stack after push 1, 2, 3: 3 2 1 (top first)
peek: 3
pop: 3, leaving 2 1
queue after enqueue 1, 2, 3: 1 2 3 (front first)
peek: 1
dequeue: 1, leaving 2 3
poll on an empty ArrayDeque returns null
pop on an empty ArrayDeque throws NoSuchElementExceptionclass ArrayQueue<T> {
private items: T[] = [];
private head = 0;
enqueue(value: T): void {
this.items.push(value);
}
dequeue(): T | undefined {
if (this.head === this.items.length) {
return undefined;
}
const value = this.items[this.head];
this.head += 1;
if (this.head === this.items.length) {
this.items = [];
this.head = 0;
}
return value;
}
peek(): T | undefined {
return this.items[this.head];
}
frontFirst(): string {
return this.items.slice(this.head).join(" ");
}
}
function topFirst(stack: number[]): string {
return [...stack].reverse().join(" ");
}
const stack: number[] = [];
for (const value of [1, 2, 3]) {
stack.push(value);
}
console.log(`stack after push 1, 2, 3: ${topFirst(stack)} (top first)`);
console.log(`peek: ${stack[stack.length - 1]}`);
console.log(`pop: ${stack.pop()}, leaving ${topFirst(stack)}`);
const queue = new ArrayQueue<number>();
for (const value of [1, 2, 3]) {
queue.enqueue(value);
}
console.log(`queue after enqueue 1, 2, 3: ${queue.frontFirst()} (front first)`);
console.log(`peek: ${queue.peek()}`);
console.log(`dequeue: ${queue.dequeue()}, leaving ${queue.frontFirst()}`);
const empty: number[] = [];
console.log(`pop on an empty array returns ${empty.pop()}`);
console.log(`dequeue on an empty ArrayQueue returns ${new ArrayQueue<number>().dequeue()}`);stack after push 1, 2, 3: 3 2 1 (top first)
peek: 3
pop: 3, leaving 2 1
queue after enqueue 1, 2, 3: 1 2 3 (front first)
peek: 1
dequeue: 1, leaving 2 3
pop on an empty array returns undefined
dequeue on an empty ArrayQueue returns undefinedRemoving from an empty structure is where the three differ. Python's pop raises IndexError, Java's pop throws NoSuchElementException while poll returns null, and TypeScript's pop returns undefined, as dequeue does here. Java also has an older Stack class, and its documentation recommends a Deque such as ArrayDeque in its place.
The one-line mistake in each language is a dequeue that removes from the front of an array: pop(0) on a Python list, remove(0) on a Java ArrayList and shift() on a TypeScript array. Each returns the right item, and each moves every item behind it to do so.
← → move through sections and cards