Aim:
Write a C Program to Implement a Stack Using Linked List (Pointer).
Theory:
Linked List Implementation of a Queue:
We go for a linked list implementation of a queue rather than an array implementation because of the run time memory allocation feature of linked lists. In this implementation we make a head pointer and make it point to the first created node in the stack. Whenever an element is enqueued into the queue, a new node is created at the end of the linked list and the element is kept in that node. Whenever a dequeue operation is performed on the queue, the head pointer is made to point to the node, next to the one that it is currently pointing to.
Insertion:
HEAD prev newItem

NULL
Deletion:
Before Deletion:

After Deletion
Algorithm:
- step 1:Make FRONT point to the new node
- step 2:Make REAR point to the new node
- step 3:Exit
- step 4:Make the next field of REAR point to the new node.
- step 5:Make REAR point to the new node.
Algorithm for delete:
- step 1:If the queue is empty: // FRONT = NULL
- step 2: Display “Queue empty”
- step 3:Exit
- step 4:Mark the node marked FRONT as current
- step 5:Make FRONT point to the next node in its sequence
- step 6:Release the memory for the node marked as current
Program:
#include <stdio.h> #include <stdlib.h> struct node { int info; struct node *ptr; }*front,*rear,*temp,*front1; void enq(int data); void deq(); void display(); void create(); int count = 0; void main() { int no, ch, e,i=0; printf("\n 1 - Enque"); printf("\n 2 - Deque"); printf("\n 4 - Exit"); printf("\n 3 - Display"); create(); while (i!=1) { printf("\n Enter choice : "); scanf("%d", &ch); switch (ch) { case 1: printf("Enter data : "); scanf("%d", &no); enq(no); break; case 2: deq(); break; case 3: display(); break; case 4: i= 1; break; default: printf("Wrong choice, Please enter correct choice "); break; } } } void create() { front = rear = NULL; } void enq(int data) { if (rear == NULL) { rear = (struct node *)malloc(1*sizeof(struct node)); rear->ptr = NULL; rear->info = data; front = rear; } else { temp=(struct node *)malloc(1*sizeof(struct node)); rear->ptr = temp; temp->info = data; temp->ptr = NULL; rear = temp; } } void display() { front1 = front; if ((front1 == NULL) && (rear == NULL)) { printf("Queue is empty"); return; } while (front1 != rear) { printf("%d ", front1->info); front1 = front1->ptr; } if (front1 == rear) printf("%d", front1->info); } void deq() { front1 = front; if (front1 == NULL) { printf("\n Error: Trying to display elements from empty queue"); return; } else if (front1->ptr != NULL) { front1 = front1->ptr; printf("\n Dequed value : %d", front->info); free(front); front = front1; } else { printf("\n Dequed value : %d", front->info); free(front); front = NULL; rear = NULL; } }
Execution:
Input: 1 45 1 55 1 77 2 3 4 Output: 1 - Enque 2 - Deque 4 - Exit 3 - Display Enter choice : Enter data : Enter choice : Enter data : Enter choice : Enter data : Enter choice : Dequed value : 45 Enter choice : 55 77 Enter choice :
Result:
Thus, Implement Queue using linked list (pointer) was executed successfully.