Understanding the Stack Data Structure in C: Introduction, Implementation, and Examples

introduction

A foundational idea in computer science, the stack data structure is essential to many algorithms and programming languages. A stack is a linear data structure in C where a new element is added and an existing element is removed at the same end, sometimes referred to as the top of the stack. This article gives a thorough description of stacks in C, including their fundamental concepts, how they are implemented using arrays and linked lists, and examples of operations like pushing and popping pieces from stacks.

What is Stack in C?

A stack is a linear data structure in which the insertion of a new element and removal of an existing element takes place at the same end represented as the top of the stack.

Simply

• Assume you have a plate stack. Plates can only be added or removed from the top of the stack. In programming, this is referred to as a stack.

• When you add a plate to the stack, it goes on top of the other plates. The plate you add last is the one you can remove first. So, the last plate you put on the stack is the first one you can take off.

Let’s take an exmaple

• Let’s say you have a stack of plates in this order: purple, red, orange, blue, pink. So the purple plate in the bottom and the pink on the top.
• You have to start from the top if you want to remove a plate. so if you need to remove the purple plate, you have to remove the pink, blue, orange, red then the purple.

• So finally, we can say. A stack is a way to store data where the last item added is the first one that can be removed. You can only add or remove items from the top of the stack.
• Obviously! The first element you put in a stack is the last one to come out. The “Last In, First Out” (LIFO) rule governs this. Similarly, the last thing you put in is the first thing you may take out.
• As a result, in a stack, element insertion and deletion always occur at the top. You can add new components to the top of the stack and delete elements from the top of the stack. The remainder of the components under the top are unaffected.
• A stack data structure is distinguished by its Last In First Out behaviour and the ability to insert and delete components only from the top.

There are two common ways to implement a stack

1. Statically using an array

• You allocate a fixed-size array to contain the stack components in this procedure.
• The array acts as the stack’s underlying data structure.
• To keep track of the top element and the number of elements in the stack, you use the variable “top.”
• By incrementing the top variable and saving the new element at that position, you may push (add) elements to the stack.
• Similarly, you may pop (remove) elements from the stack by accessing the top element and decrementing the top variable.
• The stack size is constant and cannot be adjusted dynamically, which is one disadvantage of this strategy.

2. Dynamically using a linked list.

• To implement the stack in this approach, you utilise a linked list.
• Each node in the linked list represents a stack element and contains the actual data as well as a reference to the next node.
• The linked list’s head represents the top of the stack.
• To push an element, you build a new node, assign it a data value, and make it the linked list’s new head.
• Popping an element involves removing the head node and updating the head pointer to the next node in the list.
• The advantage of this strategy is that the stack may dynamically increase or decrease depending on the number of items.

Array implementation

• Determining the size of the stack prior to the program run is very important.
• In the array implementation of a stack, inserting an element is known as “pushing” an element onto the stack. When you push an element, it gets added to the stack’s top. This signifies that the element will be placed at the index indicated by the “top” variable at the time.
• Assume we have an array-based stack with the entries [5, 8, 12, 3]. The variable “top” originally points to index 3, which has the value 3. Now we want to add element 10 to the stack. We raise the “top” variable and add the new element to the freshly updated index. After pushing 10, the stack looks like this: [5, 8, 12, 3, 10]. The variable “top” now points to index 4, which has a value of 10.
• When you push an element into the stack, all of the current elements retain their places, but the “top” variable is modified to reflect the new topmost element.

Algorithm for pushing

Example

#include <stdio.h>
#define LIMIT 100
//The limited number of elements inside the stack is 100
int stack[LIMIT];
int top = -1;
void push()
{
  int element;
//Checking if the tack full of elements so we can't add more
  if (top == [LIMIT - 1]{
        pirntf("Stack Overflow: Cannot push element\n");
}
else{
      //if not, take the elements from the user 
      printf("Enter the element to be inserted: ");
      // store it in a variable
      scanf("%d", &element);
      //open a position or a place in the array for it
      top++;
      // add the value to the position
      stack[top] = element;
    }
}

int main()
{
  int i;
  //call the function
  push()

  printf("Stack elements: ");
  //loop for printing the result
  for (i = 0; i <= top; i++)
      {
        printf("%d ", stack[i]);
      }
printf("\n");
return 0;
}

Explanation

1. We define the constant LIMIT as 100, which represents the maximum size of the stack.

• Reason: By defining a limit, we can ensure that the stack does not exceed its maximum capacity. LIMIT as 100, we are manually allocating a fixed amount of memory for the stack. This limit represents the maximum number of elements that the stack can hold.

2. We declare an array stack with a size of LIMIT. This array will be used to store the elements of the stack.

3. Variable top and initialize it with -1. This variable will keep track of the index of the top element in the stack.

• Reason: Setting the top value to -1 indicates that the stack is initially empty. It will be increased and decremented to indicate the top element’s current location.

4. We define the function push(), which is responsible for inserting an element into the stack.

• Reason: The logic for putting an element onto the stack is encapsulated in the push() method, making the code modular and easy to comprehend.

5. Inside the push() function, we declare an integer variable element to store the element to be inserted.

• Reason: We’ll need a variable to hold the user’s input for the element they’d like to add to the stack.

6. We check if the stack is already full by comparing the top with LIMIT — 1. If the condition is true, we print the message “Stack Overflow: Cannot push element”, indicating that the stack is full and no more elements can be inserted.

• Reason: By determining if the stack is full, we may avoid inserting components that exceed the stack’s capacity and so avoid data corruption.

7. If the stack is not full, we prompt the user to enter the element to be inserted using the printf() function.

8. We use the scanf() function to read the user’s input and store it in the element variable.

9. We increment the top by one to point to the next available position in the stack.

• Reason: Incrementing the top signals that a new element will be added to the stack at the following place.

10. We assign the value of the element to the array stack at the index top, effectively inserting the element into the stack.

• Reason: We save the element on the stack by assigning the value to the array at the proper index.

11. In the main() function, we call the push() function to insert an element into the stack.

12. After calling push(), we print the elements in the stack using a loop. The loop starts from index 0 and continues until the top to access each element in the stack.

13. Finally, we print a newline character \n to provide a clean output.

Deletion

• The process of eliminating an element from a stack is known as popping an element from the stack. A data element is removed from the stack from the top.

Algorithm for popping

Example

#include <stdio.h>
#define LIMIT 100

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

void pop()
{
int element;

  //checking if the array is empty
    if (top == -1)
      {
         printf("Stack underflow\n");
      } 
      else
      {
          element = stack[top];
          printf("Popped item: %d\n", element);
           top--;
      }
}
  

int main()
{
    stack[++top] = 10;
    stack[++top] = 20;
    stack[++top] = 30;

    pop();

    return 0;
}

Explanation

• This code defines the pop() function, which is used to conduct the stack pop action.
• The method determines whether the stack is empty (top == -1). If it is empty, an error message indicating a stack underflow is printed.
• If the stack is not empty, the following steps are taken:
• The variable “element” is assigned the value of the topmost element in the stack.
• The value of the popped item is printed using printf.
• The value of “top” is decremented by one to signal that the element below the topmost element is now the new topmost element.
• The main() function is the program’s entry point.
• In this example, the “stack[++top]” notation is used to push three items (10, 20, 30) into the stack.
• The “++top” syntax raises the value of “top” before allocating the element to the stack, guaranteeing that the items are added progressively from the bottom.
• The pop() method is then called, which pops the topmost element off the stack and prints its value.
• Finally, it returns 0 to indicate that the execution was successful.

Output

Display

• According to the LIFO rule, the stack data items are presented in the stack.

#include <stdio.h>
#define LIMIT 100 

int top = -1; // Variable to keep track of the topmost element index
int stack[LIMIT]; // Array to store the stack elements

void displayStack()
{
  int i;
  if (top == -1)
    {
        printf("Stack is empty.\n");
    }
     else
     {
        printf("Stack elements: ");
         for (i = top; i >= 0; i--)
            {
                printf("%d ", stack[i]);
             }
            printf("\n");
        }
   }

int main()
{
    // Pushing elements onto the stack

    stack[++top] = 10;
    stack[++top] = 20;
    stack[++top] = 30;
    stack[++top] = 40;

    // Displaying the stack elements
    displayStack();

    return 0;
}

Explanation

• With a value of 100, the constant LIMIT represents the maximum amount of elements that may be placed on the stack.
• To hold the stack components, an array stack of size LIMIT is defined. The variable top is set to -1, indicating that the stack is empty.
• The displayStack() method is used to display the stack’s components.
• Three elements (10, 20, 30) are put onto the stack in the main() method by incrementing the top and assigning values to the stack array.
• The displayStack() method is invoked, which checks if the stack is empty and shows the stack’s items if it is not.

stack overflow

• A stack is a type of data structure that operates on the Last-In-First-Out (LIFO) principle. It’s usually done with an array or linked list. Elements are added or taken from one end of a stack, which is generally referred to as the “top” of the stack.
• The maximum number of items that can be stored in static memory allocation in a stack is predetermined. Assume we have a stack with a capacity of 100 items.
• A stack overflow problem, often known as “stack full,” happens when the stack has reached its limit and no more components may be added. This signifies that there is no room on the stack for additional components.
• In other words, attempting to push (insert) an element onto an already full stack would result in a stack overflow. The stack cannot accommodate the additional element since it has surpassed its capacity.
• When a stack overflow occurs, it signals that the stack has reached its limit and that any further additions would result in an error. It is critical to handle this scenario correctly to avoid data loss or program failures.

This is the stack overflow😂

stack unoverflow

• A stack is a data structure that adheres to the Last-In-First-Out (LIFO) principle, in which components are added or deleted from one end of the stack, which is generally referred to as the “top” of the stack.
• In the instance of stack underflow, it refers to the situation in which we attempt to conduct an action on the stack, such as displaying or deleting elements, but there are no elements in the stack.
• Assume we have an empty stack and attempt to conduct a pop operation to remove an element from the stack. We cannot remove any components from the stack since there are none, resulting in a stack underflow scenario.
• Similarly, attempting to display the items of an empty stack with no elements introduced results in a stack underflow condition.
• Stack underflow is so named because it implies that the stack lacks enough components to accomplish the intended action. It is critical to handle this circumstance correctly in order to avoid mistakes or unexpected behaviour in the program.

It’s like a boy is trying to drink an empty glass😂

Linked List Implementation of Stack in C

• Linked lists enable dynamic memory allocation for stack data components, providing for size allocation flexibility during programme execution. In the context of linked list implementation, let’s look at the three basic operations of insertion, deletion, and display.

Example

#include <stdio.h>

void push()
{ 
  int data;
  struct node *newN = malloc(sizeof(struct node*));

  //checking for malloc error
  if (newN == NULL)
     {
        printf("Stack overflow\n");
     }
      else
    {
          printf("Enter the element to be inserted: ");
          scanf("%d", &data);

          //Assgin the data to the new node
          newN->data = data;

          // Set the new node's next pointer to the current top node
           newN->next = temp //suppose temp is the pointer to the first node
      

          // Update the top pointer to point to the new node
           temp = newN;


  

Explanation

• The data variable is declared to hold the value of the inserted element.
• Using the malloc() method, a new node pointer is produced dynamically.
• The memory for the new node is allocated based on the size of the struct node. The code determines whether or not memory allocation was successful by comparing the reference to NULL. If it is, it indicates a lack of memory, and a “Stack overflow” alert is shown.
• If the memory allocation succeeds, the function inserts the element into the stack.
• The user is asked to input the element to be added, and its value is saved in the data variable through the scanf() method.
• The data value is assigned to pointer->data, representing the new node’s data value.
• As the new node should point to the current top node, the pointer->next is set to the current top of the stack (temp).
• The temporary pointer is then modified to refer to the new node, making it the new top of the stack.
• Following the LIFO concept, the insertion process is completed, and the new element is added at the beginning of the linked list.
• Don’t Forget: When we add or remove we do that on the first element of the linked list. So the insertion and deletion process here is done on the first element

Delete

• Note: The process is

1. Store the data of the node to be deleted in the item variable
2. To make a new pointer called pointer and this pointer will point to the node that will be deleted
3. To move the temp pointer to the next node which is the node before the node will be deleted because after the deletion of the node, it will be the first one
4. The delete the node by free function

void pop()
{
int item;
struct node *pointer;
  if (temp == NULL)
    {
      printf("Stack Underflow\n");
    }
  else
    {
      item = temp -> data;
      pointer = temp;
      temp = temp -> next;
      free(pointer);
      printf("The deleted item is %d\n",item);
    }
}

Since pop() is declared and has a void return type, it does not return a value.

item is a variable to hold the data coming from the deleted node.

The malloc() method is used to declare and allocate memory for the pointer variable pointer. A reference to a struct node) that is the size of the memory that is allocated.

The stack is checked for emptiness on the next line when the variable temp equals NULL. The code outputs “Stack underflow” if the stack is empty to show that there are no elements to remove from the stack.

The else block is run if the stack is not empty. The item at the top of the stack is then removed.

The statement item = temp->data sets the item variable’s value to the value of the data field from the top-level node (temp). This line retrieves the value of the top item prior to removal, assuming there is a data field in the struct node structure.

The temp pointer’s value is transferred to the pointer through the line pointer = temp; to save the address of the deleted node.

The temp pointer is updated to point to the following node on the stack by the statement temp= temp->next; The top node in the stack is basically removed by doing this.

The statement free(pointer ); releases the node that was removed from the stack by releasing the memory that was previously allotted to the temp pointer.

The code then uses printf(“The deleted item is:%d”, pointer); to output the value of the deleted item.

Please note that the code assumes the existence of a struct node definition and a variable has the top pointer for the stack. Additionally, error handling for an invalid state where the temp pointer is not properly initialized or points to an invalid memory location is not included in this code snippet...

Display

void display()
{
  int i;
  struct node* pointer;
// Assign the value of the temporary pointer to the 'pointer' variable
  pointer = temp;
  // If the stack is empty, print "Stack underflow"
  if (pointer == NULL)
  {
    printf("Stack Underflow");
  }
   else
  {
// Print the message indicating the elements in the stack
    printf("The elements of the stack are: \n");

    while (pointer != NULL)
      {
       // Print the data of the current node
      printf("%d\n", pointer->data);
      // Move the 'pointer' to the next node
      pointer = pointer->next;
    }
  }
}

The function determines if the pointer, which denotes an empty stack, is NULL.

“Stack underflow” is printed if the pointer is NULL, which indicates that there is no data on the stack.

The pointer indicates whether or not there are elements in the stack if it is not NULL, and it then prints those elements.

To display the next items, it outputs the message “The elements of the stack are:”.

The linked list is traversed using a while loop until the pointer is set to NULL. It publishes the value of pointer->data, which is the current node’s data, inside the loop.

Pointer = pointer->next is then used to transfer the pointer to the following node. All of the pieces in the stack have been printed once the loop has finished.

Complete Example

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

// Function prototypes
void push();
void pop();
void display();

// Structure definition for a node
struct node {
    int data;
    struct node* next;
};

// Global variable to store the top of the stack
struct node* temp;

int main()
{
    printf("Welcome to DataFlair tutorials!\n\n");
    int choice;
    printf("LINKED LIST IMPLEMENTATION USING STACKS\n\n");
    
    // Menu-driven program
    do
    {
        printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
        printf("Enter your choice:");
        scanf("%d", &choice);
        
        switch (choice)
        {
            case 1:
                push();
                break;
            case 2:
                pop();
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
                break;
            default:
                printf("Sorry, invalid choice!\n");
                break;
        }
    } while (choice != 4);
    
    return 0;
}

void push()
{
    int data;
    struct node* pointer = (struct node*)malloc(sizeof(struct node));
    
    if (pointer == NULL)
    {
        printf("Stack overflow\n");
    }
    else
    {
        printf("Enter the element to be inserted: ");
        scanf("%d", &data);
        
        if (temp == NULL)
        {
            pointer->data = data;
            pointer->next = NULL;
            temp = pointer;
        }
        else
        {
            pointer->data = data;
            pointer->next = temp;
            temp = pointer;
        }
    }
}

void pop()
{
    int item;
    struct node* pointer;
    
    if (temp == NULL)
    {
        printf("Stack underflow\n");
    }
    else
    {
        item = temp->data;
        pointer = temp;
        temp = temp->next;
        free(pointer);
        printf("The deleted item is %d\n", item);
    }
}

void display()
{
    struct node* pointer;
    pointer = temp;
    
    if (pointer == NULL)
    {
        printf("Stack underflow\n");
    }
    else
    {
        printf("The elements of the stack are:\n");
        
        while (pointer != NULL)
        {
            printf("%d\n", pointer->data);
            pointer = pointer->next;
        }
    }
}

Application of Stack in C

To evaluate arithmetic expressions like infix, postfix, or prefix expressions, stacks are frequently utilised. They assist in preserving the proper sequence of events and manage operator precedence.

Function Call Stack: The function call stack in C is used to handle function calls. To ensure appropriate execution and return flow, it maintains track of function calls, their local variables, and return addresses.

Backtracking: Backtracking algorithms, such as those for solving mazes, Sudoku puzzles, and the N-queens problem, frequently store the current state in stacks and retrace to earlier states as needed.

Matching brackets: Stacks can be used to verify that brackets, braces and brackets are utilised correctly in an expression. They aid in ensuring an adequate balance between the opening and closing symbols.

Browser History: The back button’s functionality in web browsers may be implemented using stacks. The user may go back by popping URLs off the stack after visiting each URL that is placed into the stack.

Using stacks to implement undo and redo actions in apps is a good idea. A command object is created for each operation and is then placed into the stack. To reverse the consequences of an action, the command must be popped off the stack.

Depth-First Search (DFS): DFS is a graph traversal method that keeps track of the vertices that have been visited while probing more and farther into the graph until it comes to a dead end. The stack aids in going back to previously unexplored vertices.

Conclusion

Stacks are a crucial type of data structure in programming, especially when it comes to Last-In-First-Out (LIFO) data management. Either arrays or linked lists can be used to implement them, and each has advantages and restrictions of its own. Programmers may substantially benefit from understanding the stack data structure and how it is implemented in C by building effective algorithms and finding solutions to a variety of issues. Developers may efficiently use stacks in their C programmes to organise and manipulate data by adhering to the guidelines and examples given in this article.