Stack
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The last element added to the stack is the first one to be removed. Think of it like a stack of plates: you can only add or remove a plate from the top of the pile. Stacks are fundamental to many algorithms and are used in function call management, expression evaluation, undo mechanisms, and backtracking algorithms.
How Stack Works
A stack operates on the LIFO (Last In, First Out) principle. It supports a small set of operations, all of which happen at the top of the stack. You never access or modify elements in the middle or bottom directly.
Core operations:
- Push: Add an element to the top of the stack. The new element becomes the topmost item. This operation takes O(1) time because we only modify the top pointer.
- Pop: Remove and return the element from the top of the stack. The element below it becomes the new top. If the stack is empty, this results in a stack underflow error. This operation is O(1).
- Peek (or Top): Return the top element without removing it. This lets you inspect the top of the stack without modifying its contents. O(1) time.
- isEmpty: Check whether the stack has any elements. Returns true if the stack is empty, false otherwise. O(1) time.
Real-world analogies:
- Stack of plates: You always take the top plate off and add new plates on top.
- Undo in a text editor: Each action is pushed onto a stack. When you press undo, the most recent action is popped off and reversed.
- Browser back button: Each page you visit is pushed onto a history stack. Clicking "Back" pops the most recent page.
- Function call stack: When a program calls a function, it pushes a stack frame. When the function returns, the frame is popped.
Stacks can be implemented using arrays or linked lists. Array-based stacks are simple and cache-friendly, while linked-list-based stacks never have a capacity limit (beyond available memory). Both provide O(1) push, pop, and peek operations.
Interactive Visualization
Experiment with the stack below. Enter a value and click Push to add it to the top, or click Pop to remove the top element. Peek highlights the top element without removing it. Use the playback controls to step through each operation.
Code Implementation
Below is a complete stack implementation using an array (or list) in three languages. The implementation includes push, pop, peek, isEmpty, and size operations with proper error handling for underflow conditions.
class Stack:
def __init__(self):
"""Initialize an empty stack."""
self.items = []
def push(self, value):
"""Push a value onto the top of the stack. O(1)"""
self.items.append(value)
def pop(self):
"""Remove and return the top element. O(1)"""
if self.is_empty():
raise IndexError("Stack underflow: cannot pop from empty stack")
return self.items.pop()
def peek(self):
"""Return the top element without removing it. O(1)"""
if self.is_empty():
raise IndexError("Stack underflow: cannot peek empty stack")
return self.items[-1]
def is_empty(self):
"""Check if the stack is empty. O(1)"""
return len(self.items) == 0
def size(self):
"""Return the number of elements. O(1)"""
return len(self.items)
def __str__(self):
"""String representation (top is rightmost)."""
return "Stack: " + str(self.items)
# Example usage
s = Stack()
s.push(10)
s.push(25)
s.push(8)
s.push(42)
print(s) # Stack: [10, 25, 8, 42]
print(s.peek()) # 42
print(s.pop()) # 42
print(s.pop()) # 8
print(s) # Stack: [10, 25]
print(s.is_empty()) # False
print(s.size()) # 2
import java.util.ArrayList;
public class Stack {
private ArrayList<Integer> items;
public Stack() {
items = new ArrayList<>();
}
/** Push a value onto the top of the stack. O(1) amortized */
public void push(int value) {
items.add(value);
}
/** Remove and return the top element. O(1) */
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Stack underflow: cannot pop from empty stack");
}
return items.remove(items.size() - 1);
}
/** Return the top element without removing it. O(1) */
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack underflow: cannot peek empty stack");
}
return items.get(items.size() - 1);
}
/** Check if the stack is empty. O(1) */
public boolean isEmpty() {
return items.size() == 0;
}
/** Return the number of elements. O(1) */
public int size() {
return items.size();
}
@Override
public String toString() {
return "Stack: " + items.toString();
}
public static void main(String[] args) {
Stack s = new Stack();
s.push(10);
s.push(25);
s.push(8);
s.push(42);
System.out.println(s); // Stack: [10, 25, 8, 42]
System.out.println(s.peek()); // 42
System.out.println(s.pop()); // 42
System.out.println(s.pop()); // 8
System.out.println(s); // Stack: [10, 25]
System.out.println(s.isEmpty()); // false
System.out.println(s.size()); // 2
}
}
#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;
class Stack {
private:
vector<int> items;
public:
// Push a value onto the top of the stack. O(1) amortized
void push(int value) {
items.push_back(value);
}
// Remove and return the top element. O(1)
int pop() {
if (isEmpty()) {
throw runtime_error("Stack underflow: cannot pop from empty stack");
}
int top = items.back();
items.pop_back();
return top;
}
// Return the top element without removing it. O(1)
int peek() const {
if (isEmpty()) {
throw runtime_error("Stack underflow: cannot peek empty stack");
}
return items.back();
}
// Check if the stack is empty. O(1)
bool isEmpty() const {
return items.empty();
}
// Return the number of elements. O(1)
int size() const {
return items.size();
}
// Print the stack contents
void print() const {
cout << "Stack: [";
for (int i = 0; i < items.size(); i++) {
cout << items[i];
if (i < items.size() - 1) cout << ", ";
}
cout << "]" << endl;
}
};
int main() {
Stack s;
s.push(10);
s.push(25);
s.push(8);
s.push(42);
s.print(); // Stack: [10, 25, 8, 42]
cout << "Peek: " << s.peek() << endl; // 42
cout << "Pop: " << s.pop() << endl; // 42
cout << "Pop: " << s.pop() << endl; // 8
s.print(); // Stack: [10, 25]
cout << "Empty: " << s.isEmpty() << endl; // 0 (false)
cout << "Size: " << s.size() << endl; // 2
return 0;
}
Complexity Analysis
All primary stack operations operate on the top element only, making them constant time. Searching for an element requires scanning through the stack, which takes linear time.
| Operation | Time Complexity | Notes |
|---|---|---|
| Push | O(1) | Add element to top; only the top pointer is updated |
| Pop | O(1) | Remove element from top; only the top pointer is updated |
| Peek | O(1) | Read the top element without modification |
| Search | O(n) | Must scan from top to bottom to find an element |
| Space | O(n) | Proportional to the number of elements stored |
Quiz
Test your understanding of stacks with these questions.
Q1. Which principle does a stack follow?
Q2. What is the time complexity of the push operation on a stack?
Q3. If you push the elements 5, 10, 15, 20 onto an empty stack (in that order) and then pop twice, what is the top element?
Q4. What happens when you try to pop from an empty stack?
Q5. Which of the following is NOT a common application of stacks?