Stack Push and Pop Program in C

Types of Stack Data Structure

There are three main types of stack data structures:

1. Fixed-size stack: In this type, the maximum size of the stack is fixed & cannot be changed during runtime. The stack is implemented using an array, & the size is determined at the time of declaration.
 

2. Dynamic-size stack: This type of stack allows the size to be changed dynamically during runtime. It is implemented using a linked list, where nodes are allocated & deallocated as needed.
 

3. Growable stack: This is a variation of the fixed-size stack that allows the stack to grow in size when it becomes full. When the stack reaches its maximum capacity, a new array with a larger size is allocated, & the elements from the old array are copied to the new one.
 

In this article, we will focus on implementing a fixed-size stack using an array in C.

For example: 

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

In this code, we define a constant `MAX_SIZE` to set the maximum size of the stack, which is fixed at 100. We declare an integer array `stack` of size `MAX_SIZE` to store the stack elements. The variable `top` is initialized to -1, indicating that the stack is currently empty.

Note: With a fixed-size stack, we need to be cautious not to push elements when the stack is already full, as it will lead to a stack overflow error. Similarly, we need to ensure not to pop elements when the stack is empty, as it will cause a stack underflow error.

Basic Operations on Stack Data Structure

A stack data structure supports the following basic operations:

1. Push: Adds an element to the top of the stack
 

2. Pop: Removes the top element from the stack
 

3. Top or Peek: Returns the top element of the stack without removing it
 

4. isEmpty: Checks if the stack is empty
 

5. isFull: Checks if the stack is full

Let's discuss each of these operations in detail.

Push Operation in Stack Data Structure

The push operation adds an element to the top of the stack. Let’s see how we can implement the push function in C:

void push(int element) {
    if (isFull()) {
        printf("Stack Overflow! Cannot push element.\n");
    } else {
        top++;
        stack[top] = element;
        printf("Element %d pushed to stack.\n", element);
    }
}

In this code, we first check if the stack is full using the `isFull()` function. If the stack is full, we print an error message indicating a stack overflow. If the stack is not full, we increment the `top` variable & assign the new element to `stack[top]`. Finally, we print a message confirming that the element has been pushed to the stack.

The time complexity of the push operation is O(1) since it takes constant time to add an element to the top of the stack.

Pop Operation in Stack Data Structure

The pop operation removes the top element from the stack & returns its value. Let’s see how we can implement the pop function in C:

int pop() {
    if (isEmpty()) {
        printf("Stack Underflow! Cannot pop element.\n");
        return -1;
    } else {
        int poppedElement = stack[top];
        top--;
        return poppedElement;
    }
}

In this code, we first check if the stack is empty using the `isEmpty()` function. If the stack is empty, we print an error message indicating a stack underflow & return -1 to signify an invalid operation. If the stack is not empty, we store the top element in a variable `poppedElement`, decrement the `top` variable, & then return the popped element.

The time complexity of the pop operation is O(1) since it takes constant time to remove an element from the top of the stack.

Let’s take an example of how to use the pop function:

int main() {
    push(10);
    push(20);
    push(30);
    
    int poppedElement = pop();
    printf("Popped element: %d\n", poppedElement);
    
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output:

Element 10 pushed to stack.
Element 20 pushed to stack.
Element 30 pushed to stack.
Popped element: 30

In this example, we push three elements (10, 20, 30) onto the stack. Then, we call the `pop()` function to remove the top element, which is 30, & store it in the `poppedElement` variable. Finally, we print the popped element.

Top or Peek Operation in Stack Data Structure

The top or peek operation returns the top element of the stack without removing it. Here's how we can implement the top function in C:

int top() {
    if (isEmpty()) {
        printf("Stack is empty. No top element.\n");
        return -1;
    } else {
        return stack[top];
    }
}

In this code, we first check if the stack is empty using the `isEmpty()` function. If the stack is empty, we print a message indicating that there is no top element & return -1 to signify an invalid operation. If the stack is not empty, we simply return the element at index `top`, which represents the top element of the stack.

The time complexity of the top operation is O(1) since it takes constant time to access the top element of the stack.

For example: 

int main() {
    push(10);
    push(20);
    push(30);
    
    int topElement = top();
    printf("Top element: %d\n", topElement);
    
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Element 10 pushed to stack.
Element 20 pushed to stack.
Element 30 pushed to stack.
Top element: 30

In this example, we push three elements (10, 20, 30) onto the stack. Then, we call the `top()` function to get the top element of the stack, which is 30, & store it in the `topElement` variable. Finally, we print the top element.

Note: The top operation is useful when you want to know the top element of the stack without actually removing it.

isEmpty Operation in Stack Data Structure

The isEmpty operation checks if the stack is empty. It returns true if the stack is empty and false otherwise. Here's how we can implement the isEmpty function in C:

int isEmpty() {
    return (top == -1);
}

In this code, we simply check if the `top` variable is equal to -1. If `top` is -1, it means the stack is empty, and we return true (1). Otherwise, if `top` is not -1, it means the stack is not empty, and we return false (0).

The time complexity of the isEmpty operation is O(1) since it takes constant time to check the value of `top`.

Let’s look at an example of how to use the isEmpty function:

int main() {
    if (isEmpty()) {
        printf("Stack is empty.\n");
    } else {
        printf("Stack is not empty.\n");
    }
    
    push(10);
    
    if (isEmpty()) {
        printf("Stack is empty.\n");
    } else {
        printf("Stack is not empty.\n");
    }
    
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Stack is empty.
Element 10 pushed to stack.
Stack is not empty.

In this example, we first check if the stack is empty using the `isEmpty()` function. Since we haven't pushed any elements yet, the stack is empty, and it prints "Stack is empty." Then, we push an element (10) onto the stack and check again using `isEmpty()`. This time, the stack is not empty, so it prints "Stack is not empty."

Note: The isEmpty operation is useful when you want to check if the stack is empty before performing any operations on it, such as popping an element.

isFull Operation in Stack Data Structure

The isFull operation checks if the stack is full. It returns true if the stack is full and false otherwise. Here's how we can implement the isFull function in C:

int isFull() {
    return (top == MAX_SIZE - 1);
}

In this code, we check if the `top` variable is equal to `MAX_SIZE - 1`. If `top` is equal to `MAX_SIZE - 1`, it means the stack is full, and we return true (1). Otherwise, if `top` is not equal to `MAX_SIZE - 1`, it means the stack is not full, and we return false (0).

The time complexity of the isFull operation is O(1) since it takes constant time to check the value of `top`.

For example: 

int main() {
    if (isFull()) {
        printf("Stack is full.\n");
    } else {
        printf("Stack is not full.\n");
    }
    
    // Push elements until the stack is full
    for (int i = 0; i < MAX_SIZE; i++) {
        push(i);
    }
    
    if (isFull()) {
        printf("Stack is full.\n");
    } else {
        printf("Stack is not full.\n");
    }
    
    return 0;
}

Output

Stack is not full.
Element 0 pushed to stack.
Element 1 pushed to stack.

Element 98 pushed to stack.
Element 99 pushed to stack.
Stack is full.

In this example, we first check if the stack is full using the `isFull()` function. Since we haven't pushed any elements yet, the stack is not full, and it prints "Stack is not full." Then, we use a for loop to push elements onto the stack until it reaches its maximum size (`MAX_SIZE`). After pushing all the elements, we check again using `isFull()`. This time, the stack is full, so it prints "Stack is full."

Note: The isFull operation is useful when you want to check if the stack is full before pushing any more elements onto it to avoid a stack overflow.

Implementation of Stack Data Structure

Now that we have discussed the basic operations on a stack data structure, let's see how we can implement a stack using an array in C.

Implementation of Stack Data Structure using Array

Let’s take a look at the complete code for implementing a stack using an array in C:

#include <stdio.h>
#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

void push(int element) {
    if (top == MAX_SIZE - 1) {
        printf("Stack Overflow! Cannot push element.\n");
    } else {
        top++;
        stack[top] = element;
        printf("Element %d pushed to stack.\n", element);
    }
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow! Cannot pop element.\n");
        return -1;
    } else {
        int poppedElement = stack[top];
        top--;
        return poppedElement;
    }
}

int peek() {
    if (top == -1) {
        printf("Stack is empty. No top element.\n");
        return -1;
    } else {
        return stack[top];
    }
}

int isEmpty() {
    return (top == -1);
}


int isFull() {
    return (top == MAX_SIZE - 1);
}

int main() {
    push(10);
    push(20);
    push(30);
    
    printf("Top element: %d\n", peek());
    
    int poppedElement = pop();
    printf("Popped element: %d\n", poppedElement);
    
    printf("Is stack empty? %s\n", isEmpty() ? "Yes" : "No");
    printf("Is stack full? %s\n", isFull() ? "Yes" : "No");
    
    return 0;
}

You can also try this code with Online C Compiler

Run Code

In this code, we defined a constant `MAX_SIZE` to set the maximum size of the stack. We declared an integer array `stack` to store the stack elements & a variable `top` to keep track of the top element.

Then, we implemented the `push()`, `pop()`, `peek()`, `isEmpty()`, & `isFull()` functions. In the `main()` function, we demonstrated the usage of these functions. We push three elements onto the stack, peek at the top element, pop an element, & check if the stack is empty or full.

Output:

Element 10 pushed to stack.
Element 20 pushed to stack.
Element 30 pushed to stack.
Top element: 30
Popped element: 30
Is stack empty? No
Is stack full? No

Implementation of Stack Data Structure using Linked List

Another way to implement a stack data structure is by using a linked list. In a linked list implementation, each element in the stack is represented as a node, and the nodes are connected using pointers.

Let’s look at the code for implementing a stack using a linked list in C:

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};


struct Node* top = NULL;

void push(int element) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = element;
    newNode->next = top;
    top = newNode;
    printf("Element %d pushed to stack.\n", element);
}

int pop() {
    if (top == NULL) {
        printf("Stack Underflow! Cannot pop element.\n");
        return -1;
    } else {
        struct Node* temp = top;
        int poppedElement = temp->data;
        top = top->next;
        free(temp);
        return poppedElement;
    }
}

int peek() {
    if (top == NULL) {
        printf("Stack is empty. No top element.\n");
        return -1;
    } else {
        return top->data;
    }
}


int isEmpty() {
    return (top == NULL);
}


int main() {
    push(10);
    push(20);
    push(30);
    
    printf("Top element: %d\n", peek());
    
    int poppedElement = pop();
    printf("Popped element: %d\n", poppedElement);
    
    printf("Is stack empty? %s\n", isEmpty() ? "Yes" : "No");
    
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Element 10 pushed to stack.
Element 20 pushed to stack.
Element 30 pushed to stack.
Top element: 30
Popped element: 30
Is stack empty? No

In this code, we define a `struct Node` to represent each element in the stack. Each node contains an integer `data` and a pointer `next` to the next node in the stack.
 

We initialize a pointer `top` to `NULL` to represent the top of the stack.
 

The `push()` function creates a new node, assigns the element to its `data`, and updates the `next` pointer to the current top. Then, it updates `top` to point to the newly created node.
 

The `pop()` function checks if the stack is empty. If it is, it prints an underflow message. Otherwise, it retrieves the data from the top node, updates `top` to point to the next node, frees the memory of the popped node, and returns the popped element.
 

The `peek()` function checks if the stack is empty and returns the data of the top node if it exists.
 

The `isEmpty()` function checks if `top` is `NULL` to determine if the stack is empty.
 

In the `main()` function, we demonstrate the usage of these functions similar to the array implementation.

Complexity Analysis of Operations on Stack Data Structure

Let's analyze the time and space complexity of the basic operations on a stack data structure.

1. Push Operation

• Time Complexity: O(1)
  The push operation takes constant time as it involves adding an element to the top of the stack, which is a single step operation.
   
• Space Complexity: O(1)
  The push operation requires a constant amount of extra space to store the new element.

2. Pop Operation

• Time Complexity: O(1)
  The pop operation takes constant time as it involves removing the top element from the stack, which is a single step operation.
   
• Space Complexity: O(1)
  The pop operation does not require any extra space.

3. Top or Peek Operation

• Time Complexity: O(1)
  The top or peek operation takes constant time as it involves accessing the top element of the stack, which is a single step operation.
   
• Space Complexity: O(1)
  The top or peek operation does not require any extra space.

4. isEmpty Operation

• Time Complexity: O(1)
  The isEmpty operation takes constant time as it involves checking a single condition, which is a single step operation.
   
• Space Complexity: O(1)
  The isEmpty operation does not require any extra space.

5. isFull Operation

• Time Complexity: O(1)
  
  The isFull operation takes constant time as it involves checking a single condition, which is a single step operation.
   
• Space Complexity: O(1)
  
  The isFull operation does not require any extra space.

Overall, the time complexity of all the basic operations on a stack data structure is O(1), which means they are performed in constant time regardless of the stack's size. The space complexity is also O(1) for all operations except the push operation, which requires a constant amount of extra space to store the new element.

Note: The stack data structure provides efficient insertion and deletion of elements at one end (the top), making it suitable for situations where elements need to be added and removed in a Last-In-First-Out (LIFO) manner.

Advantages of Stack Data Structure

1. Simplicity: The stack data structure is simple to understand and implement. It follows the Last-In-First-Out (LIFO) principle, which makes it intuitive to use in certain scenarios.
 

2. Efficient Operations: The basic operations on a stack, such as push, pop, and peek, have a time complexity of O(1). This means that these operations are performed in constant time, regardless of the size of the stack, making them highly efficient.
 

3. Memory Utilization: Stacks have a small memory footprint. They require minimal additional memory to store the elements and maintain the structure. This makes stacks memory-efficient, especially when dealing with a large number of elements.
 

4. Reverse Order Access: Stacks provide a natural way to access elements in reverse order of their insertion. This is useful in scenarios where the most recently added element needs to be accessed first, such as in undo/redo operations or function call tracking.
 

5. Backtracking: Stacks are commonly used in backtracking algorithms. When exploring multiple possibilities or paths, a stack can be used to keep track of the current state and easily revert to a previous state when needed.
 

6. Expression Evaluation: Stacks are used in evaluating arithmetic expressions, particularly in infix to postfix conversion and postfix expression evaluation. They help in maintaining the order of operands and operators during the evaluation process.
 

7. Function Calls: Stacks are used to manage function calls in programming languages. When a function is called, its local variables and return address are pushed onto the stack. When the function returns, the stack is used to restore the previous state and return to the calling function.

Disadvantages of Stack Data Structure

1. Limited Accessibility: Stacks provide access to only the top element. Elements in the middle or at the bottom of the stack cannot be accessed or modified directly. To access an element other than the top, you need to remove all the elements above it, which can be inefficient.
 

2. Fixed Size (in array implementation): When implementing a stack using an array, the size of the stack is fixed and needs to be specified in advance. If the stack becomes full, it may lead to stack overflow, and if the stack is empty, it may lead to stack underflow. Resizing the array can be costly in terms of time and space complexity.
 

3. Not Suitable for Searching: Stacks are not efficient for searching elements. To find an element in a stack, you need to traverse the stack from the top until the desired element is found. This can be time-consuming, especially for large stacks.
 

4. No Random Access: Stacks do not support random access to elements. You cannot directly access an element at a specific position in the stack. To access an element, you need to remove all the elements above it, which can be inefficient.
 

5. Limited Functionality: Stacks have limited built-in functionality compared to other data structures like arrays or linked lists. They are primarily designed for pushing and popping elements, and any additional operations need to be implemented separately.
 

6. Stack Overflow: If the stack grows too large and exceeds the available memory, it may lead to a stack overflow error. This can happen if there are too many recursive function calls or if the stack is not properly managed.

Applications of Stack Data Structure

1. Function Call Management: Stacks are used to manage function calls in programming languages. When a function is called, its local variables, parameters, and return address are pushed onto the stack. When the function returns, the stack is used to restore the previous state and return to the calling function.
 

2. Expression Evaluation: Stacks are used in evaluating arithmetic expressions. They are used in infix to postfix conversion and postfix expression evaluation algorithms. Stacks help in maintaining the order of operands and operators during the evaluation process.
 

3. Backtracking: Stacks are used in backtracking algorithms, such as solving a maze, finding all possible paths, or solving puzzles like Sudoku. The stack is used to store the current state and explore different possibilities. If a path leads to a dead end, the algorithm backtracks by popping the previous state from the stack and tries a different path.

4. Undo/Redo Functionality: Stacks are used to implement undo/redo functionality in applications like text editors or graphic design software. The previous states or actions are pushed onto the stack. When the user wants to undo an action, the last state is popped from the stack and restored. Similarly, for redo, the previously undone state is pushed back onto the stack.
 

5. Recursive Algorithms: Stacks are inherently used in recursive algorithms. When a recursive function is called, the function's state is pushed onto the stack. When the base case is reached, the function returns, and the previous states are popped from the stack to continue the execution.
 

6. Browser History: Web browsers use stacks to maintain the history of visited web pages. When a new page is visited, its URL is pushed onto the stack. When the user clicks the back button, the previous URL is popped from the stack, and the browser navigates to that page.
 

7. Syntax Parsing: Stacks are used in parsing the syntax of programming languages. Compilers and interpreters use stacks to keep track of nested structures like parentheses, braces, and function calls. Stacks help in ensuring the proper matching and nesting of these structures.

Frequently Asked Questions 

What is the main difference between a stack and a queue?

The main difference is that a stack follows the LIFO (Last-In-First-Out) principle, while a queue follows the FIFO (First-In-First-Out) principle.

Can a stack be implemented using a linked list?

Yes, a stack can be implemented using a linked list by adding and removing elements from one end, typically called the top.

What happens when we try to pop an element from an empty stack?

When we try to pop an element from an empty stack, it results in a stack underflow error, indicating that there are no elements to remove.

Conclusion

In this article, we discussed the stack data structure and its implementation using arrays and linked lists in C. We covered basic operations like push, pop, peek, isEmpty, and isFull, along with their time and space complexities. We also discussed the advantages, disadvantages, and various applications of stacks. Stacks are a fundamental data structure that follows the LIFO principle and finds use in many algorithms and real-world scenarios.

You can also check out our other blogs on Code360.