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.
Resources Recommended for Data Structures and Algorithms
- Cracking the Coding Interview: 189 Programming Questions and Solutions by Gayle Laakmann McDowell.
- Introduction to Algorithms by Thomas H. Cormen.
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.
Let’s say we want to access P3, then before reaching the plate P3, you first have to remove the plates P5 and P4 from the stack.
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
- Push: To insert an element on to the stack.
- Pop: To delete an element from the stack.
Implementation of a Stack
There are two ways in which we can implement the stacks data structure.
1. 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.
Here, the toppointer keeps track of the topmost location of the stack. If the value of the top pointer is -1 then it represents that the stack is empty. This point is also applicable to the linked list representation of stack.
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.
2. 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.
The time complexity for both insertion and deletion of an element in a linked list also takes O(1), i.e. constant time.
Thanks for reading and if you like the content then support us on Patreon. Your support will surely help us in writing more of such content.