Stack Implementation
In this page:
Array Stack
A stack can be built on top of a plain array by keeping a top index that tracks the position of the most recently pushed element, incrementing it on push and decrementing it on pop.
Example: Array Stack
#include <iostream>
using namespace std;
int main() {
int arr[5]; int top = -1;
arr[++top] = 10; arr[++top] = 20;
cout << "top index=" << top << ", value=" << arr[top] << endl;
top--;
cout << "after pop, top index=" << top << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = new int[5]; int top = -1;
arr[++top] = 10; arr[++top] = 20;
System.out.println("top index=" + top + ", value=" + arr[top]);
top--;
System.out.println("after pop, top index=" + top);
}
}arr = [0] * 5
top = -1
top += 1; arr[top] = 10
top += 1; arr[top] = 20
print("top index=", top, ", value=", arr[top])
top -= 1
print("after pop, top index=", top)#include <stdio.h>
int main() {
int arr[5]; int top = -1;
arr[++top] = 10; arr[++top] = 20;
printf("top index=%d, value=%d\n", top, arr[top]);
top--;
printf("after pop, top index=%d\n", top);
return 0;
}Login to try C/C++/Java code in the editor
Stack Class
Wrapping that array and top index inside a class keeps the internal details private and exposes only clean push, pop, and peek methods, so code using the stack doesn't need to know how it's implemented underneath.
Example: Stack Class
#include <iostream>
using namespace std;
class Stack {
int arr[5]; int top = -1;
public:
void push(int x) { arr[++top] = x; }
int pop() { return arr[top--]; }
int peek() { return arr[top]; }
};
int main() {
Stack s;
s.push(5); s.push(15);
cout << "peek: " << s.peek() << endl;
return 0;
}class Stack {
int[] arr = new int[5]; int top = -1;
void push(int x) { arr[++top] = x; }
int pop() { return arr[top--]; }
int peek() { return arr[top]; }
}
public class Main {
public static void main(String[] args) {
Stack s = new Stack();
s.push(5); s.push(15);
System.out.println("peek: " + s.peek());
}
}class Stack:
def __init__(self):
self.items = []
def push(self, x):
self.items.append(x)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
s = Stack()
s.push(5); s.push(15)
print("peek:", s.peek())#include <stdio.h>
typedef struct { int arr[5]; int top; } Stack;
void push(Stack *s, int x) { s->arr[++s->top] = x; }
int peek(Stack *s) { return s->arr[s->top]; }
int main() {
Stack s = { .top = -1 };
push(&s, 5); push(&s, 15);
printf("peek: %d\n", peek(&s));
return 0;
}Login to try C/C++/Java code in the editor
Overflow and Underflow
An array-backed stack has a fixed capacity, so pushing onto a full stack causes overflow, and popping from an empty one causes underflow. Both need explicit checks to avoid crashing or returning garbage data.
Example: Overflow and Underflow
#include <iostream>
using namespace std;
int main() {
int arr[2]; int top = -1; int capacity = 2;
arr[++top] = 1; arr[++top] = 2;
if (top == capacity - 1) cout << "overflow: stack is full, cannot push" << endl;
top = -1;
if (top == -1) cout << "underflow: stack is empty, cannot pop" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = new int[2]; int top = -1; int capacity = 2;
arr[++top] = 1; arr[++top] = 2;
if (top == capacity - 1) System.out.println("overflow: stack is full, cannot push");
top = -1;
if (top == -1) System.out.println("underflow: stack is empty, cannot pop");
}
}arr = [0, 0]
top = -1
capacity = 2
top += 1; arr[top] = 1
top += 1; arr[top] = 2
if top == capacity - 1:
print("overflow: stack is full, cannot push")
top = -1
if top == -1:
print("underflow: stack is empty, cannot pop")#include <stdio.h>
int main() {
int arr[2]; int top = -1; int capacity = 2;
arr[++top] = 1; arr[++top] = 2;
if (top == capacity - 1) printf("overflow: stack is full, cannot push\n");
top = -1;
if (top == -1) printf("underflow: stack is empty, cannot pop\n");
return 0;
}Login to try C/C++/Java code in the editor
Linked List Stack
A stack can also be built on a linked list instead of an array, pushing and popping at the head, which naturally has no fixed size limit and never overflows, at the cost of a little extra memory per element for the node pointers.
Example: Linked List Stack
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* top = nullptr;
Node* n1 = new Node{1, top}; top = n1;
Node* n2 = new Node{2, top}; top = n2;
cout << "pushed onto head, top=" << top->data << endl;
top = top->next;
cout << "popped from head, new top=" << top->data << endl;
return 0;
}class Node { int data; Node next; Node(int d, Node n) { data = d; next = n; } }
public class Main {
public static void main(String[] args) {
Node top = null;
top = new Node(1, top);
top = new Node(2, top);
System.out.println("pushed onto head, top=" + top.data);
top = top.next;
System.out.println("popped from head, new top=" + top.data);
}
}class Node:
def __init__(self, data, next_node):
self.data = data
self.next = next_node
top = None
top = Node(1, top)
top = Node(2, top)
print("pushed onto head, top=", top.data)
top = top.next
print("popped from head, new top=", top.data)#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *top = NULL;
struct Node *n1 = malloc(sizeof(struct Node)); n1->data = 1; n1->next = top; top = n1;
struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = top; top = n2;
printf("pushed onto head, top=%d\n", top->data);
top = top->next;
printf("popped from head, new top=%d\n", top->data);
return 0;
}Login to try C/C++/Java code in the editor
Implementation Practice
Whether backed by an array or a linked list, both implementations expose identical push/pop/peek behavior; the choice comes down to whether you need a fixed, predictable memory footprint or unbounded, dynamic growth.
Example: Implementation Practice
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> arrayLike;
arrayLike.push(1); arrayLike.push(2);
cout << "same push/pop/peek interface regardless of array or linked-list backing: " << arrayLike.top() << endl;
return 0;
}import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> arrayLike = new Stack<>();
arrayLike.push(1); arrayLike.push(2);
System.out.println("same push/pop/peek interface regardless of backing: " + arrayLike.peek());
}
}array_like = []
array_like.append(1)
array_like.append(2)
print("same push/pop/peek interface regardless of backing:", array_like[-1])#include <stdio.h>
int main() {
int s[10], top = -1;
s[++top] = 1; s[++top] = 2;
printf("same push/pop/peek interface regardless of backing: %d\n", 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: