Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c
data structure
stack

How to implement a stack in C using an array

Educative Answers Team

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.

Implementation

The following code will implement three functions supported by a stack.

  • Push(a): It adds element a on top of the stack. It takes O(1)O(1) 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 O(1)O(1) time as the top contains the index of the most recently added element.
  • Top(): It returns the element on top of the stack. It takes O(1)O(1) time as finding the value stored at a particular index in an array is a constant time operation.

The following illustration will explain how the code works:

1 of 7
#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 empty
  if((*top) == stackSize - 1){
    (*top) = -1;
  }
  else{
    (*top)++;
  }
 }
}
int main() {
  int stackSize = 4;
  char stack[stackSize];
  // A negative index shows that the stack is empty
  int 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;
}

RELATED TAGS

c
data structure
stack
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring