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.
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:
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.
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]); } }
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.
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.
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
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.
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
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.
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.
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
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.
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.
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
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.
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; }
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.
To push the element in the stack we need to follow the given steps:
- Update the new node next to the top node.
- 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.
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.
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
The pop method needs to follow the given steps for removing an element from the stack:
- Store the top node value.
- Update the top pointer to its next node.
- Return the stored value.
Example: Deleting a new node from the linked list stack and updating the top pointer to the next node.
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.
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
The peek method needs to follow the given steps to display the top element of the stack:
- Store the top node value.
- 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.
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]- Practice Design & Analysis of Algorithms MCQ
- Check Computer Science Books
- Check Programming Books
- Apply for Computer Science Internship
- Check Data Structure Books