How to Implement a Stack in C (+ encapsulation)

Introduction

This tutorial will guide you through implementing a stack in C using two different methods: an array and a linked list. Stacks are essential data structures that operate on a Last-In-First-Out (LIFO) principle, which makes them useful in various applications such as parsing expressions, backtracking algorithms, and managing function calls in programming.

Step 1: Implementing a Stack Using an Array

Setting Up the Stack

1. Define the Array

   • Choose the type of elements stored in the stack (e.g., integers).
   • Define the maximum size for the stack.

   #define MAX 5
   int stack[MAX];
   int top = -1; // Indicates that the stack is empty
   

2. Push Function

   • Create a function to add an element to the stack.
   • Check if the stack is full before adding.
   • Increment the top index and store the value.

   bool push(int value) {
       if (top == MAX - 1) {
           return false; // Stack is full
       }
       stack[++top] = value; // Increment top and add value
       return true;
   }
   

3. Pop Function

   • Create a function to remove and return the top element.
   • Check if the stack is empty before removing.
   • Decrement the top index after removing the value.

   int pop() {
       if (top == -1) {
           return INT_MIN; // Stack is empty
       }
       return stack[top--]; // Return top value and decrement
   }
   

4. Testing the Array Implementation

   • In the main function, test the push and pop functions.
   • Print the elements to confirm they are in reverse order of insertion.

   int main() {
       push(1);
       push(2);
       push(3);
       printf("%d\n", pop()); // Should print 3
       // Continue popping to test
   }
   

Step 2: Implementing a Stack Using a Linked List

Setting Up the Linked List

1. Define the Node Structure

   • Create a structure to represent a node in the linked list.

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

2. Define the Stack Structure

   • Create a structure for the stack that includes a pointer to the head node.

   struct Stack {
       struct Node* head;
   };
   

3. Push Function

   • Allocate a new node and check for memory allocation failure.
   • Set the new node's next pointer to the current head and update the head.

   bool push(struct Stack* stack, int value) {
       struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
       if (!newNode) {
           return false; // Memory allocation failed
       }
       newNode->value = value;
       newNode->next = stack->head;
       stack->head = newNode;
       return true;
   }
   

4. Pop Function

   • Remove the top node, return its value, and free the memory.
   • Check if the stack is empty.

   int pop(struct Stack* stack) {
       if (stack->head == NULL) {
           return INT_MIN; // Stack is empty
       }
       struct Node* temp = stack->head;
       int value = temp->value;
       stack->head = stack->head->next;
       free(temp);
       return value;
   }
   

5. Testing the Linked List Implementation

   • In the main function, test the push and pop functions.
   • Print the elements to verify they are in reverse order.

   int main() {
       struct Stack stack;
       stack.head = NULL;
       push(&stack, 1);
       push(&stack, 2);
       push(&stack, 3);
       printf("%d\n", pop(&stack)); // Should print 3
       // Continue popping to test
   }
   

Conclusion

In this tutorial, you learned how to implement a stack in C using both an array and a linked list. Each approach has its advantages, with arrays providing simple and fast access at the cost of fixed size, while linked lists allow dynamic growth but involve more complex memory management. Consider encapsulation principles when creating your stack to enhance code maintainability and flexibility. Now you can experiment further by creating multiple stacks or implementing additional stack functions like peek or checking if the stack is empty.