Easy difficulty · Algorithm · Topics: stack, design, array, lifo
A stack is a collection that follows LIFO (last in, first out): the most recently added element is the first one removed. This array implementation stores the items in a fixed-size array and keeps a single index, top, that points to the newest element. It supports Push, Pop, Peek, Is Empty and Is Full, all in constant time.
Think of a stack of plates: you add a plate on top and take a plate from the top; the plate at the bottom has to wait. Because every operation touches only one end, we do not need to move any data. We only move the top index.
The invariant: items[0..top] are the stored elements (oldest at index 0), and top === -1 exactly when the stack is empty. The stack is full when top === capacity - 1.
capacity slots and set top = -1.false). Otherwise top++ and store x at items[top].nullitems[top]top--null; otherwise return items[top] without changing top.top === -1.top === capacity - 1.top + 1.Test case 0 uses capacity = 3.
| Operation | top after | items after | Result |
|---|---|---|---|
push(10) | 0 | [10, null, null] | true |
push(20) | 1 | [10, 20, null] | true |
push(30) | 2 | [10, 20, 30] | true |
isFull() | 2 | unchanged | true |
push(40) | 2 | unchanged | false (overflow) |
peek() | 2 | unchanged | 30 |
pop() | 1 | [10, 20, null] | 30 |
size() | 1 | unchanged | 2 |
pop() | 0 | [10, null, null] | 20 |
pop() | -1 | [null, null, null] | 10 |
pop() | -1 | unchanged | null (underflow) |
isEmpty() | -1 | unchanged | true |
| Operation | Time | Why |
|---|---|---|
| Push, Pop, Peek | O(1) | only the slot at top is touched |
| Is Empty, Is Full, Size | O(1) | a comparison on top |
| Space | O(capacity) | the array is allocated up front |
items[top] on an empty stack (top = -1) returns undefined. Check isEmpty() first.top is an index, so the size is top + 1.top.top (const top = this.top) before indexing, so the top chip appears on this.items at the newest element: it lands one cell to the right on a push and on the cell being cleared on a pop. The field this.top itself shows the same number in the object view.null and top decreases; the value is returned from the method.push(40) when full, pop() when empty) change nothing: watch that top stays put.Input
["ArrayStack", "push", "push", "push", "isFull", "push", "peek", "pop", "size", "pop", "pop", "pop", "isEmpty"]
[[3], [10], [20], [30], [], [40], [], [], [], [], [], [], []]
Output
[null, true, true, true, true, false, 30, 30, 2, 20, 10, null, true]
class ArrayStack {
constructor(capacity) {
this.items = new Array(capacity).fill(null); // fixed-size storage
this.top = -1; // index of the top element; -1 means empty
}
// Push: put x on top. Returns false on overflow.
push(x) {
if (this.isFull()) {
return false;
}
this.top++;
const top = this.top;
this.items[top] = x;
return true;
}
// Pop: remove and return the top element, or null on underflow.
pop() {
if (this.isEmpty()) {
return null;
}
const top = this.top;
const value = this.items[top];
this.items[top] = null;
this.top--;
return value;
}
// Peek: read the top element without removing it.
peek() {
if (this.isEmpty()) {
return null;
}
const top = this.top;
return this.items[top];
}
isEmpty() {
return this.top === -1;
}
isFull() {
return this.top === this.items.length - 1;
}
size() {
return this.top + 1;
}
}