Implementation of Stack Using Array in C
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the most recently added element is the first one to be removed. In this article, we will learn how to implement a stack using an array in C.
Implementation of Stack Using Arrays in C
In the array-based implementation of a stack, we use an array to store the stack elements. The top of the stack is represented by the end of the array. Hence, we keep an index pointer named top. We can also enclose this array and index pointer in the structure data type.
Representation of Array Stack in C
typedef struct stack {
int top;
int capacity;
type* arr;
}Stack;
Here, we typedef is used for convenience for shorter struct declaration. It is recommended to define the array as the last element as to avoid overwriting the top variable in case of out of bound writing of array. We can define the size of the array dynamically using desired value.
Initially, we set the top index pointer to -1 representing there are no elements in the stack. We can then implement the basic stack operation according to this representation.
The below illustration shows the working of array stack in C:
Implementation of Stack Operations in C
There are five basic stack operations:
Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
Push | Add one element to the top of stack. | O(1) | O(1) |
Pop | Delete one element from the top of stack. | O(1) | O(1) |
Peek | Return the top element. | O(1) | O(1) |
IsFull | Returns true is stack is full. If not, returns false. | O(1) | O(1) |
IsEmpty | Returns true is stack is empty. If not, returns false. | O(1) | O(1) |
1. isFull Implementation
The top pointer will always point to the index that have the current top element. So the stack full condition will be top is greater that or equal to the MAX_SIZE i.e. the size of the array.
Algorithm
- If top == capacity – 1, return true.
- Else, return false
2. isEmpty Implementation
We have set the top = -1 initially when there were no element. This will be true for whenever the stack is empty.
Algorithm
- If top == -1, return true.
- Else, return false
3. Push Implementation
The push operation will be performed at the top of the stack. The top variable points to the current top element, so we need to increment it to insert the new element the top. But before, we need to check whether the given stack is full or not. Pushing an element while the stack is full is called stack overflow.
Algorithm
- If stack is full, print stack overflow and return.
- Else, increment the top and insert the new element at arr[top].
4. Pop Implementation
The pop operation is also performed at the top. But in array, we cannot remove the element directly. So, we just decrement the top pointer effectively removing the current top element. But removing element from the stack that is empty leads to the stack underflow condition.
- If the stack is empty (top == -1), print “stack underflow” and return.
- Otherwise, decrement the top.
5. Peek Implementation
The peek operation returns the top element of the stack without removing it. We can access the top element as arr[top].
Algorithm
- If the stack is empty, print “Stack is Empty!” and return -1.
- Else, return arr[top].
C Program to Implement Stack Using Arrays
// C Program to implement stack along with its basic
// operation using arrays
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// A structure to represent a stack
struct Stack {
int top;
int capacity;
int* array;
};
// Function to create a stack of given capacity. It
// initializes size of stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array
= (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
return stack->top == stack->capacity - 1;
}
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
if (isFull(stack)) {
printf("Overflow\n");
return;
}
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}
// Function to remove an item from stack. It decreases top
// by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack)) {
printf("Underflow\n");
return INT_MIN;
}
return stack->array[stack->top--];
}
// Function to return the top from stack without removing it
int peek(struct Stack* stack)
{
if (isEmpty(stack)) {
printf("Stack is empty\n");
return INT_MIN;
}
return stack->array[stack->top];
}
// Function to display stack elements
void display(struct Stack* stack)
{
if (isEmpty(stack)) {
printf("Stack is empty\n");
}
else {
for (int i = stack->top; i >= 0; i--) {
printf("%d\n", stack->array[i]);
}
}
}
// Driver program to test above functions
int main()
{
struct Stack* stack = createStack(100);
push(stack, 1);
push(stack, 2);
push(stack, 3);
printf("%d popped from stack\n", pop(stack));
printf("Top element is %d\n", peek(stack));
printf("Elements present in stack:\n");
display(stack);
return 0;
}
Output
1 pushed to stack 2 pushed to stack 3 pushed to stack 3 popped from stack Top element is 2 Elements present in stack: 2 1
Advantages of Array Implementation of Stack in C
- It is very easy to implement the stack using array.
- The insertion and deletion at the end of the array is very fast and efficient, so the push and pop are more efficient in this implementation.
Limitation of Array Implementation of Stack in C
- The size of the array is fixed and cannot be changed once defined. Even if we define the array using dynamic memory location, we still will need to create another array and copy the current elements to increase/decrease the size.
Other Implementations of Stack
Apart from the array, we can also implement the stack in the following ways:
Contact Us