Implementation of Stack Using Array in C
![C++ Course: Learn the Essentials](https://www.scaler.com/topics/images/instructor-prateek.webp)
Overview
A stack is a linear data structure that follows LIFO(Last In First Out) approach, which means the element added at last in the stack will be removed first and the specific order can't be changed
The stack can be implemented in multiple ways. In this article, we will see stack implementation using array in c.
The basic operations of stack are PUSH() and POP()
In stack implementation using array in c, we will do all the operations of the stack data structure using an array. The operations include:
- push(a): Adding a element at the top of the stack in O(1) time.
- pop(): Removing the top element from the stack in O(1) time.
- peak(): Accessing the top element of the stack by returning it in O(1) time.
Adding an element onto the stack (push operation)
Adding a new element at the top of the stack is known as the push operation. Push operation executes in two steps:
Step 1: Increment the variable top (the pointer that points to the top of the stack). Now it will point to a new memory location.
Step 2: Add the new element at the updated top, the new memory location. And increase the size of the stack.
Note: Push operation can cause stack overflow condition if we try to perform push operation on an already full stack.
Algorithm
Time Complexity
Push operation in stack happens in O(1) time.
Implementation of Push Algorithm in C Language
In the above code, through if-else we are first checking whether the stack array is full or not. If the stack is full, the program will print overflow. Otherwise, it will increase the top and will add a new element in that position.
Deletion of an element from a stack (Pop operation)
Retrieving the value while removing it from the top of the stack, is known as a pop operation. In an array implementation of pop() operation in the stack data structure, the data element is not removed, instead, the top pointer is decremented to a lower position in the stack to point to the next value, and simultaneously the size is decreased.
The pop function will return this removed value.
Note: Underflow condition can occur in pop operation if we try to perform a pop operation on an empty stack.
Algorithm
Time Complexity
Pop operation in stack happens in O(1)
Implementation of Pop Algorithm in C Language
In the above code, through if-else we are first checking whether the stack array is empty or not. If the stack is empty, the program will print underflow. Otherwise, it will decrement the top and will delete the top element from the stack.
Visiting each element of the stack (Peek operation)
In peek operation we return the element which is present at the top of the stack without deleting it. If we try to iterate over an empty stack then the stack underflow condition occurs.
Algorithm
Time Complexity
Peek operation in stack happens in O(1) time.
Implementation of Peek Algorithm in C Language
In the above code, firstly we are checking whether the stack is empty or not. If the stack is empty, the program will print underflow and will return zero. Otherwise, it will return the top element of the stack.
C Program for STACK Using Arrays
In this code, we are combining all the three operations we discussed above. Using switch cases we are giving the user the functionality to select the option of operation to perform on the stack. This is how we implement stack using array in C.
A shorter code version for real-time implementation of stack data structure in C language
Conclusion
In this article, we saw stack implementation using array in c. Using an array to implement stack data structures and their operations have its pros and cons. Let's a few of them in brief:
-
Pros:
- No extra space is required to save pointers when we use the array.
-
Cons:
- As we need to predefine the size of the array, the size of the stack cannot be increased or decreased.
Time complexity-wise also stack data structure is very efficient. It does push, pop, and peek operations in just O(1) time.