Tutorial

How To Implement a Stack in C Programming

Updated on December 13, 2022
Default avatar

By Safa Mulani

How To Implement a Stack in C Programming

Introduction

A stack is a linear data structure, a collection of items of the same type.

In a stack, the insertion and deletion of elements happen only at one endpoint. The behavior of a stack is described as “Last In, First Out” (LIFO). When an element is “pushed” onto the stack, it becomes the first item that will be “popped” out of the stack. In order to reach the oldest entered item, you must pop all the previous items.

In this article, you will learn about the concept of stack data structure and its implementation using arrays in C.

Operations Performed on Stacks

The following are the basic operations served by stacks.

  • push: Adds an element to the top of the stack.
  • pop: Removes the topmost element from the stack.
  • isEmpty: Checks whether the stack is empty.
  • isFull: Checks whether the stack is full.
  • top: Displays the topmost element of the stack.

Underlying Mechanics of Stacks

Initially, a pointer (top) is set to keep the track of the topmost item in the stack. The stack is initialized to -1.

Then, a check is performed to determine if the stack is empty by comparing top to -1.

As elements are added to the stack, the position of top is updated.

As soon as elements are popped or deleted, the topmost element is removed and the position of top is updated.

Implementing Stack in C

Stacks can be represented using structures, pointers, arrays, or linked lists.

This example implements stacks using arrays in C:

#include <stdio.h>

#include <stdlib.h>

#define SIZE 4

int top = -1, inp_array[SIZE];
void push();
void pop();
void show();

int main()
{
    int choice;

    while (1)
    {
        printf("\nPerform operations on the stack:");
        printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
        printf("\n\nEnter the choice: ");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            push();
            break;
        case 2:
            pop();
            break;
        case 3:
            show();
            break;
        case 4:
            exit(0);

        default:
            printf("\nInvalid choice!!");
        }
    }
}

void push()
{
    int x;

    if (top == SIZE - 1)
    {
        printf("\nOverflow!!");
    }
    else
    {
        printf("\nEnter the element to be added onto the stack: ");
        scanf("%d", &x);
        top = top + 1;
        inp_array[top] = x;
    }
}

void pop()
{
    if (top == -1)
    {
        printf("\nUnderflow!!");
    }
    else
    {
        printf("\nPopped element: %d", inp_array[top]);
        top = top - 1;
    }
}

void show()
{
    if (top == -1)
    {
        printf("\nUnderflow!!");
    }
    else
    {
        printf("\nElements present in the stack: \n");
        for (int i = top; i >= 0; --i)
            printf("%d\n", inp_array[i]);
    }
}

This program presents the user with four options:

  1. Push the element
  2. Pop the element
  3. Show
  4. End

It waits for the user to input a number.

  • If the user selects 1, the program handles a push(). First, it checks to see if top is equivalent to SIZE - 1. If true, "Overflow!!" is displayed. Otherwise, the user is asked to provide the new element to add to the stack.
  • If the user selects 2, the program handles a pop(). First, it checks to see if top is equivalent to -1. If true, "Underflow!!" is displayed. Otherwise, the topmost element is removed and the program outputs the resulting stack.
  • If the user selects 3, the program handles a show(). First, it checks to see if top is equivalent to -1. If true, "Underflow!!" is displayed. Otherwise, the program outputs the resulting stack.
  • If the user selects 4, the program exits.

Execute this code to push() the number "10"onto the stack:

Output
Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 1 Enter the element to be inserted onto the stack: 10

Then show() the elements on the stack:

Output
Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 3 Elements present in the stack: 10

Then pop():

Output
Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 2 Popped element: 10

Now, the stack is empty. Attempt to pop() again:

Output
Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 3 Underflow!!

Continue to experiment with this program to understand how a stack works.

Time Complexity of Stack Operations

Only a single element can be accessed at a time in stacks.

While performing push() and pop() operations on the stack, it takes O(1) time.

Conclusion

In this article, you learned the concept of stack data structure and its implementation using arrays in C.

The stack is used to solve a few of the general problems like:

  1. Tower of Hanoi
  2. N-Queens Problem
  3. Infix to Prefix Conversion

Continue your learning with How To Create a Queue in C and How To Initialize an Array in C.

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Learn more about us


About the authors
Default avatar
Safa Mulani

author



Still looking for an answer?

Ask a questionSearch for more help

Was this helpful?
 
JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
July 16, 2021

Very useful

- Lokeshwar.M

    JournalDev
    DigitalOcean Employee
    DigitalOcean Employee badge
    July 15, 2021

    Want application program

    - Birendra Kumar patel you

      Try DigitalOcean for free

      Click below to sign up and get $200 of credit to try our products over 60 days!

      Sign up

      Join the Tech Talk
      Success! Thank you! Please check your email for further details.

      Please complete your information!

      Get our biweekly newsletter

      Sign up for Infrastructure as a Newsletter.

      Hollie's Hub for Good

      Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

      Become a contributor

      Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

      Welcome to the developer cloud

      DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.

      Learn more
      DigitalOcean Cloud Control Panel