Stack in C | Queue in C

C programming language offers various types of features and functionalities to the programmers. We learnt how to implement arrays and linked lists in C. So, In this tutorial, we are going to teach you a new and important concept of data structures which is Stack and Queues. Stack and Queue in C are very useful and efficient concept to learn.

What is Stack in C?

Stack is known as a linear data structure. It follows the Last-In-First-Out rule. So, if you push something to the stack then the last value which you pushed, will be the first to pop out. The insertion and deletion operation on the stack will only take place from one end which is the top of the stack.

In 2 ways, you can implement a stack in C.

1. Statically:- In C, you can implement a stack using an array. It allows static memory allocation of its data elements. In this, the stack inherits all the features of the array.

2. Dynamically:- You can also implement a stack using a linked list. It allows dynamic memory allocation of its data elements. In this, the stack takes over the characteristics of the linked list.

Implementing Stack in C using an array:-

In C, you can implement the stack using an array. And arrays support static memory allocation of its data elements. Before running the program code, you have to declare the size of the array in advance.

1. Insertion:-

The operation for inserting a value into the stack is known as push. If you push something to the stack, it will be added at the top of the stack.

Example of Inserting elements to the stack

#define SIZE 50
void push()
{
int stack[SIZE], top, num;
if(top == SIZE- 1)
{
printf("Please increase the size of the array! If you don't then the stack overflows!\n");
}
else
{
printf("TechVidvan Tutorial: Pushing a value to the stack!\n");
num = 20;
top++;
stack[top]=num;
}
}

2. Deletion in Stack:-

The operation for deleting a value from the stack is known as pop. In stack, you can only delete an element from the top of the stack.

Example of Deleting an element from the stack using C

#define SIZE 50
void pop()
{
int stack[SIZE], top, num;
if(top == -1)
{
printf("The Stack is empty\n"); // Stack Underflow!
}
else
{
num=stack[top];
printf("TechVidvan Tutorial: Popping an element from the stack!\n");
printf("Deleted the %d item.\n",stack[top]);
top--;
}
}

3. Display Stack Elements using C

Stack follows the Last-In-Fast-Out rule. And the data elements of the stack are displayed according to it.

Example of Displaying the elements of the stack

#define SIZE 50
void print()
{
int stack[SIZE], top, n;
if(top == -1)
{
printf("The stack is empty!\n"); // Stack Underflow!
}
else if(top > 0)
{
printf("Elements of the stack are:\n");
for(n = top; n >= 0; n--)
{
printf("%d\n",stack[n]);
}
}
}

Stack Overflow:-

If the size of the array is exceeding its limit, then stack overflow occurs. If the stack is completely filled with the elements, you cannot insert any element into the stack. Still if you do then you will face stack overflow. Arrays support static memory allocation of its data elements.

Stack Underflow:-

If you are displaying the elements of a stack or performing the deletion operation on a stack but the stack is empty then this situation is called Stack Underflow.

Example of Array Implementation of Stack in C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

int stack[SIZE];
int top;
int a;
int your_choice;

void push();
void pop();
void print();

int main()
{

printf("TechVidvan Tutorial: Array Implementation of Stack in C!\n\n");
top = -1; // indicating that the stack is empty!
do
{
printf("1. Insert an Element!\n2. Delete an Element!\n3. Display the elements of the stack!\n4. Please Exit!\n\n");
printf("Enter your choice from the above: ");
scanf("%d",&your_choice);
switch(your_choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
print();
break;
case 4:
exit(0);
break;
default:
printf("Soory, Please enter a valid choice!\n");
break;
}
}while(your_choice!=4);
return 0;
}
void push()
{
int value;
if(top == SIZE- 1)
{
printf("The Stack is empty!\n");
}
else
{
printf("Enter the element to push into the stack: ");
scanf("%d", &value);
printf("Element added!\n");
top++;
stack[top]=value;
}
}
void pop()
{
int value;
if(top == -1)
{
printf("The Stack is empty!\n");
}
else
{
value=stack[top];
printf("Deleted the element: %d\n",stack[top]);
print("Deleted!\n");
top--;
}
}

void print()
{
if(top == -1)
{
printf("The Stack is empty!\n");
}
else if(top > 0)
{
printf("Elements of the stack are: \n");
for(a = top; a >= 0; a--)
{
printf("%d\n",stack[a]);
}
}
}

Output:-

Implementing stack in C using a Linked List:-

Linked Lists provide dynamic memory allocation of its data elements. In this method, you do not have to declare the size of the stack in advance. You can perform the basic three operations on it such as Insertion, Deletion and Display.

1. Insertion in Stack using Linked List:-

You can insert an element into the stack through a linked list.

Example of Inserting an element into the stack

void push()
{
int value;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("The Stack is Full!\n");
}
else
{
printf("Enter the element which you want to insert: ");
scanf("%d",&value);
if(tmp == NULL)
{
ptr -> value = value;
ptr -> next = NULL;
tmp = ptr;
}
else
{
ptr -> value = ptr;
ptr -> next = tmp;
tmp = ptr;
}
}
}

2. Deletion of Stack element using linked list

You can also delete an element from the stack.

Example of Deleting an element from the stack

void pop()
{
int element;
struct node *ptr;
if (tmp == NULL)
{
printf("The Stack is empty!\n");
}
else
{
element = temp -> value;
ptr = tmp;
tmp = tmp -> next;
free(ptr);
printf("Deleted the element: %d\n",element);
}
}

3. Display Stack Elements

If you want to display the elements of the stack then follow the below code.

void print()
{
int a;
struct node *ptr;
ptr = tmp;
if(ptr == NULL)
{
printf("The Stack is empty!\n");
}
else
{
printf("Elements of the stack are: \n");
while(ptr!= NULL)
{
printf("%d\n",ptr -> value);
ptr = ptr -> next;
}
}
}

Example of Stack Implementation using Linked Lists

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

void push();
void pop();
void print();
struct node
{
int value;
struct node *NEXT;
};
struct node *tmp;

int main()
{

printf("TechVidvan Tutorial: Stack Implementation using Linked Lists!\n\n");
int your_choice;
do
{
printf("1. Insert an element!\n2. Delete an element!\n3. Display the elements of the stack!\n4. Please Exit!\n\n");
printf("Please enter your choice from the above: ");
scanf("%d",&your_choice);

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

void push()
{
int value;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("The Stack is full!\n");
}
else
{
printf("Enter the element which you want to push into the stack: ");
scanf("%d",&value);
printf("Element added!\n");
if(tmp == NULL)
{
ptr -> value = value;
ptr -> NEXT = NULL;
tmp = ptr;
}
else
{
ptr -> value = value;
ptr -> NEXT = value;
tmp = ptr;
}
}
}

void pop()
{
int element;
struct node *ptr;
if (tmp == NULL)
{
printf("The Stack is empty!\n");
}
else
{
element = tmp -> value;
ptr = tmp;
tmp = tmp -> NEXT;
free(ptr);
printf("Deleted the element: %d\n",element);
printf("Deleted!\n");
}
}
void print()
{
int a;
struct node *ptr;
ptr = tmp;
if(ptr == NULL)
{
printf("The Stack is empty!\n");
}
else
{
printf("Elements of the stack are: \n");
while(ptr!= NULL)
{
printf("%d\n",ptr->value);
ptr = ptr -> NEXT;
}
}
}

Output:-

Applications of Stack in C:-

1. Number Reversing:- You can easily reverse a sequence of characters or digits.

2. Undo Operation:- In text editors, you can see an undo operation. If you click it then all the changes you made will go back to normal. All the changes are stored into the stack.

3. Infix to Postfix Conversion: With the help of stacks, you can convert from infix to postfix.

4. Backtracking:- You can use stacks to solve various maze puzzling problems.

5. Depth First Search:– With the help of stacks, you can perform a searching algorithm named Depth-First Search.

What is a Queue in C?

Queue is known as a linear data structure. It follows the First-In-First-Out rule. So, if you push something to the stack then the first value of the stack will pop out. In the queue, the insertion operation is done from the rear end(back) and the deletion is done from the front.

In 2 ways, you can implement the queue in C.

1. Statically:- In C, you can implement a queue using an array. It allows static memory allocation of its data elements. In this, the queue inherits all the features of the array.

2. Dynamically:- You can also implement a queue using a linked list. It allows dynamic memory allocation of its data elements. In this, the queue takes over the characteristics of the linked list.

NOTE:- You can implement both stacks and queues statically or dynamically. It depends on you.

Implementing Queue in C using an array:-

You can implement the queue using an array in C. And arrays support static memory allocation of its data elements. Before running the program code, you have to declare the size of the array in advance.

In the queue, you can perform three basic operations such as insertion, deletion and display.

1. Insertion in Queue using C

In the queue, you can insert an element from the rear end of the queue. In queue, insertion of an element is called enqueue.

Example of Inserting an element into the queue

void enqueue()
{
int value;
if (rear == SIZE - 1)
printf("The Queue is full!\n");
else
{
if (front == - 1)
front = 0;
printf("Enter the element which you want to insert into the queue: ");
scanf("%d", &value);
rear++;
queue[rear] = value;
}
}

2. Deletion of queue element using C

In the queue, you can only delete an element from the front of the queue. Deletion of an element from the queue is called dequeue.

Example of Deleting an element from the queue

void dequeue()
{
if (front == - 1 || front > rear)
{
printf("The queue is empty! \n");
}
else
{
printf("Deleted the element: %d\n", queue[front]);
front++;
}
}

3. Display Queue Element

In C, you can print the elements of the queue according to the FIFO rule.
Example:- Displaying the elements of the queue

void print()
{
int a;
if (front == - 1)
{
printf("The queue is empty!\n");
}
else
{
printf("Elements of the queue are: \n");
for (a = front; a <= rear; a++)
printf("%d\n", queue[a]);
}
}

Example:- Array implementation of queue

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

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

void enqueue();
void dequeue();
void print();

int main()
{

printf("TechVidvan Tutorial: Array implementation of Queue!\n\n");

int your_choice;
do
{

printf("1. Insert an element!\n2. Delete an element!\n3. Display the elements of the queue!\n4. Please Exit!\n\n");
printf("Enter your your_choice: ");
scanf("%d",&your_choice);

switch(your_choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
print();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, Please enter a valid choice!\n");
break;
}
} while(your_choice!=4);
return 0;
}

void enqueue()
{
struct node *tmp;

tmp = (struct node*)malloc(sizeof(struct node));
printf("Enter the element which you want to insert: ");
scanf("%d", &tmp->data);
printf("Element added!\n");
tmp->next = NULL;
if (rear == NULL)
{
front = rear = tmp;
}
else
{
rear->next = tmp;
rear = tmp;
}
}

void dequeue()
{
struct node *tmp;
tmp = front;
if (front == NULL)
{
printf("The queue is empty!\n");
front = rear = NULL;
}
else
{
printf("Deleted the element: %d\n", front->data);
printf("Deleted the element!\n");
front = front->next;
free(tmp);
}
}

void print()
{
struct node *tmp;
tmp = front;
int i = 0;
if (front == NULL)
{
printf("The queue is empty!\n");
}
else
{
printf("Elements of the stack are:\n");
while (tmp)
{
printf("%d\n", tmp->data);
tmp = tmp->next;
i++;
}
}
}

Output:-

Implementing queue using a Linked List:-

You can perform dynamic memory allocation of the data elements of the queue using linked lists. In this method, you do not have to declare the size of the queue in advance.
You can perform the basic three operations on it such as Insertion, Deletion and Display.
NOTE:- Queue overflow does not exist in the implementation of queues using linked lists.

1. Insertion in queue using Linked List

You can also insert an element to the queue using a linked list.

Example:- Inserting an element into the queue

void enqueue()
{
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
printf("Enter the element which you want to insert: ");
scanf("%d", &tmp->value);
tmp->next = NULL;
if (rear == NULL)
{
front = rear = tmp;
}
else
{
rear->next = tmp;
rear = tmp;
}
}

2. Deletion from queue using linked list

Below is the code to perform deletion on the queue using the linked list.

void dequeue()
{
struct node *tmp;
tmp = front;
if (front == NULL)
{
printf("The queue is empty!\n");
front = rear = NULL;
}
else
{
printf("Deleted the element: %d\n", front->value);
front = front->next;
free(tmp);
}
}

3. Display queue elements

You can also display the elements of the queue according to the FIFO rule.

Example:- Displaying the elements inside a queue

void print()
{
struct node *tmp;
tmp = front;
int i = 0;
if (front == NULL)
{
printf("The queue is empty!\n");
}
else
{
printf("Elements of the stack are: \n");
while (tmp)
{
printf("%d\n", tmp->value;
tmp = tmp->next;
i++;
}
}
}

Example:- Implementation of queue using the linked list

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

struct node
{
int value;
struct node *next;
}*front, *rear;

void enqueue();
void dequeue();
void print();
int main()
{

printf("TechVidvan Tutorial: Implementing queue using the linked list!\n\n");

int your_choice;
do
{

printf("1. Insert an element!\n2. Delete an element!\n3. Display the elements of the queue!\n4. Please Exit!\n\n");
printf("Enter a choice from the above ones: ");
scanf("%d",&your_choice);

switch(your_choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
print();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, You made an invalid choice!\n");
break;
}
} while(your_choice!=4);
return 0;
}

void enqueue()
{
struct node *tmp;

tmp = (struct node*)malloc(sizeof(struct node));
printf("Enter the element which you want to insert: ");
scanf("%d", &tmp->value);
printf("Element added!\n");
tmp->next = NULL;
if (rear == NULL)
{
front = rear = tmp;
}
else
{
rear->next = tmp;
rear = tmp;
}
}

void dequeue()
{
struct node *tmp;
tmp = front;
if (front == NULL)
{
printf("The queue is empty!\n");
front = rear = NULL;
}
else
{
printf("Deleted the element: %d\n", front->value);
printf("Deleted the element!\n");
front = front->next;
free(tmp);
}
}

void print()
{
struct node *tmp;
tmp = front;
int i = 0;
if (front == NULL)
{
printf("The queue is empty!\n");
}
else
{
printf("Elements of the queue are:\n");
while (tmp)
{
printf("%d\n", tmp->value);
tmp = tmp->next;
i++;
}
}
}

Output:-

Circular Queue:-

In the circular queue, the rear end of the queue is equal to the front end of that queue. Using a circular queue, you can avoid the loss of computer memory.

Like the linear queue, you can perform basic operations such as insertion, deletion and displaying the elements of the queue.

1. Insertion in circular queue

In the circular queue, you can insert an element into the queue.

Example:- Inserting an element into the circular queue

void enqueue()
{
if((front == 0 && rear == SIZE-1) || (front == rear+1))
{
printf("The queue is Full!\n");
}
if (front == -1)
{
front = rear = 0;
}
else
{
printf("Enter the element to insert: ");
scanf("%d", &value);
if(rear == SIZE-1)
{
rear = 0;
}
else
{
rear++;
}
}
circular_queue[rear] = value;
}

2. Deletion from Circular Queue

In the circular queue, you can also delete an element from it.

Example:- Deleting an element from the circular queue

void dequeue()
{
if (front == -1)
{
printf("The queue is empty!\n");
}
printf("Deleted the element: %d\n",circular_queue[front]);
if(front == rear)
{
front = rear = -1;
}
else
{
if(front == SIZE-1)
{
front = 0;
}
else
front++;
}
}

3. Display Circular Queue Elements

To display the elements from the circular queue, you can follow the code below:-
Example:- Displaying the elements of the circular queue

void print()
{
int begin_pos = front;
int end_pos = rear;
if(front == -1)
{
printf("The queue is empty!\n");
}
printf("Elements of the queue are:\n");
if( begin_pos <= end_pos )
while(begin_pos <= end_pos)
{
printf("%d\n",circular_queue[begin_pos]);
begin_pos++;
}
else
{
while(begin_pos <= SIZE-1)
{
printf("%d\n",circular_queue[begin_pos]);
begin_pos++;
}
begin_pos = 0;
while(begin_pos <= end_pos)
{
printf("%d\n",circular_queue[begin_pos]);
begin_pos++;
}
}
}

Example:- Array Implementation of the circular queue

#include<stdio.h>
#include<stdlib.h>
#define SIZE 20

int circular_queue[SIZE];
int your_choice, value;
int begin_pos, end_pos;

void enqueue();
void dequeue();
void print();

int main()
{

printf("TechVidvan Tutorial: Array Implementation of the circular queue!\n\n");

begin_pos = end_pos = -1;
do
{

printf("1. Insert an element!\n2. Delete an element!\n3. Display the elements from the circular queue!\n4. Please Exit!\n\n");
printf("Enter any choice from above: ");
scanf("%d",&your_choice);

switch(your_choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
print();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid your_choice!\n");
break;
}
} while(your_choice!=4);
return 0;
}

void enqueue()
{
if((begin_pos == 0 && end_pos == SIZE-1) || (begin_pos == end_pos+1))
{
printf("The queue is full!\n");
}
if (begin_pos == -1)  
{
begin_pos = end_pos = 0;
}
else
{
printf("Enter the element which you want to insert: ");
scanf("%d", &value);
printf("Element added!\n");
if(end_pos == SIZE-1)
{
end_pos = 0;
}
else
{
end_pos++;
}
}
circular_queue[end_pos] = value ;
}

void dequeue()
{
if (begin_pos == -1)
{
printf("The queue is empty!\n");
}
if(begin_pos!= -1)
printf("Deleted the element: %d\n",circular_queue[begin_pos]);
printf("Element Deleted!\n");
if(begin_pos == end_pos)
{
begin_pos = end_pos = -1;
}
else
{  
if(begin_pos == SIZE-1)
{
begin_pos = 0;
}
else
begin_pos++;
}
}

void print()
{
int position_at_beginning = begin_pos;
int position_at_end = end_pos;
if(begin_pos == -1)
{
printf("The queue is empty!\n");
}
if(begin_pos!= -1)
printf("Elements of the queue are: \n");
if( position_at_beginning <= position_at_end )
while(position_at_beginning <= position_at_end)
{
printf("%d\n",circular_queue[position_at_beginning]);
position_at_beginning++;
}
else
{
while(position_at_beginning <= SIZE-1)
{
printf("%d\n",circular_queue[position_at_beginning]);
position_at_beginning++;
}
position_at_beginning = 0;
while(position_at_beginning <= position_at_end)
{
printf("%d\n",circular_queue[position_at_beginning]);
position_at_beginning++;
}
}
}

Output:-

Applications of Queue in C:-

There are various applications of queue. Some of the applications of queue:-

1. Round robin algorithm:- Using the queue, you can perform the round robin algorithm.

2. CPU Scheduling:- With the help of a queue, you can share resources among multiple users at the same time. In a queue, data is processed according to the First-In-First-Out rule.

3. Input-Output Buffers:- Using a queue, you can convert the asynchronous data to synchronous data.

Difference between Stack and Queue:-

Summary

In this tutorial, we learnt what stack and queue in C are. We also discussed how to implement a stack and a queue using arrays and linked lists in detail. We also discussed three basic operations which you can perform on both stack and queue. Then we talked about another type of queue named circular queue. We discussed some important applications of both stack and queue. We also talked about the difference between stack and queue.