29
stack.push(20);
stack.push(30);
std::cout << "Top element: " << stack.peek() << "\n";
stack.pop();
stack.display();
return 0;
}
Linked-List-Based Implementation
This approach uses a dynamic linked list to create a stack, eliminating the limitation of fixed size.
Code Example:
#include <iostream>
struct Node {
int data;
Node* next;
};
class Stack {
private:
Node* top; // Pointer to the topmost element
public:
Stack() : top(nullptr) {}
void push(int value) {
Node* newNode = new Node{value, top};
30
top = newNode;
}
void pop() {
if (top == nullptr) {
std::cout << "Stack Underflow\n";
return;
}
Node* temp = top;
top = top->next;
delete temp;
}
int peek() {
if (top == nullptr) {
std::cout << "Stack is Empty\n";
return -1;
}
return top->data;
}
bool isEmpty() {
return top == nullptr;
}
void display() {
Node* temp = top;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << "\n";
31
˜Stack() {
while (top != nullptr) {
pop();
}
}
};
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
std::cout << "Top element: " << stack.peek() << "\n";
stack.pop();
stack.display();
return 0;
}
STL std::stack Implementation
The C++ Standard Template Library provides a ready-to-use std::stack class for easy stack
operations.
Code Example:
#include <iostream>
#include <stack>
32
int main() {
std::stack<int> stack;
stack.push(10);
stack.push(20);
stack.push(30);
std::cout << "Top element: " << stack.top() << "\n";
stack.pop();
std::cout << "After popping, top element: " << stack.top() << "\n";
std::cout << "Elements in stack: ";
while (!stack.empty()) {
std::cout << stack.top() << " ";
stack.pop();
}
std::cout << "\n";
return 0;
}
3.3 Stack Applications
Stacks are widely used in software engineering due to their straightforward LIFO behavior.
Below are some prominent applications: Undo Functionality in Applications
One of the most popular uses of stacks is in implementing undo/redo operations in text editors,
design software, or IDEs. Each action performed by the user is pushed onto a stack, and an undo
33
action pops the last operation to reverse it.
How it works:
• Undo: Uses a stack to store actions. Popping the stack undoes the most recent action.
• Redo: A second stack can be used to store undone actions for reapplying them.
Code Example of Undo Functionality:
#include <iostream>
#include <stack>
#include <string>
int main() {
std::stack<std::string> undoStack;
std::stack<std::string> redoStack;
undoStack.push("Write code");
undoStack.push("Save file");
undoStack.push("Compile program");
std::cout << "Undoing: " << undoStack.top() << "\n";
redoStack.push(undoStack.top());
undoStack.pop();
std::cout << "Redoing: " << redoStack.top() << "\n";
undoStack.push(redoStack.top());
redoStack.pop();
return 0;
}
34
Function Call Stack
Stacks are essential in maintaining function calls in programs. The call stack ensures that
function calls are resolved in the correct order.
Expression Evaluation
Stacks are used to evaluate postfix or prefix expressions and to convert between infix, prefix, and
postfix notation.
Conclusion
Stacks are indispensable in many software applications due to their simplicity and efficiency.
Whether managing operations like undo/redo, evaluating expressions, or tracking function calls,
understanding and implementing stacks in C++ equips programmers with the ability to solve a
wide range of computational problems effectively. This chapter has laid the groundwork for
mastering stacks, paving the way for more advanced data structures like queues and priority
queues in the next chapters.
Chapter 4
Queues
A queue is a linear data structure that operates on the First In, First Out (FIFO) principle,
where the first element added to the queue is the first one to be removed. Queues are used
extensively in scenarios where tasks need to be managed in sequential order, such as scheduling
and buffering. This chapter explores the implementation and variations of queues in C++,
including simple queues, double-ended queues (Deque), and priority queues.
4.1 What is a Queue?
A queue is similar to a real-world waiting line where people are served in the order they arrive.
In computer science, queues are used to manage tasks, processes, or data streams.
Key Characteristics of Queues:
• Operates on the FIFO principle.
• Supports two main operations:
– Enqueue: Adds an element to the rear of the queue.
35
36
– Dequeue: Removes an element from the front of the queue.
• Variants include double-ended queues (Deque) and priority queues.
4.2 Queue Implementation in C++
Queues can be implemented using arrays, linked lists, or the Standard Template Library (STL).
This section provides examples for all three implementations.
Simple Queue Implementation
Using Arrays
An array-based queue is simple but has a fixed size, which can lead to overflow if not handled
correctly.
Code Example:
#include <iostream>
#define MAX 100
class Queue {
private:
int arr[MAX];
int front, rear;
public:
Queue() : front(-1), rear(-1) {}
void enqueue(int value) {
if (rear == MAX - 1) {
std::cout << "Queue Overflow\n";
return;
37
}
if (front == -1) front = 0; // Initialize front on the first
,→ enqueue
arr[++rear] = value;
}
void dequeue() {
if (front == -1 || front > rear) {
std::cout << "Queue Underflow\n";
return;
}
front++;
}
int peek() {
if (front == -1 || front > rear) {
std::cout << "Queue is Empty\n";
return -1;
}
return arr[front];
}
bool isEmpty() {
return front == -1 || front > rear;
}
void display() {
if (isEmpty()) {
std::cout << "Queue is Empty\n";
return;
}
for (int i = front; i <= rear; i++) {
38
std::cout << arr[i] << " ";
}
std::cout << "\n";
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display();
q.dequeue();
q.display();
return 0;
}
Using Linked Lists
A linked list offers a dynamic alternative to implement queues, eliminating size constraints.
Code Example:
#include <iostream>
struct Node {
int data;
Node* next;
};
class Queue {
39
private:
Node *front, *rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
void enqueue(int value) {
Node* newNode = new Node{value, nullptr};
if (rear == nullptr) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
void dequeue() {
if (front == nullptr) {
std::cout << "Queue Underflow\n";
return;
}
Node* temp = front;
front = front->next;
if (front == nullptr) rear = nullptr; // Reset rear if queue
,→ becomes empty
delete temp;
}
int peek() {
if (front == nullptr) {
std::cout << "Queue is Empty\n";
return -1;
