Loading W Code...
LIFO and FIFO data structures - fundamental for many algorithms.
4
Topics
40
Minutes
C++
Language
Real-life examples:
- Stack of plates: You take the top plate first
- Browser back button: Goes to the last visited page
- Undo operation: Undoes the last action first
- Call stack in programming: Last function called returns first
Key Operations:
- Push: Add element to the top
- Pop: Remove element from the top
- Peek/Top: View the top element without removing
- isEmpty: Check if stack is empty
Where is Stack used?
- Function calls (call stack)
- Expression evaluation and conversion
- Backtracking algorithms
- Undo/Redo functionality
#include <iostream>
#include <stack> // STL Stack
using namespace std;
int main() {
// Using STL Stack
stack<int> s;
// Push elements
s.push(10);
s.push(20);
s.push(30);
cout << "Pushed: 10, 20, 30" << endl;
// Top element
cout << "Top element: " << s.top() << endl; // 30
// Pop element
s.pop();
cout << "After pop, top: " << s.top() << endl; // 20
// Size
cout << "Size: " << s.size() << endl; // 2
// Check if empty
cout << "Is empty: " << (s.empty() ? "Yes" : "No") << endl; // No
// Pop all elements
cout << "Popping all: ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl; // 20 10
return 0;
}1. Array-based Stack
- Fixed size (need to define maximum capacity)
- Fast operations (direct memory access)
- May waste space or overflow
2. Linked List-based Stack
- Dynamic size (grows as needed)
- No overflow (until memory runs out)
- Extra memory for pointers
Array Implementation Steps:
1. Create array with max size
2. Keep track of 'top' index (-1 means empty)
3. Push: increment top, add element
4. Pop: return element, decrement top
Important Checks:
- Overflow: Stack is full (top == maxSize - 1)
- Underflow: Stack is empty (top == -1)
#include <iostream>
using namespace std;
// Array-based Stack Implementation
class Stack {
private:
int* arr;
int top;
int capacity;
public:
Stack(int size) {
capacity = size;
arr = new int[capacity];
top = -1;
}
~Stack() {
delete[] arr;
}
void push(int val) {
if (isFull()) {
cout << "Stack Overflow!" << endl;
return;
}
arr[++top] = val;
}
int pop() {
if (isEmpty()) {
cout << "Stack Underflow!" << endl;
return -1;
}
return arr[top--];
}
int peek() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return -1;
}
return arr[top];
}
bool isEmpty() {
return top == -1;
}
bool isFull() {
return top == capacity - 1;
}
int size() {
return top + 1;
}
};
int main() {
Stack s(5);
s.push(10);
s.push(20);
s.push(30);
cout << "Top: " << s.peek() << endl; // 30
cout << "Popped: " << s.pop() << endl; // 30
cout << "Top after pop: " << s.peek() << endl; // 20
cout << "Size: " << s.size() << endl; // 2
return 0;
}Real-life examples:
- Queue at a ticket counter: First person gets served first
- Print queue: First document prints first
- CPU scheduling: Processes are handled in order
- Message queues in software
Key Operations:
- Enqueue: Add element at the rear (back)
- Dequeue: Remove element from the front
- Front: View the front element
- Rear: View the last element
- isEmpty: Check if queue is empty
Types of Queues:
1. Simple Queue: Basic FIFO
2. Circular Queue: Last position connects to first
3. Priority Queue: Elements have priorities
4. Deque: Insert/Delete from both ends
#include <iostream>
#include <queue> // STL Queue
using namespace std;
int main() {
// Using STL Queue
queue<int> q;
// Enqueue (push) elements
q.push(10);
q.push(20);
q.push(30);
cout << "Enqueued: 10, 20, 30" << endl;
// Front and back
cout << "Front: " << q.front() << endl; // 10
cout << "Back: " << q.back() << endl; // 30
// Dequeue (pop) element
q.pop();
cout << "After dequeue, front: " << q.front() << endl; // 20
// Size
cout << "Size: " << q.size() << endl; // 2
// Check if empty
cout << "Is empty: " << (q.empty() ? "Yes" : "No") << endl;
// Dequeue all
cout << "Dequeue all: ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl; // 20 30
return 0;
}Why Circular Queue?
In a normal queue, once the rear reaches the end, we can't add more elements even if there's space at the front (after dequeuing). Circular queue solves this!
How it works:
- Use modulo operation to wrap around
- Front and rear pointers move in a circle
- When rear reaches end, it wraps to beginning if space available
Formulas:
- Next position: (current + 1) % size
- Is Full: (rear + 1) % size == front
- Is Empty: front == -1
Applications:
- CPU scheduling (Round Robin)
- Memory management
- Traffic system
- Buffer in streaming
#include <iostream>
using namespace std;
class CircularQueue {
private:
int* arr;
int front, rear;
int capacity;
public:
CircularQueue(int size) {
capacity = size;
arr = new int[capacity];
front = rear = -1;
}
~CircularQueue() {
delete[] arr;
}
void enqueue(int val) {
// Check if full
if ((rear + 1) % capacity == front) {
cout << "Queue is full!" << endl;
return;
}
if (front == -1) {
front = 0; // First element
}
rear = (rear + 1) % capacity; // Circular increment
arr[rear] = val;
cout << "Enqueued: " << val << endl;
}
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
int val = arr[front];
if (front == rear) {
// Last element
front = rear = -1;
} else {
front = (front + 1) % capacity; // Circular increment
}
return val;
}
int getFront() {
if (isEmpty()) return -1;
return arr[front];
}
bool isEmpty() {
return front == -1;
}
void display() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return;
}
cout << "Queue: ";
int i = front;
while (true) {
cout << arr[i] << " ";
if (i == rear) break;
i = (i + 1) % capacity;
}
cout << endl;
}
};
int main() {
CircularQueue cq(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.enqueue(40);
cq.display(); // 10 20 30 40
cout << "Dequeued: " << cq.dequeue() << endl; // 10
cout << "Dequeued: " << cq.dequeue() << endl; // 20
cq.enqueue(50); // Wraps around!
cq.enqueue(60);
cq.display(); // 30 40 50 60
return 0;
}