Stacks
A Stack is a linear data structure that operates on the LIFO (Last In, First Out) principle. This means the last element added to the stack is the first one to be removed. 
The Mechanics: How a Stack Works
A Stack is strictly governed by LIFO (Last In, First Out). All action happens at exactly one endpoint, called the Top.
- Push: Dropping an item onto the top of the stack.
- Pop: Taking the top item off the stack.
- Peek / Top: Looking at the top item without removing it.
- Stack Overflow: An error that occurs when you try to Push an item onto a stack that has reached its maximum memory capacity.
- Stack Underflow: An error that occurs when you try to Pop an item from an empty stack.
Real-Life Examples
- A Can of Pringles: You can only eat the chip at the very top. To reach the bottom chip, you have to eat (pop) all the ones above it.
- An Elevator: The last person to squeeze into a crowded elevator is standing right in front of the doors, making them the first person to step out.
- A Stack of Books: If you pull a book from the bottom without removing the top ones first, the whole pile collapses.
Technical & Software Applications
Stacks are fundamental to how computers and software operate under the hood:
- Function Call Stack (Recursion): When a computer runs a program, it uses a stack to keep track of active functions. If Function A calls Function B, A is put on hold (pushed to the stack). When B finishes, A is popped off the stack and resumes.
- Undo Mechanisms: Every time you type a word in a text editor, that action is Pushed to a stack. When you hit Ctrl+Z (Undo), the editor Pops your most recent action off the stack and reverses it.
- Compiler Syntax Checking: Compilers use stacks to check for Balanced Parentheses (e.g., making sure every { has a matching }).
- Browser Back Button: As you click links, your current page is pushed onto the “Back” stack. Clicking the Back button pops the most recent page off the stack and loads it.
Implementation Methods
Stacks can be built in memory using two primary methods:
- Using Arrays: Pros: Extremely fast and easy to implement.
- Cons: Fixed size. You must define the maximum capacity upfront, which can lead to a Stack Overflow if you run out of space, or wasted memory if you allocate too much.
- Using Linked Lists:
- Pros: Dynamic size. The stack can grow and shrink infinitely as long as your computer has memory available.
- Cons: Slightly slower and uses extra memory because each element must also store a pointer to the next element.
Time and Space Complexity
- Time Complexity: O(1) (Constant Time). Because you are only ever interacting with the very top element, pushing, popping, and peeking take the exact same amount of time regardless of whether the stack has 10 items or 10 million items.
- Space Complexity: O(n). The memory required scales linearly with the number of elements (n) in the stack.
Code Implementation (Array-Based)
Here is a robust implementation of a Stack using an array in Java .
JavaPythonCC++
class Stack {
private int maxSize;
private int[] stackArray;
private int top;
// Constructor to initialize stack
public Stack(int size) {
this.maxSize = size;
this.stackArray = new int[maxSize];
this.top = -1; // Indicates empty stack
}
// Push operation: Add element to top
public void push(int value) {
if (isFull()) {
System.out.println("Stack Overflow! Cannot push " + value);
return;
}
stackArray[++top] = value;
System.out.println("Pushed: " + value);
}
// Pop operation: Remove element from top
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow! Stack is empty");
return -1;
}
int value = stackArray[top--];
System.out.println("Popped: " + value);
return value;
}
// Peek operation: View top element
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
}
return stackArray[top];
}
// Helper methods
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
}
class Stack:
def __init__(self, size):
self.maxSize = size
self.stackArray = [0] * size
self.top = -1 # Indicates empty stack
# Push operation
def push(self, value):
if self.isFull():
print("Stack Overflow! Cannot push", value)
return
self.top += 1
self.stackArray[self.top] = value
print("Pushed:", value)
# Pop operation
def pop(self):
if self.isEmpty():
print("Stack Underflow! Stack is empty")
return -1
value = self.stackArray[self.top]
self.top -= 1
print("Popped:", value)
return value
# Peek operation
def peek(self):
if self.isEmpty():
print("Stack is empty")
return -1
return self.stackArray[self.top]
# Helper methods
def isEmpty(self):
return self.top == -1
def isFull(self):
return self.top == self.maxSize - 1
#include <stdio.h>
#define MAX 100
struct Stack {
int stackArray[MAX];
int top;
int maxSize;
};
// Initialize stack
void initStack(struct Stack* s, int size) {
s->maxSize = size;
s->top = -1;
}
// Push operation
void push(struct Stack* s, int value) {
if (s->top == s->maxSize - 1) {
printf("Stack Overflow! Cannot push %d\n", value);
return;
}
s->stackArray[++(s->top)] = value;
printf("Pushed: %d\n", value);
}
// Pop operation
int pop(struct Stack* s) {
if (s->top == -1) {
printf("Stack Underflow! Stack is empty\n");
return -1;
}
int value = s->stackArray[(s->top)--];
printf("Popped: %d\n", value);
return value;
}
// Peek operation
int peek(struct Stack* s) {
if (s->top == -1) {
printf("Stack is empty\n");
return -1;
}
return s->stackArray[s->top];
}
#include <iostream>
using namespace std;
class Stack {
private:
int maxSize;
int* stackArray;
int top;
public:
// Constructor
Stack(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
// Push operation
void push(int value) {
if (isFull()) {
cout << "Stack Overflow! Cannot push " << value << endl;
return;
}
stackArray[++top] = value;
cout << "Pushed: " << value << endl;
}
// Pop operation
int pop() {
if (isEmpty()) {
cout << "Stack Underflow! Stack is empty" << endl;
return -1;
}
int value = stackArray[top--];
cout << "Popped: " << value << endl;
return value;
}
// Peek operation
int peek() {
if (isEmpty()) {
cout << "Stack is empty" << endl;
return -1;
}
return stackArray[top];
}
// Helper methods
bool isEmpty() {
return (top == -1);
}
bool isFull() {
return (top == maxSize - 1);
}
};