Stack and Queue
Stack is a Last-In-First-Out data structure, which means the last element added to the list will be the first one to be removed.
It is used in many real-world applications. For example, when you view emails on your mobile, the most recent one is at the top, and the oldest one is at the bottom. This is an application of a stack in the real world.
Example of Stack
In the image above, you can see a stack. For example, stack 1, 2, and 3 are placed on top of each other. Initially, we push 1, which is at the top. Then, we add 2, and it becomes the top while 1 goes below it. Finally, we push 3, making it the new top. To remove or pop the top element, 3 is removed, leaving 2 as the new top, and so on.
Code of Stack
In the image above, I have shown the main function where push, pop, and print functions are already defined in the structure. Here, we perform the same operations as explained in the stack example. First, we push 1, then 2, and then 3. Printing the stack shows: 3 -> 2 -> 1 -> null. The "->" is added to make it simple and understandable. After removing or popping the top element, the stack now looks like: 2 -> 1 -> null. This demonstrates how the stack works.
Now let us see the underlying code step by step. Don’t worry, I will explain each part.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
// constructor
Node(int v): data(v), next(nullptr) {}
};
In this part, I added the boilerplate code. The main part starts with struct Node, where I defined an integer data and a pointer to the next node. After that, the Node(int v): data(v), next(nullptr) {} is a constructor to initialize the values, so we don’t have to do it manually every time.
struct Stack {
Node* head;
Stack(): head(nullptr) {}
};
In this part, I created another struct, Stack, which includes a pointer head. Initially, the head is nullptr. That’s why I added the constructor Stack(): head(nullptr) {}.
// push will add a new node to the top of the stack
void push(int v) {
Node* n = new Node(v);
n->next = head;
head = n;
}
The push method adds a node to the top of the stack. First, it creates a new node and assigns it to a pointer n. If there is any element in the stack, the new node points to it, and head is updated to n.
// pop will remove the top node from the stack
void pop() {
if (head == nullptr) {
cout << "stack is empty" << endl;
} else {
Node* t = head;
head = head->next;
delete t;
}
}
The pop method removes the top element from the stack. It first checks if the stack is empty. If not, it uses a temporary node t to manipulate the head. The head is updated to point to the next element, and t is deleted.
void print() {
Node* t = head;
while (t != nullptr) {
cout << t->data << " -> ";
t = t->next;
}
cout << "null" << endl;
}
};
The print function displays all elements in the stack. First, a temporary node t is created. Using a while loop, the function prints the data and updates t to point to the next node until null is reached. Finally, "null" is printed to indicate the end of the stack.
Queue
Queue is a First In, First Out (FIFO) data structure, which means the first element added will be the first one to be removed.
In real-world applications, it can be like a booking system where the first person to book is the first to be served.
Queue Example
In the image above, you can see a queue example. I added 1, 2, 3 using the enqueue function, which adds elements from the front to the back. When the dequeue function is called, it removes the first element, so the queue becomes 2 and 3.
Queue Code
This is the main function where the enqueue (add) and dequeue (remove) functions are used. For example, enqueue(1), enqueue(2), and so on. The dequeue function removes the first element added, and the remaining queue is printed. You can see the values as 3 -> 2 -> 1 -> null, and when dequeue() is called, 1 is removed, as it was the first to be added.
Let’s see the code step by step:
struct Node {
int data;
Node* next;
Node(int v) : data(v), next(nullptr) {}
};
This is the struct, same as it was in the stack, so nothing has changed here.
struct Queue {
Node* head;
Queue() : head(nullptr) {}
Here, I added a struct named Queue with a head initialized to nullptr using the constructor.
// enqueue will add a new node to the end of the queue
void enqueue(int v) {
Node* n = new Node(v);
if (head == nullptr) {
head = n;
} else {
Node* t = head;
while (t->next != nullptr) {
t = t->next;
}
t->next = n;
}
}
The enqueue function adds a new node to the end of the queue. It first checks if the queue is empty; if it is, the head is set to the new node. Otherwise, a temporary node t is used to iterate to the last node, and the new node n is added at the end.
// dequeue will remove the first node from the queue
void dequeue() {
if (head == nullptr) {
cout << "Queue is empty" << endl;
} else {
Node* t = head;
head = head->next;
delete t;
}
}
The dequeue function removes the first node from the queue, similar to the pop operation in a stack. It’s straightforward if you understand each step.
void print() {
Node* t = head;
while (t != nullptr) {
cout << t->data << " -> ";
t = t->next;
}
cout << "null" << endl;
}
};
Finally, the print function simply prints all the values in the queue. It’s similar to the print function in the stack example, so there’s nothing new to explain here.
This concludes today’s tutorial. See you in the next one 😊
Check out the full video tutorial:
