Stack Implementation using Linked List
Suppose the structure of a node is defined as given below:
struct node
{
int info;
struct node *link;
}*top;
Push Operation
Initially, the stack is empty, i.e., top = NULL.
Push First Element 10:
i. Allocate memory of the size of a node and store its address in a pointer variable, say, temp.
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the info part of a node.
temp->info = 10;
iii. As this is going to be the first node, the address part should have NULL value.
temp->link = NULL;
iv. The pointer variable, top, should point the last node; therefore, it should be updated by
inserting the address of a node into top.
top = temp;
100 10 NULL
top 100
temp
Push the Second Element 20:
i. Allocate memory of the size of a node and store its address in a pointer variable, say, temp.
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the info part of a node as: temp->info = 20;
iii. Link this node with the previous node. Note that the address of the previous node is in top.
temp->link = top;
iv. Update top, because the topmost node is now the newly pushed one as:
top = temp;
200 20 100 10 NULL
top 200 100
temp
Push the Third Element 30:
i. Allocate memory of the size of a node and store its address in a pointer variable, say temp.
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the info part of a node as
temp->info = 30;
iii. Link this node with the previous node. Note that the address of the previous node is in top.
temp->link = top;
iv. Update top, because the topmost node is now the newly pushed one.
top = temp;
300 30 100 20 100 10 NULL
top 300 200 100
temp
Algorithm: PUSH into Stack
Function: push[item, top]
1. Allocate memory of the size of a node and store its address in a pointer variable, say temp.
2. Insert data element in the info part of a node as temp->info = item.
3. If stack is empty, then insert NULL in the address part (link) of a new node as temp->link=NULL.
4. Else, Link new node with the previous node as temp->link=top.
5. Update top as the new node becomes the top most node as top = temp.
6. End.
Pop Operation
Let us suppose the stack is as below:
300 30 100 20 100 10 NULL
top 300 200 100
Temp
Pop Element:
i. Take a temporary variable, temp, and store the address of the topmost element in it.
temp = top;
ii. If the topmost element is deleted, the top should point to the next node and modified as
top = top->link;
200
top 30 100 20 100 10 NULL
300 200 100
temp
iii. Deallocate memory of a deleted node as
free(temp);
200 20 100 10 NULL
top 200 100
Pop Element:
i. Take a temporary variable, temp, and store the address of the topmost element in it as: temp
= top;
200 20 100 10 NULL
top 200 100
temp
ii. If the topmost element is deleted, the top should point to the next node and modified as
top = top->link;
100
top 20 100 10 NULL
200 100
temp
iii. Deallocate memory of a disconnected node as
free(temp);
100 10 NULL
Top 100
Pop Element:
i. Take a temporary variable, temp, and store the address of the topmost element in it as
temp = top;
100 10 NULL
Top 100
temp
ii. If the topmost element is deleted, the top should point to the next node and modified as
top = top->link; (top will become NULL)
iii. Deallocate memory of a deleted node as
free(temp);
NULL
top
Pop Element:
As the top is NULL, stack is empty. Element cannot be deleted.
The algorithm to pop element from stack is as follows:
Algorithm: POP from Stack
Function: pop[top]
i. If top == NULL then stack is empty. Element cannot be deleted.
ii. Else
a. Take a temporary variable, temp, and store the address of the topmost element in it.
b. Update pointer variable, top, to point the next node.
c. Deallocate memory of a disconnected node.
iii. End
Traversing in a Stack
Store the address of the element at the top, access the top element and then keep traversing and
accessing the elements till the stack is exhausted. The algorithm to traverse the stack is as
follows:
Algorithm: Traversing Stack
Function: traverseStack[top]
i. If top = = NULL then stack is empty, return
ii. Set ptr = top.
iii. Repeat the following steps until ptr becomes NULL
a. Access ptr->data
b. Set ptr = ptr->link
[End of loop]
iv. End
/*Program to Implement a Stack using Linked List*/
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *link;
}*top;
void push(int data);
void pop();
void display();
void destroy();
void stack_count();
int count = 0;
int main()
{
int no, ch, e;
top = NULL;
while (1)
{
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Display");
printf("\n 4- Quit!");
printf("\n 5 - Stack Count");
printf("\n 6 - Destroy stack");
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter the element: ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
display();
}
break;
case 4:
exit(0);
case 5:
stack_count();
break;
case 6:
destroy();
break;
default:
printf(" Wrong choice, Please enter correct choice! ");
}
}
return (0);
}
void stack_count() /* Count stack elements */
{
printf("\n No. of elements in stack : %d", count);
}
void push(int data) /* Push data into stack */
{
struct node *temp;
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->link = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->link = top;
temp->info = data;
top = temp;
}
count++;
}
void display() /* Display stack elements */
{
struct node *q = top;
while (q != NULL)
{
printf("%d ", q->info);
q = q->link;
}
}
void pop() /* Pop Operation on stack */
{
struct node *temp;
if (top == NULL)
{
printf("\n Error : Trying to pop from empty stack");
return;
}
else
{
temp=top;
top = top->link;
printf("\n Popped value : %d", temp->info);
free(top);
count--;
}
}
void empty() /* Check if stack is empty or not */
{
if (top == NULL)
printf("\n Stack is empty");
else
printf("\n Stack is not empty with %d elements", count);
}
void destroy() /* Destroy entire stack */
{
struct node *top1;
top1 = top;
while (top1 != NULL)
{
top1 = top->link;
free(top);
top = top1;
top1 = top1->link;
}
free(top1);
top = NULL;
printf("\n All stack elements destroyed");
count = 0;
}
Queue Implementation using Linked List
Suppose the structure of a node is defined as below:
struct node
{
int data;
struct node* next;
}*rear, *front;
Add Element in a Queue
Addition is done at the rear end of a queue.
Initially, suppose the queue is empty, therefore, front = NULL, rear = NULL.
Add the First Element 15:
i. Allocate memory of the size of a node and store its address in a pointer variable, say temp as
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the data part of a node as
temp->data = 15;
iii. Insert NULL in the address part of the node as
temp->next = NULL
iv. As this element is the first and also the last element, therefore front and rear both will point
to this node only as
front = temp; rear = temp;
front
10 NULL
rear
Add the Second Element 25:
i. Allocate memory of the size of a node and store its address in a pointer variable, say temp as
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the data part of a node as
temp->data = 25;
iii. Insert NULL in the address part of the node as
temp->next = NULL;
iv. As this is the last node, rear will point to this node as
rear = temp;
200
front 20 100 10 NULL
200 100 rear
temp
Add the Third Element 35:
i. Allocate memory of the size of a node and store its address in a pointer variable, say, temp
as
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the data part of a node as
temp->data = 35;
iii. Insert NULL in the address part of the node as
temp->next = NULL;
iv. As this is the last node, rear will point to this node as
rear = temp;
front
15 25 35 NULL
rear
temp
Algorithm: Add into Queue
Function: addQueue [front, rear, item]
1. Allocate memory of size of a node and store its address in a pointer variable, say temp.
2. Store the item in the data part of a new node as temp->data = item
3. Insert NULL in the address part of a new node as temp->next = NULL
4. If front == NULL, queue is empty then
Set front = temp and rear =temp
5. Else
i. Set rear->next = temp
ii. Set rear = temp
6. End
Delete Element from a Queue
Deletion is done from the front end.
Delete an Element:
1. Take a variable temp and store the address of the first node as: temp = front;
2. If the first node is deleted, then the second node will become the first node, therefore, modify
front as
front = front->next;
front
15 25 35 NULL
rear
temp
3. Deallocate memory occupied by the disconnected node as
free(temp);
front
25 35 NULL
rear
Delete an Element:
1. Take a variable temp and store the address of the first node as
temp = front;
2. If the first node is deleted, then the second node will become the first node, therefore, modify
front as
front = front->next;
front
25 35 NULL
rear
temp
3. Deallocate memory occupied by the disconnected node as
free(temp);
front
35 NULL
rear
Delete an Element:
1. Take a variable temp and store the address of the first node as
temp = front;
2. Set front = front->next;
NULL 35 NULL
front rear
3. Deallocate memory occupied by the disconnected node as
free(temp);
NULL
front
Delete an Element:
As the front has NULL and the queue is empty, we cannot delete an element.
Algorithm: Delete an element from Queue
Function: delQueue [front, rear]
1. If front ==NULL then queue is empty. Return.
2. Set temp = front
3. Modify front as front = front->next
4. Deallocate memory as free(temp)
5. End
Traversing a Queue
Store the address of the element at the front, access the front element and then keep traversing
and accessing the elements till the queue is exhausted. The algorithm to traverse the queue is
as follows:
Algorithm: Traversing a Queue
Function: traverseQueue[front, rear]
1. If front = = NULL, Queue is empty. Return
2. Set ptr = front
3. Repeat the steps 4 and 5 until ptr becomes NULL
4. Access ptr->data
5. Set ptr = ptr->next
[End of loop]
6. End
/*Program of Queue using linked list*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* next;
}
*rear, *front;
void delQueue();
void addQueue(int);
void display();
int main()
{
int value, i=0;
front=NULL;
while(1)
{
printf(" \n1. Add an element in Queue");
printf(" \n2. Delete an element from Queue");
printf(" \n3. Display elements of Queue");
printf(" \n4. Want to Quit!\n");
printf(" \nChoose Option: ");
scanf("%d",&i);
switch(i)
{
case 1:
printf("\nEnter a value to push into Queue: ");
scanf("%d",&value);
addQueue (value);
display();
break;
case 2:
delQueue();
display();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nwrong option! Choose other option:");
}
}
return 0;
}
void delQueue()
{
struct node *temp=front;
if(front!=NULL)
{
front = front->next;
free(temp);
}
else
{
printf("\nQueue is Empty");
}
}
void addQueue (int value)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=value;
if (front == NULL)
{
front=temp;
front->next=NULL;
rear=front;
}
else
{
rear->next=temp;
rear=temp;
temp->next=NULL;
}
}
void display()
{
struct node *ptr=front;
if(front!=NULL)
{
printf("\nElements are as: ");
while(ptr!=NULL)
{
printf("\t%d", ptr->data);
ptr=ptr->next;
}
printf("\n");
}
else
printf("\nQueue is Empty");
}
Circular Queue using Linked List
Suppose the structure of a node is defined as below:
struct node
{
int data;
struct node* link;
}*rear, *front;
Add an element in a circular queue
Addition is done at the rear end of a circular queue.
Initially, suppose the queue is empty, therefore front = NULL, rear = NULL.
Add the First Element 15:
i. Allocate memory of the size of a node and store its address in a pointer variable, say temp as
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the data part of a node as
temp->data = 15;
iii. As the last node should point to the first node, insert the address of the first node in the
address part of the node as
temp->link = front;
iv. As this element is the first and also the last element, therefore, the front and rear both will
point to this node only as
front = temp; rear = temp;
front
15
rear
temp
Add the Second Element 25.
i. Allocate memory of the size of a node and store its address in a pointer variable, say temp as
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the data part of a node as
temp->data = 25;
iii. Insert the address of the first node in the address part of new node as
temp->link = front;
iv. As this is the last node, therefore, rear will point to this node as
rear = temp;
front
15 25
rear
temp
Add the Third Element 35:
i. Allocate memory of the size of a node and store its address in a pointer variable, say temp as
temp = (struct node*) malloc (sizeof(struct node));
ii. Insert data element in the data part of a node as
temp->data = 35;
iii. Insert the address of the first node in the address part of the node as
temp->link = front;
iv. As this is the last node, therefore, rear will point to this node as
rear = temp;
front
15 25 35
rear
temp
Algorithm: Add into Circular Queue
Function: addCircularQueue [front, rear, item]
1. Allocate memory of size of a node and store its address in a pointer variable, say temp.
2. Store the item in the data part of a new node as temp->data = item
3 Insert the address of the first node in the address part of the node as temp->link = front;
4. If front == NULL, queue is empty then
Set front = temp and rear =temp
5. Else set rear->link = temp
6. Set rear = temp
7. End
Delete Element from a Circular Queue
Deletion is done from the front end.
Delete an Element:
1. Take a variable temp and store the address of the first node as
temp = front;
2. The first node is to be deleted, therefore, the second node will become the first node,
therefore, modify front as
front = front->link;
front
15 25 35
rear
temp
3. The last node should point to the first node therefore modify the address part of the last node
as
rear->link = front;
front
15 25 35
rear
temp
4. Deallocate memory occupied by the disconnected node as
free(temp);
front
25 35
rear
Delete an Element:
1. Take a variable temp and store the address of the first node as
temp = front;
2. If the first node is deleted, then the second node will become the first node, therefore, modify
front as
front = front->link;
front
25 35
rear
temp
3. The last node should point to the first node therefore, modify the address part of last node as
rear->link = front;
front
25 35
rear
temp
4. Deallocate memory occupied by the disconnected node as
free(temp);
front
35
rear
Delete an Element:
1. Take a variable temp and store the address of the first node as
temp = front;
front
35
rear
temp
2. As front == rear, since single node is remaining, therefore, set
front = rear = NULL;
NULL
front 35 NULL
rear
temp
3. Deallocate memory occupied by the disconnected node as
free(temp);
Delete Element:
As front has NULL and the circular queue is empty, we cannot delete an element.
Algorithm: Delete an element from Circular Queue
Function: delQueue [front, rear]
1. If front ==NULL then queue is empty. Return.
2. Set temp = front
3. If front == rear, then set front = rear = NULL
4. Modify front as front = front->link as the second node has become the first node
5. Set rear->link = front as the last node should point to the first node
4. Deallocate memory as free(temp)
5. End
Algorithm: Traversing a Circular Queue
Function: traverseCircularQueue[front, rear]
1. If front = = NULL, Queue is empty. Return
2. Set ptr = front
3. Repeat the steps 4 and 5 until the queue is exhausted
4. Access ptr->data
5. Set ptr = ptr->link
[End of loop]
6. End
/*Circular Queue through Linked List*/
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
/* structure containing a data part and link part */
struct node
{
int data ;
struct node * link ;
};
void addCircularQueue ( struct node **, struct node **, int ) ;
void delCircularQueue ( struct node **, struct node ** ) ;
void displayCircularQueue ( struct node * ) ;
int main( )
{
int num, option, i;
struct node *front, *rear ;
front = rear = NULL ;
while(1)
{
printf(“\nAdd an element:: 1”);
printf(“\nDelete an element::2”);
printf(“\nDisplay Circular Queue::3”);
printf(“\nWant to quit? :: 4”);
printf(“\nEnter your choice:: ”);
scanf(“%d”, &option);
switch(option)
{
case 1:
printf(“\nEnter any number:: ”);
scanf(“%d”, &num );
addCircularQueue ( &front, &rear, num ) ;
break;
case 2:
delCircularQueue ( &front, &rear ) ;
break;
case 3:
displayCircularQueue ( front ) ;
break;
case 4:
exit(0);
default:
printf(“\nWrong choice!”);
}
}
return 0;
}
void displayCircularQueue ( struct node *f ) /* displays the elements of the circular queue */
{
struct node *q = f;
do /* traverse the entire linked list */
{
printf ( "%d\t", q -> data ) ;
q = q -> link;
} while (q!=f);
}
void addCircularQueue ( struct node **f, struct node **r, int item ) /* adds a new element at the end*/
{
struct node *q ;
q = malloc ( sizeof ( struct node ) ) ; /* create new node */
q -> data = item;
if ( *f == NULL ) /* if the queue is empty */
*f = q;
else
( *r ) -> link = q ;
*r = q ;
( *r ) -> link = *f ;
}
void delCircularQueue ( struct node **f, struct node **r ) /* removes an element from front*/
{
struct node *q ;
int item ;
if ( *f == NULL ) /* if queue is empty */
{
printf ( "queue is empty" ) ;
return;
}
else if ( *f == *r )
{
item = ( *f ) -> data ;
free ( *f ) ;
*f = NULL;
*r = NULL;
}
else
{
q = *f ; /* delete the node */
item = q -> data ;
*f = ( *f ) -> link ;
( *r ) -> link = *f ;
free ( q ) ;
}
printf(“\nElement %d is deleted”, item);
}