C Program to Implement Stack

Problem Description

Write a C program to implement the stack data structure and display the stack.

Stack Data Structure: Stack is a linear data structure to store the data item in LIFO (Last In First Out) principle. That means the item inserted at the end comes first out of the stack. It has only one direction to do all operations related to it.

There are many real-life examples of stacks that one can think about as piles of plates, books, etc.

Example:

Let’s understand the working of the stack with the given example.
Working of the stack with example

Problem Solution

There are many ways to implement the stack data structure. Before implementation, we have to know about the basic operations that we can perform in the stack. These operations are given below:

  • Push the data onto the stack
  • Pop the data from the stack
  • Peek the data from the stack
  • Display the stack

Here, we are discussing two methods of implementation of the Stack Program in C:

advertisement
advertisement

Method 1: (Stack Implementation in C using Array)

An array is a linear data structure that stores data items in contiguous memory space. Here we will use a structure that contains the array and the top pointer. The top pointer keeps tracking the top element of the stack.

Program/Source Code

Here is source code of the C program to implement stack using array. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/* 
 * C program to Implement Stack using Array
 */
 
#include <stdio.h>
#define MAX_SIZE 20
 
// function prototyping
void push(int);
int pop(void);
int peek(void);
int is_empty();
int is_full();
void display();
 
struct stack
{
    int stk[MAX_SIZE];
    int top;
};
 
struct stack st;
 
int main()
{
    st.top = -1;
 
    char userContinue = 'Y';
    int userChoice;
    while (userContinue == 'Y' || userContinue == 'y') {
        printf("\n------ STACK DATA STRUCTURE ------\n\n");
        printf("\n1. Push the data");
        printf("\n2. Pop the data");
        printf("\n3. Peek the data");
        printf("\n4. Display Stack");
        printf("\n5. Exit");
 
        printf("\n\nEnter Your Choice: ");
        scanf("%d", &userChoice);
 
        switch (userChoice) 
        {
        case 1:
            printf("\n\nEnter Data: ");
            scanf("%d", &userChoice);
            push(userChoice);
            break;
        case 2:
            if (!is_empty())
            {
                int data = pop();
                printf("\nValue %d was popped", data);
            } 
            else 
            {
                printf("\n\tStack is Empty!");
            }
            break;
        case 3:
            if (!is_empty())
            {
                int data = peek();
                printf("\nValue %d was peeked", data);
            }
            else
            {
                printf("\n\tStack is Empty!");
            }
            break;
        case 4:
            display();
            break;
        case 5:
            printf("\n\tProgram Terminated!\n");
            return 1;
            break;
        default:
            printf("\n\tInvalid Choice!");
        }
 
        printf("\n\nDo you want to continue? ");
        fflush(stdin);
        scanf(" %c", &userContinue);
    }
    return 0;
}
 
int is_full()
{
    if (st.top == MAX_SIZE)
    {
        return 1;
    }
 
    return 0;
}
 
int is_empty()
{
    if (st.top == -1)
    {
        return 1;
    }
    return 0;
}
 
void push(int data)
{
    if (is_full())
    {
        printf("\nStack Overflow!");
    }
    else
    {
        st.stk[++st.top] = data;
        printf("\n* %d was inserted", data);
    }
}
 
int pop()
{
    return st.stk[st.top--];
}
 
int peek()
{
    return st.stk[st.top];
}
 
void display()
{
    if (is_empty())
    {
        printf("\n\tStack is Empty!");
        return;
    }
    for (int i = st.top; i >= 0; i--)
    {
        printf("\n\t%d", st.stk[i]);
    }
}
Program Explanation

In this program, we are using the array of size 20. We have created a structure of the array and a top pointer that points to the top of the stack.

Note: Join free Sanfoundry classes at Telegram or Youtube

Here, we have discussed the essential functions of the stack and their time and space complexities. Assuming the size of the stack is currently n, where n is the number of elements in the node.

push() Function:

It is used to insert new data onto the stack. To insert a new value, we have to increment the top by one and insert the data in the new position.

Example: Inserting a node with data 89
Stack push() function using array

advertisement

Time Complexity: O(1)
In the above proram, since we are not traversing through the array, time is constant.

Space Complexity: O(1)
Space is constant because there are only temporary variables that are used.

Run Time Testcases

In this case, we are performing a push operation on the stack.

------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 1
 
Enter Data: 67
 
* 67 was inserted        
 
Do you want to continue? y 
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data   
4. Display Stack   
5. Exit
 
Enter Your Choice: 1
 
Enter Data: 45
 
* 45 was inserted        
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data   
4. Display Stack   
5. Exit
 
Enter Your Choice: 1
 
Enter Data: 35
 
* 35 was inserted        
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data   
4. Display Stack   
5. Exit
 
Enter Your Choice: 1
 
Enter Data: 89
 
* 89 was inserted        
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        89
        35
        45
        67
 
Do you want to continue? N

advertisement
Pop() Method:

It removes an element from the top of the stack if the stack is not empty. After removing the element, the top is decremented by one.

Example: Pop out the data from the stack.

Stack Pop method using array

Time Complexity: O(1)
It doesn’t require the traversals of the stack. So the time is constant of stack in C is O(1).

Space Complexity: O(1)
Since we are not using any additional space to perform pop operations, the space is constant.

Run Time Testcases

In this case, we are performing a pop operation on the stack.

------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        89
        35
        45
        67
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 2
 
Value 89 was popped
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        35
        45
        67
 
Do you want to continue? n

Peek() Method

It is used to show the top element of the non-empty stack. The top is not decremented in this case.

Example: Peeking at the top element of the stack.
Stack Peek method using array

Time Complexity: O(1)
It doesn’t require the traversals of the stack. So the time is constant in this case.

Space Complexity: O(1)
Since we are not using any additional space to perform pop operations, the space is constant.

Run Time Testcases

In this case, we are performing a peek operation on the stack.

------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        35
        45
        67
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 3
 
Value 35 was peeked
 
Do you want to continue? n

Method 2: (Stack Implementation using Linked List)

The linked list is a linear data structure that stores the data in the node. Every node contains data and the reference to the next node. We are implementing the stack using a linked list.

Here, we insert and delete the nodes from the beginning to perform the push and pop operation respectively.

Program/Source Code

Here is source code of the C program to implement stack using linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/* 
 * C program to Implement Stack using linked list
 */
#include<stdio.h>
#include<stdlib.h>
 
struct stack
{
    int data;
    struct stack* next;
};
 
struct stack* top = NULL;
 
//function prototyping
struct stack* create_node(int);
void push(int);
int pop();
int peek();
int is_empty();
void display();
 
int main()
{
    char userContinue = 'Y';
    int userChoice;
    while (userContinue == 'Y' || userContinue == 'y') {
        printf("\n------ STACK DATA STRUCTURE ------\n\n");
        printf("\n1. Push the data");
        printf("\n2. Pop the data");
        printf("\n3. Peek the data");
        printf("\n4. Display Stack");
        printf("\n5. Exit");
 
        printf("\n\nEnter Your Choice: ");
        scanf("%d", &userChoice);
 
        switch (userChoice) 
        {
        case 1:
            printf("\n\nEnter Data: ");
            scanf("%d", &userChoice);
            push(userChoice);
            break;
        case 2:
            if (!is_empty()) {
                int data = pop();
                printf("\nValue %d was popped", data);
            } else {
                printf("\n\tStack is Empty!");
            }
            break;
        case 3:
            if (!is_empty()) {
                int data = peek();
                printf("\nValue %d was peeked", data);
            } else {
                printf("\n\tStack is Empty!");
            }
            break;
        case 4:
            display();
            break;
        case 5:
            printf("\n\tProgram Terminated!\n");
            return 1;
            break;
        default:
            printf("\n\tInvalid Choice!");
        }
 
        printf("\n\nDo you want to continue? ");
        fflush(stdin);
        scanf(" %c", &userContinue);
    }
    return 0;
 
}
 
/* creates a new node */
struct stack* create_node(int data)
{
    struct stack* new_node = (struct stack*) malloc (sizeof(struct stack));
 
    if (new_node == NULL) {
        printf("\nMemory can't be allocated\n");
        return NULL;   
    }
 
    new_node->data = data;
    new_node->next = NULL; 
    return new_node;
}
 
/* push the data in the stack */
void push(int data)
{
    struct stack* new_node = create_node(data);
    if (new_node != NULL) {
        new_node->next = top;
        top = new_node;
 
        printf("\n* %d was inserted", data);
    }
}
 
/* pop the data from the stack */
int pop()
{
    int data = top->data;
    top = top->next;
    return data;
}
 
/* peek the data of the stack */
int peek()
{
    int data = top->data;
    return data;
}
 
/* display the stack */
void display()
{
    if(is_empty()) {
        printf("\n\tStack is Empty");
    }
    struct stack* temp = top;
    while (temp != NULL) {
        printf("\n\t%d", temp->data);
        temp = temp->next; 
    }
}
 
/* check whether stack is empty or not */
int is_empty() 
{
    if (top == NULL) {
        return 1;
    } 
    return 0;
}
Program Explanation

In the linked list implementation of the stack, we have created a structure of node which contains the node value and address of the next node.

Here, we are discussing the main functions and their time complexities.

push() Method

To push the element in the stack we need to follow the given steps:

  1. Update the new node next to the top node.
  2. Update the top pointer to the new node.

Example: Inserting a new node in the linked list stack and updating the top pointer to the new node.
Stack Push Method using Linked List

Time Complexity: O(1)
Inserting a new value into the stack requires a constant amount of time.

Space Complexity: O(1)
Space is constant because only temporary variables are taken.

Run Time Testcases

In this case, we are performing a push operation on the stack.

------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 1
 
Enter Data: 45
 
* 45 was inserted
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 1
 
Enter Data: 78
 
* 78 was inserted
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 1
 
Enter Data: 89
 
* 89 was inserted
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        89
        78
        45
 
Do you want to continue? n

pop() Method

The pop method needs to follow the given steps for removing an element from the stack:

  1. Store the top node value.
  2. Update the top pointer to its next node.
  3. Return the stored value.

Example: Deleting a new node from the linked list stack and updating the top pointer to the next node.

Stack pop method using linked list

Time Complexity: O(1)
Time is constant because no traversals need to remove the element from the stack from the top.

Space Complexity: O(1)
Space is constant due to temporary variables.

Run Time Testcases

In this case, we are performing a pop operation on the stack.

------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        89
        78
        45
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 2
 
Value 89 was popped
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        78
        45
 
Do you want to continue? n

peek() Method

The peek method needs to follow the given steps to display the top element of the stack:

  1. Store the top node value.
  2. Return the stored value.

Time Complexity: O(1)
Time is constant because no traversals need to remove the element from the stack from the top.

Space Complexity: O(1)
Space is constant due to temporary variables.

Run Time Testcases

In this case, we are performing a peek operation on the stack.

 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 4
 
        78
        45
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 3
 
Value 78 was peeked
 
Do you want to continue? y
 
------ STACK DATA STRUCTURE ------
 
1. Push the data
2. Pop the data
3. Peek the data
4. Display Stack
5. Exit
 
Enter Your Choice: 5
 
        Program Terminated!

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

Related Posts:

advertisement

Recommended Articles:

  1. Java Program to Implement Stack using Linked List
  2. C Program to Implement Stack
  3. C Program to Implement Stack Operations using Dynamic Memory Allocation
  4. Java Program to Implement Stack using Two Queues
  5. C++ Program to Implement Stack
  6. Java Program to Implement Stack
  7. C Program to Implement Stack using Linked List
  8. C++ Program to Implement Stack in STL
  9. C# Program to Implement Stack with Push and Pop Operations
  10. Java Program to Implement Stack API
advertisement
Additional Resources:
Popular Pages:
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.