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. To reach the oldest entered item, you must pop all the previous items.

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

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 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 whether 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.

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