What Is Stack in Data Structure in C?

//

Heather Bennett

What Is Stack in Data Structure in C?

A stack is a fundamental data structure in computer science that follows the Last-In-First-Out (LIFO) principle. It is an abstract data type that can be implemented using an array or linked list. In this article, we will explore the concept of stacks in data structures and how they can be implemented in the C programming language.

Stack Operations

A stack primarily supports two main operations:

  • Push: This operation adds an element to the top of the stack.
  • Pop: This operation removes and returns the topmost element from the stack.

Stack Implementation using Arrays

In C, stacks can be implemented using arrays. Let’s consider an example of implementing a stack using an array of integers:

#include <stdio.h>

#define MAX_SIZE 100

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

void push(int item) {
    if (top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    
    stack[++top] = item;
    printf("%d pushed to stack\n", item);
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    
    int item = stack[top--];
    return item;
}

int main() {
    push(10);
    push(20);
    push(30);
    
    printf("%d popped from stack\n", pop());
    
    return 0;
}

In this example, we define a maximum size for our stack using the #define directive. We initialize the stack’s top index top to -1 to indicate an empty stack. The push() function checks if the stack is full before adding an element, and the pop() function checks if the stack is empty before removing an element.

Stack Implementation using Linked List

An alternative way to implement a stack in C is by using a linked list. Each node in the linked list contains an item and a pointer to the next node. Let’s see an example:

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

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

struct Node* top = NULL;

void push(int item) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory Allocation Failed\n");
return;
}

newNode->data = item;
newNode->next = top;
top = newNode;

printf("%d pushed to stack\n", item);
}

int pop() {
if (top == NULL) {
printf("Stack Underflow\n");
return -1;
}

struct Node* temp = top;
int item = temp->data;

top = top->next;

free(temp);

return item;
}

In this example, we define a structure Node that represents each node of the linked list. The push() function creates a new node, assigns the item value, and updates the top pointer to point to the new node. The pop() function removes the topmost node from the stack and returns its item value.

Both array-based and linked list-based implementations have their own advantages and disadvantages. The choice of implementation depends on the specific requirements of your application.

Conclusion

In summary, a stack is a data structure that follows the Last-In-First-Out (LIFO) principle. It can be implemented using arrays or linked lists in C. Stacks are commonly used in various algorithms and applications, such as expression evaluation, function call management, and backtracking.

Understanding stacks is essential for any programmer as they serve as a foundation for more complex data structures and algorithms.