STACK AND QUEUE

By Dr. Anita Murmu

LINKED REPRESENTATION OF STACK AND QUEUE

• STACK USING LINKED LIST

• Concept
• A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
In a linked list implementation, each element (called a node) contains:
• data → value of the element
• next → pointer to the next node
• The top pointer points to the most recently inserted node.
 Operations

Structure of a Stack Node Push (Insert element at top)

•Create a new node.
struct Node { •Assign data.
int data; •Point its next to current top.
•Update top to new node.
struct Node* next;
}; void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Stack Overflow\n");
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed to stack\n", value);
}
Pop (Remove element from top)

• Check if stack is empty.

Display Stack
• Store top node temporarily.

• Move top to top->next.

void display() {
• Free the removed node. struct Node* temp = top;
if (temp == NULL) {
printf("Stack is empty\n");
void pop() { return;
if (top == NULL) { }
printf("Stack elements: ");
printf("Stack Underflow\n"); while (temp != NULL) {
return; printf("%d ", temp->data);
temp = temp->next;
} }
struct Node* temp = top; printf("\n");
}
printf("%d popped from stack\n", top->data);
top = top->next;
free(temp);

}
• QUEUE USING LINKED LIST

• Concept
• A queue is a linear data structure that follows the FIFO (First In, First Out) principle.
In a linked list representation, each node has:
• data → element value
• next → pointer to next node

We maintain two pointers:

• front → points to the first node
• rear → points to the last node
 Operations

Structure of a Queue Node Enqueue (Insert element at rear end)

•Create a new node.
•If queue is empty, make both front and rear point to new node.
•Otherwise, link new node to the end and move rear forward.
struct Node {
int data; void enqueue(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* next; newNode->data = value;
newNode->next = NULL;
};
if (rear == NULL) {
front = rear = newNode;
return;
}

rear->next = newNode;
rear = newNode;
printf("%d enqueued to queue\n", value);
}
Dequeue (Remove element from front end)
• Check if queue is empty.
• Move front pointer to next node.
Display Queue
• Free the old front node.
void display() {
void dequeue() { struct Node* temp = front;
if (temp == NULL) {
if (front == NULL) { printf("Queue is empty\n");
printf("Queue is empty\n"); return;
return; }
}
printf("Queue elements: ");
struct Node* temp = front; while (temp != NULL) {
printf("%d dequeued from queue\n", front->data); printf("%d ", temp->data);
temp = temp->next;
front = front->next;
}
if (front == NULL) printf("\n");
rear = NULL; }
free(temp);
}
PRIORITY QUEUE

• A Priority Queue is a type of queue in which each element is associated with a priority.
• Elements with higher priority are dequeued first.
• If two elements have the same priority, they are served in the order of their arrival (FIFO).
• Example:

Element Priority
A 2
B 1
C 3

Dequeue order → C → A → B (since priority 3 > 2 > 1)

TYPES OF PRIORITY QUEUE

• Ascending Priority Queue:

• Lower number = Higher priority (1 > 2 > 3).
• Descending Priority Queue:
• Higher number = Higher priority (3 > 2 > 1).

Implementation Methods

Priority queues can be implemented in two ways:

[Link] Array
[Link] Linked List
PRIORITY QUEUE USING ARRAY
• Maintain two arrays:
• data[] → stores the elements.
• priority[] → stores corresponding priorities.
• When inserting an element, we store both its value and priority.
When deleting, we remove the element with the highest priority.
❖Operations
• Insert Operation
• Add element and its priority at the end.
• No need to sort immediately.
• Delete Operation
• Find the element with highest priority.
• Delete that element.
#include <stdio.h>
void delete() { void display() {
#define SIZE 10 if (n == 0) { if (n == 0) {
printf("Queue Underflow\n"); printf("Queue is empty\n");
return; return;
int data[SIZE]; }
}
int priority[SIZE]; printf("Elements:\n");
int highest = 0; for (int i = 0; i < n; i++) {
int n = 0; // Number of elements printf("Value: %d | Priority: %d\n", data[i],
for (int i = 1; i < n; i++) {
if (priority[i] > priority[highest]) priority[i]);
highest = i; }
void insert(int value, int p) { }
}
if (n == SIZE) {
printf("Deleted element: %d (Priority: %d)\n", int main() {
printf("Queue Overflow\n"); insert(10, 2);
data[highest], priority[highest]);
return; insert(20, 3);
for (int i = highest; i < n - 1; i++) { insert(30, 1);
} display();
data[i] = data[i + 1];
data[n] = value; priority[i] = priority[i + 1]; delete();
} display();
priority[n] = p;
n--; return 0;
n++; } }
}
PRIORITY QUEUE USING LINKED LIST
• In a linked list representation, each node contains:
• data → value of the element
• priority → priority of the element
• next → pointer to next node
• Nodes are arranged in order of priority — highest priority node comes first.
❖Operations
• Insert Operation
• Create a new node.
• If the list is empty, insert at the start.
• Else, traverse until the correct position (based on priority) and insert the node.
• Delete Operation
• Remove the first node (highest priority node).
#include <stdio.h> if (front == NULL || p > front->priority) {
newNode->next = front; void display() {
#include <stdlib.h> front = newNode; if (front == NULL) {
struct Node { } else { printf("Queue is empty\n");
struct Node* temp = front; return;
int data; while (temp->next != NULL && }
int priority; temp->next->priority >= p) struct Node* temp = front;
temp = temp->next; printf("Priority Queue: \n");
struct Node* next; newNode->next = temp->next; while (temp != NULL) {
}; temp->next = newNode; printf("Value: %d | Priority: %d\n",
} temp->data, temp->priority);
} temp = temp->next;
struct Node* front = NULL; }
void delete() { }
if (front == NULL) {
void insert(int value, int p) { printf("Queue Underflow\n"); int main() {
return; insert(10, 2);
struct Node* newNode = (struct } insert(20, 1);
Node*)malloc(sizeof(struct Node)); struct Node* temp = front; insert(30, 3);
printf("Deleted element: %d (Priority: %d)\n", display();
newNode->data = value; temp->data, temp->priority); delete();
newNode->priority = p; front = front->next; display();
free(temp); return 0;
newNode->next = NULL;
} }