How to implement a stack in C using an array
A stack is a linear data structure that follows the Last in, First out principle (i.e. the last added elements are removed first).
This abstract data type can be implemented in C in multiple ways. One such way is by using an array.
Pro of using an array:
- No extra memory required to store the pointers.
Con of using an array:
- The size of the stack is pre-set so it cannot increase or decrease.
Stack using an Array
The following methods are implemented to push an element, remove an element and take the element at the top of the array:
- Push(a): It adds element a on top of the stack. It takes time as each element is inserted starting from the table of the array; there is no need to shift existing elements to make room for the new element.
- Pop(): It removes the element on top of the stack. It also takes time as the
topcontains the index of the most recently added element. - Top(): It returns the element on top of the stack. It takes time as finding the value stored at a particular index in an array is a constant time operation.
Let’s see a visual description of how a Stack works.
Code
The following code explains how to implement a stack in C using an array:
#include<stdio.h>void push(char element, char stack[], int *top, int stackSize){if(*top == -1){stack[stackSize - 1] = element;*top = stackSize - 1;}else if(*top == 0){printf("The stack is already full. \n");}else{stack[(*top) - 1] = element;(*top)--;}}void pop(char stack[], int *top, int stackSize){if(*top == -1){printf("The stack is empty. \n");}else{printf("Element popped: %c \n", stack[(*top)]);// If the element popped was the last element in the stack// then set top to -1 to show that the stack is emptyif((*top) == stackSize - 1){(*top) = -1;}else{(*top)++;}}}int main() {int stackSize = 4;char stack[stackSize];// A negative index shows that the stack is emptyint top = -1;push('a', stack, &top, stackSize);printf("Element on top: %c\n", stack[top]);push('b',stack, &top, stackSize);printf("Element on top: %c\n", stack[top]);pop(stack, &top, stackSize);printf("Element on top: %c\n", stack[top]);pop(stack, &top, stackSize);printf("Top: %d\n", top);pop(stack, &top, stackSize);return 0;}
Test your knowledge!
Write a C program to reverse a string using a stack data structure. The program should take this string Educative and utilize a stack to reverse the order of characters in the string. Please use the widget provided below to write the program and execute the program by clicking on the "Run" button.
Note: If you feel stuck at any point click the "Solution" button to see the solution of the problem.
#include<stdio.h>void push(char element, char stack[], int *top, int stackSize){if(*top == -1){stack[stackSize - 1] = element;*top = stackSize - 1;}else if(*top == 0){printf("The stack is already full. \n");}else{stack[(*top) - 1] = element;(*top)--;}}void pop(char stack[], int *top, int stackSize){if(*top == -1){printf("The stack is empty. \n");}else{printf("Element popped: %c \n", stack[(*top)]);// If the element popped was the last element in the stack// then set top to -1 to show that the stack is emptyif((*top) == stackSize - 1){(*top) = -1;}else{(*top)++;}}}void reverseString(char str[], int length) {int stackSize = length;char stack[stackSize];// ADD YOUR CODE HERE}int main() {char str[] = "hello";int length = sizeof(str) / sizeof(str[0]) - 1; // excluding the null terminatorprintf("Original string: %s\n", str);reverseString(str, length);return 0;}
RELATED TAGS
