Stacks and Queues in C – Master the Concepts of LIFO & FIFO

After getting well-versed with linked lists and arrays in C, you are now ready to explore a new concept, that is stacks and queues. Both stacks and queues in C are data structures that can be implemented using either arrays or linked lists.

Newbies to programming often find it cumbersome to implement stacks and queues in C as it requires a thorough knowledge of all the concepts of C that we have covered so far. So, we will understand each and every important concept involved in stacks and queues in C in detail so that you would develop a clear understanding of the topic.

In this Stacks and Queues in C tutorial, we will discuss:

• Stack in C
• Array implementation of a Stack
• Linked list implementation of a Stack
• Applications of Stack
• Queue in C
• Array implementation of a Queue
• Linked list implementation of a Queue
• Circular Queue
• Applications of Queue

If we want to learn this concept then we have to go deep inside it. That’s why we are going to discuss its key topics, which will be helping us to grasp the concept in an efficient way. So let’s start –

1. What is Stack in C?

A stack in C is nothing but a linear data structure that follows the LIFO rule (Last In First Out). In a stack, both insertion and deletion take place from just one end, that is, from the top.

In order to better understand it, consider the following scenario: Imagine you have 5 plates that you have to keep on top of each other of distinct colors: Red, Green, Blue, White, and Orange.

You start by placing the red plate on the table. This is the first element of the stack. Then, you place the green plate on top of the red plate. This is the second element of the stack. Similarly, you place the blue plate followed by white and then finally orange. Note that the first plate you inserted into the stack was the red one. Now, you want to remove the red plate. But, before that, you need to remove the rest of the plates that are on top of the red one.

From this discussion, it is pretty obvious that the first plate (first data element) to be inserted is removed at the last. And, the last plate to be inserted is removed at first, that is, it follows the “Last In First Out” rule. Also, we infer that placing and removing the plate is done from the top, that is, insertion and deletion are done from the top

We can implement a stack in C in 2 ways:

1. Statically: Array implementation of stacks allows the static memory allocation of its data elements. It is important to note that in this method, the stack acquires all the features of an array.
2. Dynamically: Linked list implementation of stacks follow the dynamic memory allocation of its data elements. It is important to note that in this method, the stack inherits all the characteristics of a linked list in C.

1.1 Array Implementation of Stack in C

As we already discussed, arrays support the static memory allocation of the data elements of the stack. Therefore, it is important to determine the size of the stack prior to the program run.

The C stack functions basically include:

1.1.1 Insertion

In a stack, the operation of inserting an element into the stack is referred to as pushing an element in the stack. The elements are inserted into the stack from the top and hence would compel the elements to shift.

Here is a diagrammatic representation of how elements are pushed into a stack:

This is how we can insert elements into a C stack:

#define LIMIT 100
void push()
{
int stack[LIMIT], top, element;
if(top == LIMIT- 1)
{
printf("Stack Overflow\n");
}
else
{
printf("Enter the element to be inserted:");
scanf("%d", &element);
top++;
stack[top]=element;
}
}

Enhance your Fundamental Skills with Different types of Operators in C

1.1.2 Deletion

In a stack, the operation of deleting an element into the stack is referred to as popping an element in the stack. The deletion of a data element from the stack is done from the top.

Here is a diagrammatic representation of how elements are pushed into a stack:

This is how we can delete elements from a stack:

#define LIMIT 100
void pop()
{
int stack[LIMIT], top, element;
if(top == -1)
{
printf("Stack underflow\n");
}
else
{
element=stack[top];
printf("The deleted item is %d\n",stack[top]);
top--; // The element below the topmost element is deleted
}
}

1.1.3 Display

The stack data elements are displayed in the stack according to the LIFO rule.

This is how you can display the stack in C:

#define LIMIT 100
void display()
{
int stack[LIMIT], top, i;
if(top == -1)
{
printf("Stack underflow\n"); // Stack is empty
}
else if(top > 0)
{
printf("The elements of the stack are:\n");
for(i = top; i >= 0; i--) // top to bottom traversal
{
printf("%d\n",stack[i]);
}
}
}

Apart from these 3 main functions, it is necessary to check the overflow and underflow conditions to avoid unfavorable situations.

1.1.4 Stack Overflow

Here we are talking about the static memory allocation of data elements of a stack. Therefore, if the stack is filled completely, that is, no more elements can be inserted in the stack, then the condition would be called STACK-FULL condition. It is also referred to as stack overflow.

1.1.5 Stack Underflow

In case we wish to display the data elements of the stack or perform the deletion operation, but no elements have been inserted into the stack yet, this condition is called STACK-EMPTY. It is also referred to as stack underflow.

Before discussing the example, let’s revise the concept of Variables in C

Here is a program in C that illustrates the array implementation of stacks:

#include <stdio.h>
#include <stdlib.h>
#define LIMIT 100 // Specifying the maximum limit of the stack

/* Global declaration of variables */

int stack[LIMIT]; // Array implementation of stack
int top; // To insert and delete the data elements in the stack
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations

void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the element from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

printf ("ARRAY IMPLEMENTATION USING STACKS\n\n");
top = -1; // Initializing top to -1 indicates that it is empty
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void push()
{
int element;
if(top == LIMIT- 1)
{
printf("Stack underflow\n");
}
else
{
printf("Enter the element to be inserted:");
scanf("%d", &element);
top++;
stack[top]=element;
}
}

void pop()
{
int element;
if(top == -1)
{
printf("Stack underflow\n");
}
else
{
element=stack[top];
printf("The deleted item is %d\n",stack[top]);
top--; // The element below the topmost element is deleted
}
}

void display()
{
if(top == -1)
{
printf("Stack underflow\n"); // Stack is empty
}
else if(top > 0)
{
printf("The elements of the stack are:\n");
for(i = top; i >= 0; i--) // top to bottom traversal
{
printf("%d\n",stack[i]);
}
}
}

Output-

1.2 Linked List Implementation of Stack in C

As we already discussed, linked lists support the dynamic memory allocation of the data elements of the stack. Therefore, the size of the stack is allocated during the program run and needn’t be specified beforehand.

The 3 basic operations of Insertion, Deletion, and Display follow a similar trend as we saw in the array implementation of stacks.

Functions in C – An Important Concept for beginners

The stack functions basically include:

1.2.1  Insertion

This is how we can insert elements into the stack in C:

void push ()
{
int data;
struct node *pointer = (struct node*)malloc(sizeof(struct node));
if(pointer == NULL)
{
printf("Stack overflow");
}
else
{
printf("Enter the element to be inserted: ");
scanf("%d",&data);
if(temp == NULL)
{
pointer -> data = data;
pointer -> next = NULL;
temp = pointer;
}
else
{
pointer -> data = data;
pointer -> next = temp;
temp = pointer;
}
}
}

1.2.2 Deletion

This is how we can delete elements from a stack in C:

void pop()
{
int item;
struct node *pointer;
if (temp == NULL)
{
printf("Stack Underflow\n");
}
else
{
item = temp -> data;
pointer = temp;
temp = temp -> next;
free(pointer);
printf("The deleted item is %d\n",item);
}
}

1.2.3 Display

This is how we display the elements of a stack:

void display()
{
int i;
struct node *pointer;
pointer = temp;
if(pointer == NULL)
{
printf("Stack underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while(pointer!= NULL)
{
printf("%d\n",pointer -> data);
pointer = pointer -> next;
}
}
}

Here is a code in C that illustrates the linked list implementation of arrays:

#include <stdio.h>
#include <stdlib.h>

void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the elememt from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule

struct node
{
int data;
struct node *next;
};
struct node *temp;

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

int choice;
printf ("LINKED LIST IMPLEMENTATION USING STACKS\n\n");
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void push ()
{
int data;
struct node *pointer = (struct node*)malloc(sizeof(struct node));
if(pointer == NULL)
{
printf("Stack overflow");
}
else
{
printf("Enter the element to be inserted: ");
scanf("%d",&data);
if(temp == NULL)
{
pointer -> data = data;
pointer -> next = NULL;
temp = pointer;
}
else
{
pointer -> data = data;
pointer -> next = temp;
temp = pointer;
}
}
}

void pop()
{
int item;
struct node *pointer;
if (temp == NULL)
{
printf("Stack Underflow\n");
}
else
{
item = temp -> data;
pointer = temp;
temp = temp -> next;
free(pointer);
printf("The deleted item is %d\n",item);
}
}
void display()
{
int i;
struct node *pointer;
pointer = temp;
if(pointer == NULL)
{
printf("Stack underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while(pointer!= NULL)
{
printf("%d\n",pointer -> data);
pointer = pointer -> next;
}
}
}

Output-

1.3 Application of Stack in C

The principle LIFO followed by stacks gives birth to the various applications of stacks. Some of the most popular applications of stacks are:

• Number reversal: A stack helps you reverse a number or a word entered as a sequence of digits or characters respectively.
• Undo operation: Implementation of a stack helps you perform the “undo” operation in text editors or word processors. Here, all the changes done in the text editor are stored in a stack.
• Infix to postfix conversion: Using stacks, you can perform the conversion of an infix expression to a postfix expression.
• Backtracking: Stacks are finding applications in puzzle or maze problem-solving.
• Depth-first search (DFS): Stacks allow you to perform a searching algorithm called the depth-first search.

2. What is a Queue in C?

In contrast to a stack, a queue in C is nothing but a linear data structure that follows the FIFO rule (First In First Out). Insertion is done from the back (the rear end) and deletion is done from the front.

Learn More about Structures in C Language

In order to better understand the concept of queues in C, we can say that it follows the rule of “First Come First Serve”. Let us consider a simple scenario to help you get a clear picture of queues. Suppose you want to purchase a movie ticket. For that, you need to stand in a queue and wait for your turn, that is, you have to stand at the rear end of the queue. You can’t simply stand in the middle of the queue or occupy the front position.

From the above discussion, it is pretty obvious that insertion in a queue takes place from the back and deletion is taking place from the front as the first person to enter the queue would be the first to get his job done and leave.

We can implement a queue in 2 ways:

1. Statically: Array implementation of queues allows the static memory allocation of its data elements. It is important to note that in this method, the queue acquires all the features of an array.
2. Dynamically: Linked list implementation of queues follow the dynamic memory allocation of its data elements. It is important to note that in this method, the queue inherits all the characteristics of a linked list.

Key takeaway: Both stacks and queues in C can be static or dynamic according to the way they are implemented.

2.1 Array Implementation of Queue in C

As we already discussed, arrays support the static memory allocation of the data elements of the queue. Therefore, it is important to determine the size of the queue prior to the program run.

It’s the right time to uncover the secrete of Multi-dimensional Arrays in C

The queue functions basically include:

2.1.1 Insertion

Insertion of elements into the queue takes place from the rear end. Inserting an element into the queue is also called enqueue.

Here is a diagrammatic representation of how elements are inserted into a queue:

This is how can insert elements into the queue in C:

void insert()
{
int element;
if (rear == LIMIT - 1)
printf("Queue Overflow\n");
else
{
if (front == - 1)
front = 0;
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
rear++;
queue[rear] = element;
}
}

2.1.2 Deletion

In a queue, the removal of data elements is done from the front. Removing the element from the queue is also called dequeue.

Here is a diagrammatic representation of how elements are deleted from a queue in C:

This is how we can delete elements from the queue:

void delet()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
}
else
{
printf("The deleted element in the queue is: %d\n", queue[front]);
front++;
}
}

Key takeaway: It is important to note that we used the function name “delet” instead of “delete” because “delete” is a keyword.

2.1.3 Display

The stack data elements are displayed in the queue according to the FIFO rule.

This is how we display all the elements in the queue in C:

void display()
{
int i;
if (front == - 1)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the queue are:\n");
for (i = front; i <= rear; i++)
printf("%d\n", queue[i]);
}
}

Similarly, in queues, apart from these 3 main functions, it is necessary to check the overflow and underflow conditions to avoid unfavorable situations.

Here is a code in C that illustrates the array implementation of queues in C:

#include <stdio.h>
#include <stdlib.h>
#define LIMIT 100 // Specifying the maximum limit of the queue

/* Global declaration of variables */

int queue[LIMIT]; // Array implementation of queue
int front, rear; // To insert and delete the data elements in the queue respectively
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations

void insert(); // Function used to insert the element into the queue
void delet(); // Function used to delete the elememt from the queue
void display(); // Function used to display all the elements in the queue according to FIFO rule

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

printf ("ARRAY IMPLEMENTATION OF QUEUES\n\n");
front = rear = -1; // Initialzing front and rear to -1 indicates that it is empty
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void insert()
{
int element;
if (rear == LIMIT - 1)
printf("Queue Overflow\n");
else
{
if (front == - 1)
front = 0;
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
rear++;
queue[rear] = element;
}
}

void delet()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
}
else
{
printf("The deleted element in the queue is: %d\n", queue[front]);
front++;
}
}

void display()
{
int i;
if (front == - 1)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the queue are:\n");
for (i = front; i <= rear; i++)
printf("%d\n", queue[i]);
}
}

Output-

2.2 Linked List Implementation of Queue in C

As we already discussed, linked lists support the dynamic memory allocation of the data elements of the queue. Therefore, the size of the queue is allocated during the program run and needn’t be specified beforehand.

The 3 basic operations of Insertion, Deletion, and Display follow a similar trend as we saw in the array implementation of queues.

It is important to note that the condition of queue overflow does not exist in the linked list implementation of queues and the size of the stack is not pre-determined. But, the queue underflow condition still holds true.

2.2.1 Insertion

This is how we can insert elements into the queue:

void insert()
{
struct node *temp;

temp = (struct node*)malloc(sizeof(struct node));
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &temp->data);
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}

2.2.2 Deletion

This is how the deletion is done in a queue:

void delet()
{
struct node *temp;
temp = front;
if (front == NULL)
{
printf("Queue underflow\n");
front = rear = NULL;
}
else
{
printf("The deleted element from the queue is: %d\n", front->data);
front = front->link;
free(temp);
}
}

2.2.3 Display

This is how we display the elements in the queue

void display()
{
struct node *temp;
temp = front;
int cnt = 0;
if (front == NULL)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while (temp)
{
printf("%d\n", temp->data);
temp = temp->link;
cnt++;
}
}
}

Here is a code in C that illustrates the linked list implementation of queues in C:

#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *link;
}*front, *rear;

void insert(); // Function used to insert the element into the queue
void delet(); // Function used to delete the elememt from the queue
void display(); // Function used to display all the elements in the queue according to FIFO rule

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

int choice;
printf ("LINKED LIST IMPLEMENTATION OF QUEUES\n\n");
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void insert()
{
struct node *temp;

temp = (struct node*)malloc(sizeof(struct node));
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &temp->data);
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}

void delet()
{
struct node *temp;
temp = front;
if (front == NULL)
{
printf("Queue underflow\n");
front = rear = NULL;
}
else
{
printf("The deleted element from the queue is: %d\n", front->data);
front = front->link;
free(temp);
}
}

void display()
{
struct node *temp;
temp = front;
int cnt = 0;
if (front == NULL)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while (temp)
{
printf("%d\n", temp->data);
temp = temp->link;
cnt++;
}
}
}

Output-

2.3 Circular Queue in C

The role of circular queue comes into play when we wish to avoid the loss of computer memory using arrays. It is based on the principle that the rear end of the queue becomes equal to its front end.

Here is a diagrammatic representation of how a circular queue looks like:

The circular queue operations are the same as that of a linear queue, that is, insertion, deletion and display and checking of boundary conditions such as overflow and underflow.

We have discussed the 3 basic operations in detail:

2.3.1 Insertion

This is how we insert elements in the circular queue:

void insert()
{
if((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
printf("Queue Overflow\n");
}
if (front == -1) //If queue is empty
{
front = rear = 0;
}
else
{
printf("Enter the element to be inserted in queue: ");
scanf("%d", &item);
if(rear == LIMIT-1) // When rear is at the last position of the queue
{
rear = 0;
}
else
{
rear++;
}
}
cqueue[rear] = item ;
}

2.3.2 Deletion

This is how we delete elements in the circular queue in C:

void delet()
{
if (front == -1)
{
printf("Queue Underflow\n");
}
printf("Element deleted from queue is : %d\n",cqueue[front]);
if(front == rear) /* queue has only one element */
{
front = rear = -1;
}
else
{
if(front == LIMIT-1)
{
front = 0;
}
else
front++;
}
}

2.3.3 Display

This is we display elements in the circular queue:

void display()
{
int front_position = front;
int rear_position = rear;
if(front == -1)
{
printf("Queue underflow\n");
}
printf("The elements of the queue are:\n");
if( front_position <= rear_position )
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
else
{
while(front_position <= LIMIT-1)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
front_position = 0;
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
}
}

Here is a code in C that illustrates the implementation of a circular queue in C:

#include<stdio.h>
#include<stdlib.h>
#define LIMIT 10

/* Global declaration of variables */
int cqueue[LIMIT];
int choice, item;
int front, rear; 

void insert(); // Function to insert the element in the queue
void delet(); // Function to delete the element in the queue
void display(); // Function to display the element in the queue

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

printf ("ARRAY IMPLEMENTATION OF QUEUES\n\n");

front = rear = -1; // It indicates the queue is empty
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void insert()
{
if((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
printf("Queue Overflow\n");
}
if (front == -1)  //If the queue is empty 
{
front = rear = 0;
}
else
{
printf("Enter the element to be inserted in queue: ");
scanf("%d", &item);
if(rear == LIMIT-1) // When rear is at the last position of the queue 
{
rear = 0;
}
else
{
rear++;
}
}
cqueue[rear] = item ;
}

void delet()
{
if (front == -1)
{
printf("Queue Underflow\n");
}
if(front!= -1)
printf("Element deleted from queue is : %d\n",cqueue[front]);
if(front == rear) /* queue has only one element */
{
front = rear = -1;
}
else
{	
if(front == LIMIT-1)
{
front = 0;
}
else
front++;
}
}

void display()
{
int front_position = front;
int rear_position = rear;
if(front == -1)
{
printf("Queue underflow\n");
}
if(front!= -1)
printf("The elements of the queue are:\n");
if( front_position <= rear_position )
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
else
{
while(front_position <= LIMIT-1)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
front_position = 0;
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
}
}

Output-

2.4 Applications of Queue in C

The principle FIFO followed by queues gives birth to the various applications of queues. Some of the most popular applications of queues are:

• Round robin algorithm: The concept of queues finds a striking application in the round robin algorithm done in MBA.
• CPU Scheduling: In a queue, the data is not processed instantly, but processed according to the FIFO rule. Therefore, this feature of queues helps in the sharing of resources among multiple users at the same time.
• Input-Output Buffers: It helps in the transmission of asynchronous data (A condition where the retrieval of multiple data takes place at the user end at different rates) by converting it into synchronous data.

Summary

In this tutorial, we discussed the meaning of stacks and queues in C in detail. We saw how they are implemented using arrays and linked lists. Further, we discussed the three basic operations of both stacks and queues in C with the help of illustrative programs. We even introduced the concept of a circular queue. Finally, we concluded our discussion by stating the various real-world applications of stacks and queues in C. Stacks and queues are important concepts in every programming languages.

If you found this tutorial satisfying or if you have any queries regarding this topic, feel free to let us know your responses in the comment section below!

Build your Coding skills with these basic C Programs.