Talk about data structures. Stack and queue data structures come to mind instantly because of their simplicity and their ease of operation in terms of time complexity and space complexity.
Both stack and queue follow linear data structure, so they use simple array or you can also use linked lists to implement them.
In this short blog, we will be discussing the logic and implementation of both stack and queue in C.
Let’s jump into the discussion of stack and queue with C.
What Will You Learn?
Stack Data Structure
Stack is a linear data structure that follows the LIFO principle which stands for Last in First out. The last element to be inserted in the stack will be the first element that will be popped out.
One real life example will be a stack of plates. The plate that you have last put in will be the first plate that you will be removing.
One concept that you need to know before we dive into the implementation of Stack is the top variable.
In the implementation of stack, top will be the position of the top of the stack. It is pointing to the item that will be popped and if you push any item, we will increase the top and push at the current top.
To implement stack you need some of the methods that will help you with the full implementation of stacks which are as follows –
- Initializing the stack.
- Checking whether the stack is empty.
- Checking whether the stack is full.
- Pushing elements to the stack.
- Popping elements from the stack.
- Peeking into the stack.
Initialize the stack
At first when we are implementing the stack, we need to first look at the structure of the stack that consists of a data which is an array, and another part is the top.
At first, we will initialize top as -1.
#define MAX 100
typedef struct
{
int data[MAX];
int top;
} Stack;
void init(Stack *s)
{
s->top = -1;
}Checking whether the stack is empty
We can check whether the stack is empty by checking the value of top as one. If the top value is -1, then it means the stack is empty because that’s how we initialized it at first.
int isEmpty(Stack *s)
{
return s->top == -1;
}Checking whether the stack is full
We can check whether the stack is full or not by checking if top is pointing to the last index of data which has the maximum index of `MAX-1`. If the value of top is equal to MAX-1. If that is the case then we return true.
int isFull(Stack *s)
{
return s->top == MAX - 1;
}Pushing elements to the stack
If we want to push elements to the stack, we have to increase the value of top by 1 and then push the value at top so that we can be sure that the element that is pushed is the topmost element.
void push(Stack *s, int item)
{
if (isFull(s))
{
printf("Stack is full\n");
return;
}
s->data[++s->top] = item;
}Popping elements from stack
Element from the stack is just like how you push it. Instead of going forward you go in the backward direction.
What you just need to do is take the item that is pointed by the top, return it and before returning you just have to decrease the top value. So that virtually it would seem that you have deleted the previous top item.
Note the fact that 40 was not deleted from the stack, instead we just kind of forgot about it with pointing the top to somewhere else.
int pop(Stack *s)
{
if (isEmpty(s))
{
printf("Stack is empty\n");
return -1;
}
return s->data[s->top--];
}Peek into the stack
This operation in stack is not used much because this can also be achieved using pop. But still instead if you just want to look at what is present at the top of the stack without deleting any item then you can use the peek operation.
int peek(Stack *s)
{
if (isEmpty(s))
{
printf("Stack is empty\n");
return -1;
}
return s->data[s->top];
}Complete Code To Implement Stack in C
Following is the complete implementation of the stack –
#include <stdio.h>
#define MAX 100
typedef struct
{
int data[MAX];
int top;
} Stack;
void init(Stack *s)
{
s->top = -1;
}
int isEmpty(Stack *s)
{
return s->top == -1;
}
int isFull(Stack *s)
{
return s->top == MAX - 1;
}
void push(Stack *s, int item)
{
if (isFull(s))
{
printf("Stack is full\n");
return;
}
s->data[++s->top] = item;
}
int pop(Stack *s)
{
if (isEmpty(s))
{
printf("Stack is empty\n");
return -1;
}
return s->data[s->top--];
}
int peek(Stack *s)
{
if (isEmpty(s))
{
printf("Stack is empty\n");
return -1;
}
return s->data[s->top];
}
int main()
{
Stack s;
init(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
return 0;
}
Output:
30
20
10
Stack is empty
-1Queue Data Structure
A queue is another linear data structure that follows the First In First Out (FIFO) order of insertion and deletion.
It means that the element that is inserted first will be the first one to be removed and the element that is inserted last will be removed at last.
We will use the array data structure to store the elements. The insertion in the queue is done at the back of the queue and the deletion is done at the front. So we maintain two index pointers front and rear pointers to keep track of the front and back of the queue.
To implement the Queue in C, we need the following operations –
- Initialize the queue.
- Check if the queue is full or not.
- Check if the queue is empty or not.
- Insert in the queue.
- Delete from the queue.
- Take a peek at the queue.
Initialize the queue
We will initialize the queue with a `front` value of -1 and a `rare` value of 0. `front` is pointing at the position where we have the first data, in the case of empty queue it is -1, the `rear` will point to the position where we will insert a new value to the queue, so at first it will be 0.
#define MAX 100
typedef struct
{
int data[MAX];
int front;
int rear;
} Queue;
void init(Queue *q)
{
q->front = -1;
q->rear = 0;
}Check if the queue is full or not
If the queue is full or not, we can look at the rare value if it is equal to Max, which is the limit of the array that is the queue. Then we will say that the queue is full.
int isFull(Queue *q)
{
return q->rear == MAX;
}Check if the queue is empty or not
Whether the queue is empty or not, we will try to verify the values of front and if rear is one away from front, then it means the queue is empty.
You might be wondering why we can’t just check front as one or maybe rear as 0?
It depends on the kind of implementation you are following to create a queue. If your implementation supports this logic, then go ahead.
Right now, the implementation that we are following has the logic that if you insert some element then we are changing the rear value only and if we are deleting some value then we are changing the front value only.
int isEmpty(Queue *q)
{
return q->front == q->rear - 1;
}Insert in the queue
First check if the queue is empty or not, if empty then return. If not, then we need to insert the new element in the rear position and then increase the rear value.
void enqueue(Queue *q, int item)
{
if (isFull(q))
{
printf("Queue is full\n");
return;
}
q->data[q->rear] = item;
q->rear++;
}Delete from the queue
When we are trying to delete from the queue, we first check if the queue is empty or not. If it is empty, then we return. If it is not, then we increase the value of front.
void dequeue(Queue *q)
{
if (isEmpty(q))
{
printf("Queue is empty\n");
return -1;
}
q->front++;
}Peek at the queue
Picking at the queue means we are looking at the front element of the queue, so we just have to return the front element from the array. We also check whether the queue is empty or not. If it is then we return -1.
int peek(Queue *q)
{
if (isEmpty(q))
{
printf("Queue is empty\n");
return -1;
}
return q->data[q->front + 1];
}Complete Code To Implement Queue In C
The complete code for the queue implementation is here –
#include <stdio.h>
#define MAX 100
typedef struct
{
int data[MAX];
int front;
int rear;
} Queue;
void init(Queue *q)
{
q->front = -1;
q->rear = 0;
}
int isEmpty(Queue *q)
{
return q->front == q->rear - 1;
}
int isFull(Queue *q)
{
return q->rear == MAX;
}
void enqueue(Queue *q, int item)
{
if (isFull(q))
{
printf("Queue is full\n");
return;
}
q->data[q->rear] = item;
q->rear++;
}
void dequeue(Queue *q)
{
if (isEmpty(q))
{
printf("Queue is empty\n");
return;
}
q->front++;
}
int peek(Queue *q)
{
if (isEmpty(q))
{
printf("Queue is empty\n");
return -1;
}
return q->data[q->front + 1];
}
int main()
{
Queue q;
init(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("%d\n", peek(&q));
dequeue(&q);
printf("%d\n", peek(&q));
dequeue(&q);
printf("%d\n", peek(&q));
dequeue(&q);
return 0;
}
Output:
10
20
30
Queue is emptyConclusion
In C, there is no built-in data structure for queue and stack, so knowing how to implement them not only improves our efficiency in the language but also helps us to understand both data structures from the base.
Although the implementation is fairly simple and easy to understand, I would still recommend you implement it on your own and make sure you get the overall tiny details of both stack and queue.
Liked this blog? Read the next blog from here.
References:
