Stack Data Structure Code Implementations
Production-ready Stack Data Structure data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.
Study Stack Data Structure Guide ยท Launch Visualizer
CPP Implementation
#include <iostream>
#include <stdexcept>
using namespace std;
template <typename T>
class Stack {
private:
struct Node {
T data;
Node* next;
Node(T value) : data(value), next(nullptr) {}
};
Node* top;
int size;
public:
Stack() : top(nullptr), size(0) {}
~Stack() {
clear();
}
// Copy constructor
Stack(const Stack& other) : top(nullptr), size(0) {
if (other.top) {
// Use a temporary stack to maintain order
Stack<T> temp;
Node* current = other.top;
while (current) {
temp.push(current->data);
current = current->next;
}
// Now push from temp to maintain original order
while (!temp.empty()) {
push(temp.peek());
temp.pop();
}
}
}
void push(T value) {
Node* newNode = new Node(value);
newNode->next = top;
top = newNode;
size++;
}
void pop() {
if (empty()) {
throw runtime_error("Stack is empty");
}
Node* temp = top;
top = top->next;
delete temp;
size--;
}
T peek() const {
if (empty()) {
throw runtime_error("Stack is empty");
}
return top->data;
}
bool empty() const {
return top == nullptr;
}
int length() const {
return size;
}
void clear() {
while (!empty()) {
pop();
}
}
void display() const {
if (empty()) {
cout << "Stack: []" << endl;
return;
}
cout << "Stack: [";
Node* current = top;
while (current) {
cout << current->data;
if (current->next) cout << ", ";
current = current->next;
}
cout << "] <- top" << endl;
}
};
/// array based
#include <iostream>
#include <stdexcept>
using namespace std;
template <typename T>
class ArrayStack {
private:
T* arr;
int capacity;
int top;
void resize() {
capacity *= 2;
T* newArr = new T[capacity];
for (int i = 0; i <= top; i++) {
newArr[i] = arr[i];
}
delete[] arr;
arr = newArr;
}
public:
ArrayStack(int initialCapacity = 10)
: capacity(initialCapacity), top(-1) {
arr = new T[capacity];
}
~ArrayStack() {
delete[] arr;
}
void push(T value) {
if (top == capacity - 1) {
resize();
}
arr[++top] = value;
}
void pop() {
if (empty()) {
throw runtime_error("Stack is empty");
}
top--;
}
T peek() const {
if (empty()) {
throw runtime_error("Stack is empty");
}
return arr[top];
}
bool empty() const {
return top == -1;
}
int size() const {
return top + 1;
}
void clear() {
top = -1;
}
};JAVA Implementation
import java.util.EmptyStackException;
public class Stack<T> {
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
this.next = null;
}
}
private Node top;
private int size;
public Stack() {
top = null;
size = 0;
}
public void push(T data) {
Node newNode = new Node(data);
newNode.next = top;
top = newNode;
size++;
}
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
T data = top.data;
top = top.next;
size--;
return data;
}
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
return size;
}
public void clear() {
top = null;
size = 0;
}
public boolean contains(T data) {
Node current = top;
while (current != null) {
if (current.data.equals(data)) {
return true;
}
current = current.next;
}
return false;
}
@Override
public String toString() {
if (isEmpty()) {
return "Stack: []";
}
StringBuilder sb = new StringBuilder();
sb.append("Stack: [");
Node current = top;
while (current != null) {
sb.append(current.data);
if (current.next != null) {
sb.append(", ");
}
current = current.next;
}
sb.append("] <- top");
return sb.toString();
}
}
// array based
import java.util.Arrays;
import java.util.EmptyStackException;
public class ArrayStack<T> {
private Object[] arr;
private int top;
private int capacity;
public ArrayStack() {
this(10);
}
public ArrayStack(int initialCapacity) {
this.capacity = initialCapacity;
this.arr = new Object[capacity];
this.top = -1;
}
public void push(T data) {
if (top == capacity - 1) {
resize();
}
arr[++top] = data;
}
@SuppressWarnings("unchecked")
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
T data = (T) arr[top];
arr[top--] = null; // Help GC
return data;
}
@SuppressWarnings("unchecked")
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return (T) arr[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
public void clear() {
Arrays.fill(arr, 0, top + 1, null);
top = -1;
}
private void resize() {
capacity *= 2;
arr = Arrays.copyOf(arr, capacity);
}
}JAVASCRIPT Implementation
class Stack {
constructor() {
this.items = [];
}
// Add element to top of stack
push(element) {
this.items.push(element);
}
// Remove and return top element
pop() {
if (this.isEmpty()) {
throw new Error("Stack is empty");
}
return this.items.pop();
}
// Return top element without removing
peek() {
if (this.isEmpty()) {
throw new Error("Stack is empty");
}
return this.items[this.items.length - 1];
}
// Check if stack is empty
isEmpty() {
return this.items.length === 0;
}
// Get stack size
size() {
return this.items.length;
}
// Clear the stack
clear() {
this.items = [];
}
// Check if stack contains element
contains(element) {
return this.items.includes(element);
}
// Convert to array (top to bottom)
toArray() {
return [...this.items].reverse();
}
// String representation
toString() {
if (this.isEmpty()) {
return "Stack: []";
}
return `Stack: [${this.items.slice().reverse().join(', ')}] <- top`;
}
}
/// linked list
class LinkedStack {
constructor() {
this.top = null;
this.count = 0;
}
push(data) {
const newNode = {
data: data,
next: this.top
};
this.top = newNode;
this.count++;
}
pop() {
if (this.isEmpty()) {
throw new Error("Stack is empty");
}
const data = this.top.data;
this.top = this.top.next;
this.count--;
return data;
}
peek() {
if (this.isEmpty()) {
throw new Error("Stack is empty");
}
return this.top.data;
}
isEmpty() {
return this.top === null;
}
size() {
return this.count;
}
clear() {
this.top = null;
this.count = 0;
}
contains(data) {
let current = this.top;
while (current) {
if (current.data === data) {
return true;
}
current = current.next;
}
return false;
}
toArray() {
const result = [];
let current = this.top;
while (current) {
result.push(current.data);
current = current.next;
}
return result;
}
toString() {
if (this.isEmpty()) {
return "Stack: []";
}
const elements = this.toArray();
return `Stack: [${elements.join(', ')}] <- top`;
}
}PYTHON Implementation
class Stack:
def __init__(self):
self.items = []
def push(self, item):
"""Add element to top of stack"""
self.items.append(item)
def pop(self):
"""Remove and return top element"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
"""Return top element without removing"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.items[-1]
def is_empty(self):
"""Check if stack is empty"""
return len(self.items) == 0
def size(self):
"""Get stack size"""
return len(self.items)
def clear(self):
"""Clear the stack"""
self.items.clear()
def contains(self, item):
"""Check if stack contains item"""
return item in self.items
def to_list(self):
"""Convert to list (top to bottom)"""
return self.items[::-1]
def __len__(self):
"""Support len() function"""
return len(self.items)
def __bool__(self):
"""Support bool() function"""
return not self.is_empty()
def __str__(self):
"""String representation"""
if self.is_empty():
return "Stack: []"
return f"Stack: [{', '.join(map(str, reversed(self.items)))}] <- top"
def __repr__(self):
return f"Stack({self.items})"
def __iter__(self):
"""Make the stack iterable (top to bottom)"""
for item in reversed(self.items):
yield item
## linked list
class LinkedStack:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __init__(self):
self.top = None
self.count = 0
def push(self, data):
"""Add element to top of stack"""
new_node = self.Node(data)
new_node.next = self.top
self.top = new_node
self.count += 1
def pop(self):
"""Remove and return top element"""
if self.is_empty():
raise IndexError("Stack is empty")
data = self.top.data
self.top = self.top.next
self.count -= 1
return data
def peek(self):
"""Return top element without removing"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.top.data
def is_empty(self):
"""Check if stack is empty"""
return self.top is None
def size(self):
"""Get stack size"""
return self.count
def clear(self):
"""Clear the stack"""
self.top = None
self.count = 0
def contains(self, data):
"""Check if stack contains data"""
current = self.top
while current:
if current.data == data:
return True
current = current.next
return False
def to_list(self):
"""Convert to list (top to bottom)"""
result = []
current = self.top
while current:
result.append(current.data)
current = current.next
return result
def __len__(self):
return self.count
def __bool__(self):
return not self.is_empty()
def __str__(self):
if self.is_empty():
return "Stack: []"
elements = self.to_list()
return f"Stack: [{', '.join(map(str, elements))}] <- top"
def __iter__(self):
"""Make the stack iterable (top to bottom)"""
current = self.top
while current:
yield current.data
current = current.next