What Is Stack in Data Structure C?

//

Larry Thompson

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

What is a Stack?

A stack is an abstract data type that represents a collection of elements. It has two main operations: push and pop. The push operation adds an element to the top of the stack, while the pop operation removes and returns the topmost element from the stack.

The LIFO Principle

The Last-In-First-Out (LIFO) principle means that the last element added to the stack will be the first one to be removed. Think of it as stacking plates – you always place a new plate on top and remove the topmost plate when you need one.

Stack Implementation in C

In C, we can implement a stack using either arrays or linked lists. Let’s first look at how we can create a stack using an array.

Using Arrays

To implement a stack using an array, we need to define a fixed-size array and keep track of the top index. Here’s how it can be done:

#define MAX_SIZE 100

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

void push(int element) {
    if (top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    
    stack[++top] = element;
}

int pop() {
    if (top < 0) {
        printf("Stack Underflow\n");
        return -1; // or any other sentinel value
    }
    
    return stack[top--];
}

The push() function adds an element to the top of the stack. It first checks if the stack is full before adding the element.

If the stack is full, it prints "Stack Overflow" and returns. Otherwise, it increments the top index and assigns the element to that position in the array.

The pop() function removes and returns the topmost element from the stack. It first checks if the stack is empty before removing an element. If the stack is empty, it prints "Stack Underflow" and returns a sentinel value (-1 in this case) or performs any other desired error handling.

Using Linked Lists

An alternative way to implement a stack in C is by using linked lists. Each node in the linked list contains an element and a pointer to the next node.

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

struct Node* top = NULL;

void push(int element) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    
    newNode->data = element;
    newNode->next = top;
    
    top = newNode;
}

int pop() {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return -1; // or any other sentinel value
    }
    
    struct Node* temp = top;
    int poppedElement = temp->data;
    
    top = top->next;
    
    free(temp);
    
    return poppedElement;
}

The push() function creates a new node and assigns the element to it. It then updates the next pointer of the new node to point to the current top node. Finally, it updates the top pointer to point to the new node, making it the topmost element in the stack.

The pop() function removes and returns the topmost element from the stack. It first checks if the stack is empty.

If so, it prints "Stack Underflow" and returns a sentinel value (-1 in this case). Otherwise, it assigns the data of the top node to a variable, updates the top pointer to point to the next node, frees up memory for the removed node, and returns the popped element.

Conclusion

In this article, we explored stacks in C and learned how they can be implemented using arrays or linked lists. Stacks are widely used in various algorithms and applications, such as expression evaluation, backtracking, and managing function calls in programming languages. Understanding stacks is essential for any programmer looking to dive deeper into data structures and algorithms.

Now that you have a solid understanding of stacks in C, you can experiment with different operations on stacks or explore more advanced topics like stack-based algorithms.

Happy coding!

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy