Stack

Data Structures

avgO(1)worstO(1)spaceO(n)

15← top

capacity 8

A stack of 2; 15 is on top

1 / 13

Code

class Stack {  private items: number[] = [];  constructor(private capacity = 8) {}  push(value: number) {    if (this.items.length === this.capacity) throw new Error("Stack overflow");    this.items.push(value);  }  pop() {    if (this.items.length === 0) throw new Error("Stack underflow");    return this.items.pop()!;  }  peek() {    return this.items[this.items.length - 1];  }}

structure Stack  items ← empty list  capacity ← 8  procedure push(value)    if size = capacity then error "overflow"    place value on top  end procedure  procedure pop()    if size = 0 then error "underflow"    remove and return the top value  end procedure  procedure peek()    return the top value  end procedureend structure

Variables

size=2capacity=8

Counters

pushes: 0
pops: 0

Starting contents2 values

Operations8 / 40

1. push(23)
2. push(42)
3. pop()
4. push(8)
5. push(16)
6. pop()
7. pop()
8. push(37)

How it works

Last in, first out: push adds on top and pop takes from the top, both in O(1). Undo, expression parsing, depth-first search and the call stack itself all use stacks. This one has a fixed capacity, so it can also overflow and underflow.

Complexity

Best: O(1)
Average: O(1)
Worst: O(1)
Space: O(n)

Stack

How it works

Complexity

Search algorithms