Stack and Queue Using Linked List
PART A: STACK USING LINKED LIST
Definition:
A Stack is a linear data structure that follows the LIFO (Last In First Out) principle, meaning the
last element inserted is the first one to be removed. In a linked list implementation, each element
is stored in a node containing data and a pointer to the next node. The top pointer always points
to the most recently inserted node.
Structure of Node:
struct Node {
int data;
Node* next;
};
Node* top = NULL;
Operations on Stack:
1. Push Operation – Inserts an element at the top of the stack.
1 Create a new node.
2 Store the data in the node.
3 Set new node's next to the current top.
4 Update top to point to the new node.
2. Pop Operation – Removes the top element from the stack.
1 Check whether the stack is empty.
2 Store the top node in a temporary pointer.
3 Move top to top->next.
4 Delete the temporary node.
3. Display Operation – Traverses from top to the last node and displays all elements.
Program:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* top = NULL;
void push(int x) {
Node* n = new Node;
n->data = x;
n->next = top;
top = n;
}
void pop() {
if (top == NULL) return;
Node* t = top;
top = top->next;
delete t;
}
void display() {
for (Node* p = top; p != NULL; p = p->next)
cout << p->data << " ";
}
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
}
Output:
30 20 10 20 10
Explanation:
Three elements 10, 20 and 30 are pushed onto the stack. Since each push operation inserts the
new node at the top, the stack from top to bottom becomes 30, 20, 10, and the first display() call
prints "30 20 10". The pop() function then removes the topmost element (30) by moving the top
pointer to the next node and deleting the old top node. The second display() call now prints "20
10", showing the remaining elements in the stack.
Advantages:
• Dynamic memory allocation – size grows or shrinks as needed.
• No fixed size limitation, unlike array implementation.
• Efficient insertion and deletion at the top.
Time Complexity:
Operation Complexity
Push O(1)
Pop O(1)
Peek O(1)
Display O(n)
PART B: QUEUE USING LINKED LIST
Definition:
A Queue is a linear data structure that follows the FIFO (First In First Out) principle, meaning the
first element inserted is the first one to be removed. In a linked list implementation, insertion
takes place at the rear end and deletion takes place at the front end, using two pointers called
front and rear.
Structure of Node:
struct Node {
int data;
Node* next;
};
Node *front = NULL, *rear = NULL;
Operations on Queue:
1. Enqueue Operation – Inserts an element at the rear end of the queue.
1 Create a new node and store data in it.
2 Set the new node's next pointer to NULL.
3 If the queue is empty, set both front and rear to the new node.
4 Otherwise, link the current rear node to the new node and update rear.
2. Dequeue Operation – Removes an element from the front end.
1 Check whether the queue is empty.
2 Store the front node in a temporary pointer.
3 Move front to the next node.
4 If front becomes NULL, set rear to NULL as well.
5 Delete the temporary node.
3. Display Operation – Traverses from front to rear and displays all elements.
Program:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node *front = NULL, *rear = NULL;
void enqueue(int x) {
Node* n = new Node;
n->data = x;
n->next = NULL;
if (rear == NULL)
front = rear = n;
else {
rear->next = n;
rear = n;
}
}
void dequeue() {
if (front == NULL) return;
Node* t = front;
front = front->next;
if (front == NULL)
rear = NULL;
delete t;
}
void display() {
for (Node* p = front; p != NULL; p = p->next)
cout << p->data << " ";
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
}
Output:
10 20 30 20 30
Explanation:
Three elements 10, 20 and 30 are inserted into the queue using enqueue(). Since insertion
takes place at the rear, the queue from front to rear becomes 10, 20, 30, and the first display()
call prints "10 20 30". The dequeue() function then removes the element at the front (10) by
moving the front pointer to the next node and deleting the old front node. The second display()
call now prints "20 30", showing the remaining elements in the queue.
Advantages:
• Dynamic memory allocation – size grows or shrinks as needed.
• No wastage of memory, unlike array implementation.
• Efficient insertion at the rear and deletion at the front.
Time Complexity:
Operation Complexity
Enqueue O(1)
Dequeue O(1)
Front O(1)
Display O(n)
Conclusion
• Stack follows the LIFO principle and uses a single pointer (top).
• Queue follows the FIFO principle and uses two pointers (front and rear).
• Linked list implementation provides dynamic memory allocation and efficient
insertion/deletion operations for both data structures.