Loading W Code...
LIFO and FIFO data structures - fundamental for many algorithms.
Imagine a stack of dinner plates in a cafeteria. You can only place a new plate on the very top of the stack, and you can only take a plate off from the top. If you try to pull a plate from the bottom or middle, the entire stack collapses.
A Stack is a linear data structure that restricts insertion and deletion operations to one end, commonly referred to as the Top. It follows the LIFO principle.
O(1) Time):push(x): Places element x onto the top of the stack.pop(): Removes the element currently sitting at the top of the stack.top() / peek(): Reads the value of the top element without removing it.empty(): Returns a boolean indicating if the stack contains no elements.#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;
}Stacks are implemented using two primary backing structures:
top to track the current top element (initialized to -1).O(1)).top == capacity - 1).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;
}Imagine a line of customers waiting at a grocery store checkout. The first customer to join the line is the first one served and checked out. New customers must join at the back of the line.
A Queue is a linear data structure that operates on the FIFO principle. Insertions occur at one end (the Rear / Back), while deletions occur at the opposite end (the Front).
O(1) Time):enqueue(x): Inserts element x at the rear of the queue.dequeue(): Removes the element situated at the front of the queue.front(): Reads the value at the front of the queue without removing it.empty(): Returns true if the queue contains no elements.#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;
}In a basic array-based linear queue, once elements are dequeued, the space at the front of the array is wasted. Even if there are empty slots at the front, we cannot enqueue more items once the rear index reaches the end of the array.
A Circular Queue solves this memory wastage by connecting the last index of the array back to the first index, forming a logical loop or ring.
We shift indices using the modulo operator (%):
rear = (rear + 1) % capacityfront = (front + 1) % capacity(rear + 1) % capacity == frontfront == -1#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;
}