In this blog post, we will be learning, implementing, and having a thorough introduction to stacks data structure using the C programming language.
Before understanding the stacks data structure, you should have a good understanding of arrays and linked lists because only with the help of these two data structures can we implement stacks.
In general, for implementing any data structure, whether it is stacks, queues, trees, etc., we have to use either arrays or a linked list.
If you can predict the size of the data structure (how much memory it will need) then you can use an array, otherwise, you can dynamically allocate the memory using linked lists.
Concept of Stacks Data structure
Consider a stack as a series of plates kept one above the other, vertically, from bottom to top.
Letâs say there are five plates, P1, P2, P3, P4, and P5, and you want to organize them in the form of a stack (i.e. putting them one above the other), then how would you do it?
Obviously, you will take the first plate, P1, and on top of it, you will put the plate P2, and then the next plate, and so on, until you put the last plate on, i.e. P5.
This whole thing forms a stack of plates which is illustrated by the following diagram.
And, whenever you want to access or take out a particular plate, you have to first see if the plate you want to access is at the top or not.
A stacks data structure is also known as last-in-first-out (LIFO) meaning the element which is inserted last into the stack will be removed first from the stack.
Operations on the Stack
Implementation of a Stack
There are two ways in which we can implement the stacks data structure.
Using an array
In this representation, we will be implementing the stack using an array whose index starts with 0.
Before inserting or deleting an element, there are two conditions that we have to check, the first is the overflow condition and the second is the underflow condition.
The overflow condition simply checks whether the stack is full or not. If it is already full, then you canât insert a new element on to the stack.
The underflow condition checks whether the stack is empty or not because if the stack is already empty and if we are trying to delete an element that does not even exist as the stack is already empty, we will definitely get an error.
These are some corner case conditions that we have to check to make sure that our program works perfectly in any situation without any errors.
void push (int item) {
if (top == MAX - 1) {
printf(âOverflow! The Stack is already full.â);
}
else {
top = top + 1;
Stack[top] = item;
}
}
int pop () {
int temp;
if (top == -1) {
printf(âUnderflow! The stack is already empty.â);
return -1;
}
else {
temp = stack[top];
top = top â 1;
}
return temp;
}
In the stack, when we pop an element, we are not actually deleting the element from the stack as we do in a linked list. Here, we are only decrementing the top pointer and the value inside that particular stack block will still be there.
The time complexity for both insertion and deletion of an element in an array takes O(1), i.e. constant time.
Using the linked list
In this representation, we will be implementing the stack data structure using a linked list.
As we know, the linked list consists of various nodes and each node has two things. One is the data and the other is the pointer that points to the next node.
But, before inserting an element, we first have to create a new node and then add that node to a linked list. Here, also, we have to check the overflow and underflow conditions.
struct node {
int i;
struct node *link;
};
void push (int item) {
struct node *p = (struct node *) malloc(sizeOf(struct node));
if (p == NULL) {
printf("Error of malloc.");
return;
}
p -> data = item;
p -> link = head;
head = p;
}
void pop () {
int item;
struct node *p;
if (head == NULL) {
printf("Underflow");
return -1;
}
item = head -> i;
p = head;
head = head -> next;
free(p);
}
The time complexity for both insertion and deletion of an element in a linked list also takes O(1), i.e. constant time.
