15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A stack data structure returns values in last-in, first-out order. Only one end, the top, is active. Push adds a value there, pop removes and returns it, and peek reads it without removing. With an array and a top index, every operation is O(1) and the size is top + 1.
| Order | LIFO, last in first out |
|---|---|
| Time for push, pop, peek, isEmpty, size | O(1) each, no loops |
| Empty test | top == -1 |
| Full test before push | top == capacity - 1, otherwise report overflow |
| Size | top + 1 |
| Storage | O(C) for an array of capacity C |
A stack stores values so that the last value added is the first value removed. This is the last-in, first-out rule, or LIFO.
Only one end is active: the top.
For a stack shown as:
1bottom [4, 7] top7 is the top.push(x) adds x at the top.pop() removes and returns the top.peek() returns the top without removing it.isEmpty() tells whether there are no values.size() tells how many values are stored.We will use a fixed-capacity array. The array has indices 0 through capacity - 1.
A variable named top records the index of the current top value:
top = -1 means the stack is empty.top = 0 means one value exists at index 0.top = 1 means two values exist at indices 0 and 1.With this representation, the stack size is always top + 1.
Use a stack with capacity 4.
1Operations:
2push(4), push(7), pop(), push(2), peek()Before any operation:
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cell | _ | _ | _ | _ |
1top = -1
2logical stack = []The left side is the bottom of the stack. The value at top is the next value that pop() would remove.
Start with the first push:
1push(4)The stack is not full. Increment top from -1 to 0, then write 4 at index 0.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cell | 4 | _ | _ | _ |
1top = 0
2logical stack = [4]Push 7:
1push(7)Increment top from 0 to 1, then write 7 at index 1.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cell | 4 | 7 | _ | _ |
1top = 1
2logical stack = [4, 7]
3next pop = 7Use the same operation sequence.
A fixed-capacity array stack: top is the index of the top value and the size is top + 1. push moves top up then writes, pop reads then moves top down, peek only reads. Final stack: [4, 2].
push(4)Start:
1cells = [_, _, _, _]
2top = -1
3stack = []Increment top, then write:
1top becomes 0
2cells[0] becomes 4Result:
1cells = [4, _, _, _]
2top = 0
3stack = [4]push(7)Start:
1cells = [4, _, _, _]
2top = 0
3stack = [4]Increment top, then write:
1top becomes 1
2cells[1] becomes 7Result:
1cells = [4, 7, _, _]
2top = 1
3stack = [4, 7]pop()The top is 1, so index 1 holds the value to remove.
Read the old top value before changing top:
1returned value = cells[1] = 7Then decrement top:
1top becomes 0Result:
1logical stack = [4]
2returned value = 7When unused array positions are displayed as _, the state is:
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cell | 4 | _ | _ | _ |
1top = 0
2stack = [4]The physical array slot may still contain an old value in an implementation that does not clear it. It is no longer part of the logical stack because it lies above top.
push(2)Start:
1cells = [4, _, _, _]
2top = 0
3stack = [4]Increment top, then write:
1top becomes 1
2cells[1] becomes 2Result:
1cells = [4, 2, _, _]
2top = 1
3stack = [4, 2]An old removed value must not remain logically accessible. The second position now holds 2, not the previously popped 7.
peek()The top is 1.
1return cells[1] = 2Do not change top. Do not remove the value.
Result:
1returned value = 2
2cells = [4, 2, _, _]
3top = 1
4stack = [4, 2]Every valid state from the example is:
1top = -1: []
2top = 0: [4]
3top = 1: [4, 7]
4top = 0: [4]
5top = 1: [4, 2]In each case, the stack values occupy consecutive array indices starting at 0.
More precisely:
At every valid state, the logical stack elements occupy array indices
0throughtopin insertion order, and the top element is at indextop;topis-1exactly when the stack is empty.
The statement above is the stack invariant.
For [4, 7]:
1index: 0 1
2value: 4 7
3top = 1The values are in insertion order from index 0 through index 1. The newest value, 7, is exactly at cells[top].
For push(2) after popping 7:
1index: 0 1
2value: 4 2
3top = 1The same rule still holds. 2 was added most recently, so it is at index top.
The invariant gives the operation behavior directly:
A fixed-capacity stack must stay inside its array boundaries.
For an array with capacity C, valid indices are:
10 through C - 1Before adding a value, check whether top is already at the last valid index:
1top == capacity - 1If true, no position remains. Report overflow rather than incrementing and writing beyond the array.
Otherwise:
top.cells[top].The new value is now the top, so it will be the next value returned by pop() or peek().
Before reading, check:
1top == -1If true, the stack has no top value. Report underflow. Do not attempt to read cells[-1].
Otherwise:
cells[top].top.The order matters. Decrementing first would move from index 1 to index 0, causing a stack [4, 7] to return 4 instead of 7.
Use the same empty check as pop().
If the stack is nonempty, return cells[top]. Do not change top or any cell.
The empty condition is:
1top == -1The size is:
1top + 1There is no search through the array.
The stack stores integers in a fixed-capacity array.
1Stack:
2 cells: array of integer
3 capacity: integer
4 top: integercreateStack(capacity) requires capacity >= 0.
All operations below mutate the stack only when their stated successful update occurs.
push reports an overflow error when the stack is full.pop and peek report an underflow error when the stack is empty.11 function createStack(capacity) -> Stack
22 require capacity >= 0
33 stack = new Stack
44 stack.cells = new integer array of length capacity
55 stack.capacity = capacity
66 stack.top = -1
77 return stack11 function isEmpty(stack) -> boolean
22 return stack.top == -111 function size(stack) -> integer
22 return stack.top + 111 function push(stack, value) -> success or overflow error
22 if stack.top == stack.capacity - 1
33 report overflow error
44 return error
55 stack.top = stack.top + 1
66 stack.cells[stack.top] = value
77 return success11 function pop(stack) -> integer or underflow error
22 if stack.top == -1
33 report underflow error
44 return error
55 value = stack.cells[stack.top]
66 stack.top = stack.top - 1
77 return value11 function peek(stack) -> integer or underflow error
22 if stack.top == -1
33 report underflow error
44 return error
55 return stack.cells[stack.top]The cells above top are outside the logical stack. pop does not need to overwrite such a cell for the stack representation to be correct.
Create a capacity-four stack.
1createStack(4)4 >= 0, so continue.4, set top = -1.1cells = [_, _, _, _]
2top = -1push(stack, 4)-1 == 4 - 1. This is false.top = -1 + 1 = 0.cells[0] = 4.1cells = [4, _, _, _]
2top = 0
3stack = [4]push(stack, 7)0 == 4 - 1. This is false.top = 0 + 1 = 1.cells[1] = 7.1cells = [4, 7, _, _]
2top = 1
3stack = [4, 7]pop(stack)top == -1. Here, 1 == -1 is false.value = cells[1] = 7.top = 1 - 1 = 0.7.1returned = 7
2top = 0
3logical stack = [4]Displayed with unused positions as _:
1cells = [4, _, _, _]push(stack, 2)0 == 4 - 1. This is false.top = 0 + 1 = 1.cells[1] = 2.1cells = [4, 2, _, _]
2top = 1
3stack = [4, 2]peek(stack)top == -1. Here, 1 == -1 is false.cells[1], which is 2.The stack state remains unchanged:
1returned = 2
2cells = [4, 2, _, _]
3top = 1
4stack = [4, 2]The representation is correct when the invariant holds:
The logical stack occupies indices
0throughtopin insertion order, its newest value is at indextop, andtop = -1exactly for an empty stack.
createStack sets top to -1.
There are no indices from 0 through top, so the logical stack is empty. The invariant holds.
pushAssume the invariant holds before push.
If top == capacity - 1, the logical stack already uses the last valid array index. The operation reports overflow and does not change the stack, so the invariant remains true.
Otherwise, top < capacity - 1. Incrementing top produces a valid next array index. Writing the new value there extends the occupied range from 0..oldTop to 0..oldTop + 1.
The old elements remain in insertion order. The new value is at the new top, so it is the newest element and will be returned next by pop or peek.
popAssume the invariant holds and the stack is nonempty.
Nonempty means top != -1, so cells[top] is a valid occupied array position. By the invariant, it contains the most recently pushed value not already popped.
pop reads that value before decrementing top. After decrementing, the logical occupied range loses exactly the old top index. The remaining values are still at indices 0 through the new top in their original insertion order.
pop returns the required most recent value and reduces the size by one.
If the stack is empty, top == -1. The operation reports underflow before any array access, so it cannot read cells[-1].
peekAssume the invariant holds and the stack is nonempty.
The value at cells[top] is the current top value. peek returns it without changing top or an array cell. The stack state remains unchanged.
If the stack is empty, peek reports underflow before any array access.
Each operation contains a fixed sequence of checks, reads, writes, and index updates. There is no loop or recursion. Every call reaches either its error return or its successful return after those finite steps.
Count the operations performed by each method.
pushA successful push performs:
top.The method performs a constant number of operations, so push takes O(1) time.
popA successful pop performs:
top.The method performs a constant number of operations, so pop takes O(1) time.
peek, isEmpty, and sizepeek performs one empty check and one array read.isEmpty checks one field.size reads top and adds 1.Each examines a constant number of fields, so each takes O(1) time.
A stack with capacity C stores one array of C cells plus a constant number of fields, including capacity and top.
Therefore, the container uses O(C) storage.
Each individual operation uses only a constant number of temporary variables, such as value in pop, so each operation uses O(1) extra temporary space.
0Incorrect assumption
1pop removes cells[0]Smallest exposing input
1push(4), push(7), pop()Correct state before pop:
1cells = [4, 7, _, _]
2top = 1Wrong result
The operation returns 4.
Why it is wrong
4 was pushed first. The LIFO rule requires the most recent value, 7, to leave first.
Correction
Read and return:
1cells[top]For this state, cells[1] is 7.
Incorrect lines
1stack.top = stack.top - 1
2value = stack.cells[stack.top]Smallest exposing input
1stack = [4, 7]
2top = 1Wrong state and result
After decrementing, top becomes 0. The read returns cells[0], which is 4.
Correction
Read the old top first:
1value = stack.cells[stack.top]
2stack.top = stack.top - 1The code returns 7, then changes top to 0.
top == 0 as emptyIncorrect empty test
1if stack.top == 0Smallest exposing input
1push(4)State:
1cells = [4, _, _, _]
2top = 0Wrong result
The stack is treated as empty, so pop() or peek() incorrectly reports underflow.
Correction
Because initialization uses top = -1, the only empty condition is:
1stack.top == -1Incorrect approach
1stack.top = stack.top + 1
2stack.cells[stack.top] = valuewith no rejection when the old top already equals capacity - 1.
Smallest exposing input
1capacity = 2
2push(1), push(2), push(3)Before push(3):
1cells = [1, 2]
2top = 1
3capacity = 2Wrong state
Incrementing first makes top = 2, but index 2 lies beyond the last valid index, which is 1. Writing cells[2] is out of bounds.
Correction
Check before incrementing:
1if stack.top == stack.capacity - 1
2 report overflow error| Operation sequence | Required behavior |
|---|---|
pop() on [] | Report empty-stack underflow or return the documented failure value. Never read array[-1]. |
peek() on [] | Report empty-stack underflow or use the documented failure behavior. |
push(9) into capacity 0 | Report full-stack overflow. |
push(1), pop(), push(2) | The final logical stack is [2], not [1]. |
Capacity 4: push(1), push(2), push(3), push(4) | All four pushes succeed. |
Capacity 4: then push(5) | Report overflow. Do not write beyond index 3. |
Implement a fixed-capacity integer stack whose push, pop, peek, isEmpty, and size operations pass tests for:
pop and peek.push.Your implementation contract should use:
top = -1 for an empty stack.0 through capacity - 1.top == capacity - 1.pop or peek is attempted while top == -1.pop that reads cells[top] before decrementing top.1class ArrayStack:
2 def __init__(self, capacity):
3 self.cells = [0] * capacity
4 self.capacity = capacity
5 self.top = -1 # -1 means empty
6
7 def push(self, value):
8 if self.top == self.capacity - 1: # check before incrementing
9 return False
10 self.top += 1
11 self.cells[self.top] = value
12 return True
13
14 def pop(self):
15 if self.top == -1:
16 raise IndexError("underflow")
17 value = self.cells[self.top] # read before decrementing
18 self.top -= 1
19 return value
20
21 def peek(self):
22 if self.top == -1:
23 raise IndexError("underflow")
24 return self.cells[self.top]
25
26 def size(self):
27 return self.top + 1
28
29s = ArrayStack(4)
30s.push(4)
31s.push(7)
32print("pop:", s.pop())
33s.push(2)
34print("peek:", s.peek())
35print("stack:", s.cells[:s.size()])
36print("size:", s.size())
37s.push(1)
38s.push(3)
39print("push(5) on full stack:", "ok" if s.push(5) else "overflow")1import java.util.Arrays;
2
3public class Main {
4 static class ArrayStack {
5 int[] cells;
6 int capacity;
7 int top = -1; // -1 means empty
8
9 ArrayStack(int capacity) {
10 this.cells = new int[capacity];
11 this.capacity = capacity;
12 }
13
14 boolean push(int value) {
15 if (top == capacity - 1) return false; // check before incrementing
16 top++;
17 cells[top] = value;
18 return true;
19 }
20
21 int pop() {
22 if (top == -1) throw new IllegalStateException("underflow");
23 int value = cells[top]; // read before decrementing
24 top--;
25 return value;
26 }
27
28 int peek() {
29 if (top == -1) throw new IllegalStateException("underflow");
30 return cells[top];
31 }
32
33 int size() {
34 return top + 1;
35 }
36 }
37
38 public static void main(String[] args) {
39 ArrayStack s = new ArrayStack(4);
40 s.push(4);
41 s.push(7);
42 System.out.println("pop: " + s.pop());
43 s.push(2);
44 System.out.println("peek: " + s.peek());
45 System.out.println("stack: " + Arrays.toString(Arrays.copyOf(s.cells, s.size())));
46 System.out.println("size: " + s.size());
47 s.push(1);
48 s.push(3);
49 System.out.println("push(5) on full stack: " + (s.push(5) ? "ok" : "overflow"));
50 }
51}1#include <iostream>
2#include <stdexcept>
3#include <vector>
4using namespace std;
5
6struct ArrayStack {
7 vector<int> cells;
8 int capacity;
9 int top = -1; // -1 means empty
10
11 ArrayStack(int c) : cells(c), capacity(c) {}
12
13 bool push(int value) {
14 if (top == capacity - 1) return false; // check before incrementing
15 cells[++top] = value;
16 return true;
17 }
18
19 int pop() {
20 if (top == -1) throw runtime_error("underflow");
21 int value = cells[top]; // read before decrementing
22 top--;
23 return value;
24 }
25
26 int peek() {
27 if (top == -1) throw runtime_error("underflow");
28 return cells[top];
29 }
30
31 int size() { return top + 1; }
32};
33
34int main() {
35 ArrayStack s(4);
36 s.push(4);
37 s.push(7);
38 cout << "pop: " << s.pop() << endl;
39 s.push(2);
40 cout << "peek: " << s.peek() << endl;
41 cout << "stack: [";
42 for (int i = 0; i < s.size(); i++) cout << (i ? ", " : "") << s.cells[i];
43 cout << "]" << endl;
44 cout << "size: " << s.size() << endl;
45 s.push(1);
46 s.push(3);
47 cout << "push(5) on full stack: " << (s.push(5) ? "ok" : "overflow") << endl;
48}1class ArrayStack {
2 constructor(capacity) {
3 this.cells = new Array(capacity).fill(0);
4 this.capacity = capacity;
5 this.top = -1; // -1 means empty
6 }
7
8 push(value) {
9 if (this.top === this.capacity - 1) return false; // check before incrementing
10 this.top++;
11 this.cells[this.top] = value;
12 return true;
13 }
14
15 pop() {
16 if (this.top === -1) throw new Error('underflow');
17 const value = this.cells[this.top]; // read before decrementing
18 this.top--;
19 return value;
20 }
21
22 peek() {
23 if (this.top === -1) throw new Error('underflow');
24 return this.cells[this.top];
25 }
26
27 size() {
28 return this.top + 1;
29 }
30}
31
32const s = new ArrayStack(4);
33s.push(4);
34s.push(7);
35console.log('pop:', s.pop());
36s.push(2);
37console.log('peek:', s.peek());
38console.log(`stack: [${s.cells.slice(0, s.size()).join(', ')}]`);
39console.log('size:', s.size());
40s.push(1);
41s.push(3);
42console.log('push(5) on full stack:', s.push(5) ? 'ok' : 'overflow');Keep an array of capacity C and an index top that starts at -1. Push checks top == C - 1, increments top and writes at cells[top]. Pop reads cells[top] first, then decrements top.
Pop returns the top value and removes it by lowering top. Peek returns the same value and leaves top and every cell unchanged. On [4, 2], both return 2, but only pop leaves [4].
Overflow is a push when top == capacity - 1, so no cell is left. Underflow is a pop or peek when top == -1, so there is no top value. Check both before touching the array, or you read cells[-1] or write past the end.
Use one when the most recent item must be handled first. Undo history and the call stack work this way, and so do bracket matching and the operator stack in infix to postfix conversion.
By storage there are two: array-based stacks, fixed size or resizable, and linked-list stacks that push and pop at the head node. All of them keep the same LIFO contract. This page uses the fixed-capacity array.