How to Implement a Stack in C Programming

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

Introduction

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.

Applications of Stack

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

• Tower of Hanoi
• N-Queens Problem
• Infix to Prefix Conversion

Concept and Implementation

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.

• 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 
#include 

#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]);
    }
}

Program Features

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.

Execution Flow

• Push: 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.
• Pop: 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.
• Show: 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.
• End: The program exits.

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 of How to Implement a Stack in C Programming

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