Stack Introduction
In this page:
What is a Stack
A stack is a data structure where elements are added and removed from the same end, and the last item put in is always the first one taken out, a rule known as Last In First Out (LIFO).
Example: What is a Stack
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(1); s.push(2); s.push(3);
cout << "last in, first out -- top is " << s.top() << endl;
return 0;
}import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
s.push(1); s.push(2); s.push(3);
System.out.println("last in, first out -- top is " + s.peek());
}
}s = []
s.append(1)
s.append(2)
s.append(3)
print("last in, first out -- top is", s[-1])#include <stdio.h>
int main() {
int s[10], top = -1;
s[++top] = 1; s[++top] = 2; s[++top] = 3;
printf("last in, first out -- top is %d\n", s[top]);
return 0;
}Login to try C/C++/Java code in the editor
LIFO Principle
LIFO behaves exactly like a physical pile of plates: you can only add a plate to the top or take one off the top, never reach into the middle, which is exactly what makes a stack simple and predictable to reason about.
Example: LIFO Principle
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<string> plates;
plates.push("plate1"); plates.push("plate2"); plates.push("plate3");
cout << "take one off the top: " << plates.top() << endl;
plates.pop();
cout << "next one off the top: " << plates.top() << endl;
return 0;
}import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<String> plates = new Stack<>();
plates.push("plate1"); plates.push("plate2"); plates.push("plate3");
System.out.println("take one off the top: " + plates.pop());
System.out.println("next one off the top: " + plates.peek());
}
}plates = ["plate1", "plate2", "plate3"]
print("take one off the top:", plates.pop())
print("next one off the top:", plates[-1])#include <stdio.h>
int main() {
char *plates[3] = {"plate1", "plate2", "plate3"};
int top = 2;
printf("take one off the top: %s\n", plates[top--]);
printf("next one off the top: %s\n", plates[top]);
return 0;
}Login to try C/C++/Java code in the editor
Stack Operations
The core stack operations are push (add to the top), pop (remove from the top), peek (look at the top item without removing it), and a check for whether the stack is currently empty.
Example: Stack Operations
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(10);
s.push(20);
cout << "peek: " << s.top() << endl;
s.pop();
cout << "after pop, empty? " << s.empty() << endl;
return 0;
}import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
s.push(10); s.push(20);
System.out.println("peek: " + s.peek());
s.pop();
System.out.println("after pop, empty? " + s.isEmpty());
}
}s = []
s.append(10)
s.append(20)
print("peek:", s[-1])
s.pop()
print("after pop, empty?", len(s) == 0)#include <stdio.h>
int main() {
int s[10], top = -1;
s[++top] = 10; s[++top] = 20;
printf("peek: %d\n", s[top]);
top--;
printf("after pop, empty? %d\n", top == -1);
return 0;
}Login to try C/C++/Java code in the editor
Stack Applications
Stacks power features you use every day: undo history in an editor, a browser's back button, matching brackets in code, and the function call stack that keeps track of where to return after each function call finishes.
Example: Stack Applications
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<char> undoHistory;
undoHistory.push('A'); undoHistory.push('B'); undoHistory.push('C');
cout << "undo: reverts " << undoHistory.top() << endl;
undoHistory.pop();
cout << "undo again: reverts " << undoHistory.top() << endl;
return 0;
}import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Character> undoHistory = new Stack<>();
undoHistory.push('A'); undoHistory.push('B'); undoHistory.push('C');
System.out.println("undo: reverts " + undoHistory.pop());
System.out.println("undo again: reverts " + undoHistory.peek());
}
}undo_history = ['A', 'B', 'C']
print("undo: reverts", undo_history.pop())
print("undo again: reverts", undo_history[-1])#include <stdio.h>
int main() {
char s[10]; int top = -1;
s[++top] = 'A'; s[++top] = 'B'; s[++top] = 'C';
printf("undo: reverts %c\n", s[top--]);
printf("undo again: reverts %c\n", s[top]);
return 0;
}Login to try C/C++/Java code in the editor
Basic Stack Practice
Small exercises like reversing a sequence using a stack, or predicting the output of a series of push/pop operations, are a fast way to build a solid intuition for how LIFO order actually plays out.
Example: Basic Stack Practice
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
int arr[] = {1, 2, 3, 4};
for (int x : arr) s.push(x);
cout << "reversed: ";
while (!s.empty()) { cout << s.top() << " "; s.pop(); }
return 0;
}import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
int[] arr = {1, 2, 3, 4};
for (int x : arr) s.push(x);
System.out.print("reversed: ");
while (!s.isEmpty()) System.out.print(s.pop() + " ");
}
}s = []
for x in [1, 2, 3, 4]:
s.append(x)
print("reversed:", end=" ")
while s:
print(s.pop(), end=" ")#include <stdio.h>
int main() {
int s[10], top = -1;
int arr[] = {1, 2, 3, 4};
for (int i = 0; i < 4; i++) s[++top] = arr[i];
printf("reversed: ");
while (top >= 0) printf("%d ", s[top--]);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: