What is Stack in C - Naukri Code 360

Introduction

A stack is a basic data structure in computer programming that follows the Last In First Out (LIFO) principle. It means that the last element added to the stack will be the first one to be removed. Imagine a stack of plates where you can only add or remove plates from the top.

In this article, we will learn about the stack data structure, its operations, time complexity, types, applications & implementation using arrays & linked lists.

What is a Stack Data Structure in C?

A stack is a collection where you can add or remove items only from the top. This means that the last item you put in is the first one to come out. In technical terms, this is often abbreviated as LIFO, standing for Last In, First Out. Using a stack is like stacking plates; you can only remove the top plate without disturbing the others below it.

In programming, a stack is used to handle tasks where you need to reverse things or backtrack steps. For example, when a computer runs a program and needs to remember the point it needs to return to after completing a function, it uses a stack to keep track of these points.

Here's a simple code example in C to demonstrate creating a stack:

C

#include <stdio.h>

#define MAX 10  // Defining the maximum size of the stack

int count = 0;  // This will keep track of the number of items in the stack

// This is the stack, an array of integers

int stack[MAX];

// Function to add data to the stack

void push(int data) {

    if (count < MAX) {

        stack[count] = data;  // Place data at the top of the stack

        count++;  // Increase the count of items in the stack

    } else {

        printf("Stack is full\n");

    }

}

// Function to remove data from the stack

int pop() {

    if (count > 0) {

        count--;  // Decrease the count of items

        return stack[count];  // Return the top item from the stack

    } else {

        printf("Stack is empty\n");

        return -1;  // Return an error value

    }

}

int main() {

    push(10);  // Add number 10 to the stack

    push(20);  // Add number 20 to the stack

    printf("Item popped: %d\n", pop());  // Should print "Item popped: 20"

    return 0;

}

You can also try this code with Online C Compiler

Run Code

Output

Item popped: 20

In this example, the push function is used to add items to the top of the stack, and the pop function is used to remove the item from the top. The code is straightforward and shows how items are added and removed following the LIFO principle.

Basic Operations on Stack in C Programming

When using a stack in programming, there are several key operations that you can perform. These operations are essential for manipulating the data within the stack and include pushing, popping, and peeking.

Push Operation

The push operation involves adding an element to the top of the stack. When you push an item, it becomes the new top, and all other elements move down one position in the stack hierarchy. This operation is crucial for building up the stack with the data you need to store or process later.

Pop Operation

The pop operation removes the top element from the stack. This is useful when you need to retrieve the most recently added data, adhering to the LIFO principle. After popping, the element below the top becomes the new top of the stack.

Peek Operation

The peek operation allows you to look at the top element of the stack without removing it. This is particularly useful for checking what's on top of the stack before deciding to remove it. It helps in scenarios where you need to make decisions based on the top value without altering the stack's state.

Here's how these operations can be implemented in C:

C

#include <stdio.h>
#define MAX 10  // Maximum size of the stack

int top = -1;  // This indicates that the stack is initially empty
int stack[MAX];  // Stack array declaration

// Function to add element to the stack
void push(int value) {
    if (top < MAX - 1) {  // Check if the stack is not full
        top++;  // Increment top index
        stack[top] = value;  // Set top value
        printf("%d pushed to stack\n", value);
    } else {
        printf("Error: stack overflow\n");
    }
}

// Function to remove element from the stack
int pop() {
    if (top > -1) {  // Check if the stack is not empty
        int popped_value = stack[top];  // Get the top value
        top--;  // Decrement top index
        return popped_value;
    } else {
        printf("Error: stack underflow\n");
        return -1;  // Return an error value
    }
}

// Function to get the top element of the stack
int peek() {
    if (top > -1) {  // Check if the stack is not empty
        return stack[top];  // Return the top value
    } else {
        printf("Stack is empty\n");
        return -1;  // Return an error value
    }
}

int main() {
    push(10);
    push(20);
    push(30);
    printf("Top element is %d\n", peek());  // Should print "Top element is 30"
    printf("Element popped: %d\n", pop());  // Should print "Element popped: 30"
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

10 pushed to stack
20 pushed to stack
30 pushed to stack
Top element is 30
Element popped: 30

This code provides a clear example of how stacks are manipulated through push, pop, and peek operations in C. Each function is designed to handle a specific aspect of stack interaction, ensuring that the stack's integrity is maintained throughout its use.

Time Complexity of Stack Operations

Understanding the time complexity of operations on a stack is crucial for evaluating how efficient they are, especially when you use stacks in more complex algorithms. In computer science, time complexity is a way to describe how the execution time of operations changes relative to the size of the input data. For stack operations, this is relatively straightforward since most operations take a constant amount of time.

Constant Time Complexity: O(1)

The primary operations on a stack—push, pop, and peek—all have a time complexity of O(1), often referred to as constant time complexity. This means that no matter how many items are in the stack, these operations take the same amount of time to execute. Here's why each operation falls into this category:

Push: Adding an item to the top of the stack doesn’t depend on the stack's size. You are simply placing a new item at the top position, which is always accessible, regardless of how many items are below it.
Pop: Removing the top item from the stack is similar in efficiency. You don’t need to move or check the other items in the stack; you just take off the top item.
Peek: Looking at the top item without removing it is also independent of the stack’s size. You're directly accessing the item at the top, which is always at the same position regardless of stack size.

Why It Matters

The O(1) time complexity of these operations makes stacks an excellent choice for certain types of algorithms where quick, last-in, first-out access to data is necessary. For instance, in undo mechanisms in software applications or for backtracking algorithms where you need to reverse actions or navigate back to previous states efficiently.

Here’s a simple C function to demonstrate that each operation maintains its efficiency regardless of the stack's size:

C

#include <stdio.h>
#define MAX 1000  // Large stack size for demonstration

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

void push(int value) {
    if (top < MAX - 1) {
        stack[++top] = value;
    } else {
        printf("Stack overflow\n");
    }
}

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

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

int main() {
    for (int i = 0; i < 1000; i++) {
        push(i);  // Pushing 1000 items to demonstrate efficiency does not change
    }
    printf("Top element is %d\n", peek());  // Constant time access to the top element
    while (top != -1) {
        pop();  // Constant time removal of each element
    }
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Top element is 999

This code shows how stack operations maintain their efficiency even as the size of the stack increases to a large number. Each operation remains quick and efficient, showcasing the practical advantage of using stacks in programming.

Types of Stacks in C

In programming, different types of stacks are utilized to address various needs and scenarios. Each type of stack is tailored to specific uses based on their structure and the way they manage data. Here, we'll explore some of the common types of stacks and how they differ from one another.

Array-Based Stacks

Array-based stacks are the most straightforward type of stack, where a fixed-size array is used to store stack elements. The size of the stack is defined at the time of creation, which means it cannot grow or shrink dynamically. This simplicity allows for quick access and modification, as elements are directly accessed through their indices.

Linked List Stacks

Unlike array-based stacks, linked list stacks use dynamically allocated nodes to store data. Each node contains the data and a reference (or link) to the next node in the stack. This type of stack can grow as needed, without a predefined limit, making it more flexible than an array-based stack. Operations on a linked list stack still operate in constant time, providing the same efficiency in terms of time complexity.

Dynamic Stacks

Dynamic stacks are an extension of array-based stacks where the size of the stack can grow dynamically. They start with an initial size, but when more space is needed, a new, larger array is created, and elements are copied from the old array to the new one. This allows for a flexible size while maintaining the direct access benefit of arrays.

Circular Stacks

Circular stacks are a variation where the stack is treated as circular, meaning that it can wrap around to the beginning of the storage array when the end is reached, assuming the stack isn’t full. This is particularly useful in applications like buffer management where a fixed amount of space must be used efficiently.

Double-Ended Stacks

Double-ended stacks, or dequeues, allow data to be added or removed from both ends of the stack. This flexibility makes them useful in scenarios where elements need to be processed from both ends intermittently.

Here’s how you might implement a linked list stack in C:

C

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

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

Node* top = NULL;

void push(int value) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Failed to allocate memory.\n");
    } else {
        newNode->data = value;
        newNode->next = top;
        top = newNode;
    }
}

int pop() {
    if (top == NULL) {
        printf("Stack is empty.\n");
        return -1;
    } else {
        Node* temp = top;
        int popped = top->data;
        top = top->next;
        free(temp);
        return popped;
    }
}

void displayStack() {
    Node* temp = top;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    displayStack();  // Display stack elements
    printf("Popped: %d\n", pop());  // Pop one element
    displayStack();  // Display stack elements after pop
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

30 20 10 
Popped: 30
20 10

This code demonstrates a basic linked list stack where new elements are added to the top, and removal also takes place from the top. The dynamic nature of the linked list allows the stack to expand as needed without a predefined size limit.

Applications of the Stack Data Structure

Stacks are a versatile data structure used in various programming scenarios due to their unique Last In, First Out (LIFO) characteristic. This section discusses some key applications of stacks in computer science and programming.

Function Calls and Recursion

One of the most common uses of stacks is in managing function calls, particularly in recursive programming. When a function is called, its execution information, such as local variables and the return address, is saved on a call stack. This allows the program to return to the correct point in the program after the function completes. In recursive functions, where functions call themselves, stacks are essential to keep track of each call.

Undo Mechanisms in Software

Stacks are instrumental in implementing undo mechanisms in software applications. Actions performed in software like text editors, graphic design tools, or even web browsers can be reversed using an undo feature. Each action is pushed onto a stack, and when the user selects to undo an action, the most recent action is popped from the stack and reversed.

Expression Evaluation

Stacks are used to evaluate and convert expressions, especially arithmetic expressions. For example, stacks can convert infix expressions (like A + B) to postfix expressions (A B +) or prefix expressions (+ A B). These forms are easier for computers to evaluate quickly. Stacks are also used to evaluate these postfix or prefix expressions directly.

Syntax Parsing

Compilers use stacks for syntax parsing in programming languages. They help check the syntax of expressions and commands by matching opening and closing elements such as parentheses, brackets, and braces. This ensures that the code written by programmers adheres to the correct syntax and structure.

Backtracking Algorithms

In algorithms that require backtracking, such as solving a maze or puzzle (like Sudoku), stacks can be used to remember previous states. When an attempt to solve the problem fails, the algorithm can backtrack to the last saved state by popping from the stack and try a different path or solution.

Here's a simple example in C to demonstrate using a stack for reversing a string, which is a basic application of stack's LIFO characteristic:

C

#include <stdio.h>
#include <string.h>
#define MAX 100  // Maximum size of the stack

char stack[MAX];
int top = -1;

// Function to push a character onto the stack
void push(char ch) {
    if (top < MAX - 1) {
        stack[++top] = ch;
    } else {
        printf("Stack overflow\n");
    }
}

// Function to pop a character from the stack
char pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return -1;
    } else {
        return stack[top--];
    }
}

// Main function to demonstrate reversing a string using a stack
int main() {
    char str[] = "Hello, world!";
    int n = strlen(str);
    for (int i = 0; i < n; i++) {
        push(str[i]);  // Push each character of the string onto the stack
    }
    for (int i = 0; i < n; i++) {
        str[i] = pop();  // Pop each character and overwrite the string
    }
    printf("Reversed string: %s\n", str);
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Reversed string: !dlrow ,olleH

This code pushes each character of a string onto a stack and then pops them back into the string, effectively reversing the order due to the LIFO nature of stacks.

Implementing Stack Using Arrays

Implementing a stack using arrays is one of the most straightforward methods in programming due to the static nature of arrays, which means their size doesn't change once defined. This method is efficient and easy to manage because it leverages the simple, direct access nature of arrays.

C

#include <stdio.h>
#define MAX_SIZE 10  // Define the maximum size of the stack

int stack[MAX_SIZE];
int top = -1;  // Initialize top as -1 indicating the stack is empty

// Function to add an element to the stack
void push(int element) {
    if (top < MAX_SIZE - 1) {  // Ensure there is space in the stack
        top++;
        stack[top] = element;
        printf("%d pushed to stack\n", element);
    } else {
        printf("Stack overflow\n");  // Stack is full
    }
}

// Function to remove the top element from the stack
int pop() {
    if (top >= 0) {  // Ensure the stack is not empty
        int poppedElement = stack[top];
        top--;
        return poppedElement;
    } else {
        printf("Stack underflow\n");  // Stack is empty
        return -1;
    }
}

// Function to get the top element of the stack without removing it
int peek() {
    if (top >= 0) {
        return stack[top];
    } else {
        printf("Stack is empty\n");
        return -1;
    }
}

int main() {
    push(5);
    push(10);
    push(20);
    printf("Top element is: %d\n", peek());
    printf("Elements popped: %d, %d\n", pop(), pop());
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

5 pushed to stack
10 pushed to stack
20 pushed to stack
Top element is: 20
Elements popped: 10, 20

Advantages of Implementing Stack Using Arrays

Fast Access: Array-based stacks provide fast access to elements since accessing any element by its index is a constant time operation, O(1). This is particularly beneficial for push and pop operations.
Ease of Implementation: Implementing a stack with an array is straightforward since it only requires managing the index of the top element, making the code simpler and easier to understand.
Memory Localization: The elements of an array are stored contiguously in memory, which can lead to better cache performance due to locality of reference. This makes operations on the stack faster and more efficient in terms of memory access.
No Overhead for Pointers: Unlike linked lists, array-based stacks do not require extra memory for storing pointers, which can lead to more efficient use of memory.
Predictable Resource Allocation: Since the size of an array is fixed at compile-time, it allows for predictable allocation of memory, which can be advantageous in environments with limited or highly regulated memory usage.
Easy to Serialize: Due to their contiguous memory allocation, array-based stacks are easier to serialize (convert to a sequence of bytes) which is useful for saving to disk or transmitting across a network.

Disadvantages of Implementing Stack Using Arrays

Fixed Capacity: The main disadvantage of using arrays is the fixed size, which means that the capacity must be known in advance and cannot be changed dynamically without creating a new array and copying the old elements.
Inefficient Memory Usage: If the allocated array is much larger than the actual data needed, it results in wasted memory space. Conversely, if the stack grows beyond its initial allocation, it can lead to stack overflow.
Potential for Overflow: Since the size is fixed, pushing more elements than the array can accommodate leads to stack overflow, which must be handled to prevent data corruption or unexpected behavior.
Cost of Growing Stack: Increasing the size of an array-based stack involves creating a new, larger array and copying elements from the old array, which can be costly in terms of time and resources.
Less Flexible: Compared to linked-list implementations, arrays offer less flexibility for applications where the maximum size of the stack is unpredictable or subject to change.
Fragmentation Issues: In low-memory environments or systems with heavy memory usage, allocating a large contiguous block of memory for an array can be more difficult and can lead to fragmentation.

Implementing Stack Using Linked List

Using a linked list to implement a stack provides flexibility that isn't possible with arrays. A linked list stack grows dynamically, adjusting to the number of elements without the need for a predefined limit. This method involves creating nodes, each containing data and a reference to the next node, effectively forming a chain.

Step-by-Step Implementation of a Stack Using Linked Lists in C

Step 1: Define the Node Structure

First, we define a structure for the nodes that will make up the stack. Each node will hold an integer data and a pointer to the next node.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;

Here, Node is a structure that contains an integer data and a pointer next to the next Node in the stack.

Step 2: Initialize the Top of the Stack

We need a global pointer that will always point to the top node of the stack. Initially, this pointer (top) will be set to NULL, indicating that the stack is empty.

Node* top = NULL;  // Top of the stack

Step 3: Push Operation

The push operation adds a new node with a given value to the top of the stack. Here's how you can implement it:

void push(int value) {
    Node* newNode = (Node*) malloc(sizeof(Node));  // Allocate memory for a new node
    if (newNode == NULL) {
        printf("Memory allocation failed\n");  // Check if memory allocation was successful
        return;
    }
    newNode->data = value;  // Set the data for the new node
    newNode->next = top;    // Link the new node to the previous top node
    top = newNode;          // Update the top pointer to the new node
    printf("%d pushed to stack\n", value);
}

Memory Allocation: We use malloc to allocate memory for a new node. If memory allocation fails, we output an error message.
Setting Data and Linking: We set the data of the new node and link it to the previous top node.
Updating Top: The top pointer is updated to point to the new node.

Step 4: Pop Operation

The pop operation removes the node at the top of the stack and returns its value. If the stack is empty, it returns an error code.

int pop() {
    if (top == NULL) {
        printf("Stack is empty\n");  // Check if the stack is empty
        return -1;  // Return an error code
    }
    Node* temp = top;       // Temporary pointer to the top node
    int popped = top->data; // Save the data from the top node
    top = top->next;        // Move the top pointer to the next node
    free(temp);             // Free the memory of the old top node
    return popped;          // Return the popped value
}

Checking for Empty Stack: Before attempting to pop, we check if the stack is empty.

Removing the Top Node: We update the top pointer to the next node and free the memory of the removed node.

Step 5: Peek Operation

The peek operation returns the value of the top node without removing it. Like pop, it returns an error code if the stack is empty.

int peek() {
    if (top != NULL) {
        return top->data;  // Return the data of the top node
    } else {
        printf("Stack is empty\n");
        return -1;  // Return an error code if the stack is empty
    }
}

Step 6: Main Function

In the main function, we demonstrate using these operations to manipulate the stack.

int main() {
    push(10);
    push(20);
    push(30);
    printf("Top element is %d\n", peek());  // Display the top element
    printf("Elements popped from stack: %d, %d\n", pop(), pop());  // Pop two elements
    return 0;
}

This main function tests the stack operations by pushing three integers and then popping two, showing how the stack behaves in practice.

Advantages of Linked List Implementation

Dynamic Size: A linked list-based stack can grow and shrink according to the needs of the application, without any predefined limits. This makes it particularly useful for applications with unpredictable or varying size requirements.
Efficient Memory Utilization: Memory is allocated only as needed. Each node is created only when data is pushed onto the stack, which can lead to more efficient use of memory compared to pre-allocating a large array that may not be fully used.
No Stack Overflow: Since nodes are dynamically allocated, there is no risk of stack overflow as long as the system has free memory available, unlike in array-based stacks where a fixed size can lead to overflow errors.
Flexibility in Memory Allocation: Memory for new nodes is allocated as each element is added, which can help manage memory more efficiently in fragmented memory environments.
Simplicity in Growing the Stack: Adding to a linked list involves creating a new node and linking it, which is a straightforward operation that does not require moving or copying other elements.
Individual Element Management: Each element can be managed independently, which can simplify certain types of data management and manipulation tasks within the stack.

Disadvantages of Linked List Implementation

Higher Memory Overhead: Each node in a linked list requires additional memory for the pointer to the next node, in addition to the data itself. This extra memory requirement can add up, especially with a large number of elements.
Greater Complexity in Code: Implementing a stack with a linked list is generally more complex than using an array. This complexity can increase the risk of bugs and errors in the implementation.
Slower Access Times: Because elements are not contiguous in memory, traversing a linked list to access elements can be slower than indexing into an array. However, for standard stack operations like push and pop, this is less of an issue since they only involve the top element.
Memory Fragmentation: Frequent allocation and deallocation of nodes can lead to memory fragmentation, especially in long-running applications.
Performance Overhead from Dynamic Memory Allocation: Each push operation involves a call to malloc (or similar functions), which can be more time-consuming compared to using pre-allocated memory in an array.
Cache Inefficiency: The non-contiguous storage of linked list elements can result in poorer cache performance compared to arrays, which can degrade overall performance in scenarios where access speed is critical.

Frequently Asked Questions

What happens if you try to pop an element from an empty stack?

If you attempt to pop an element from an empty stack, it results in a condition known as "stack underflow." In this case, the function will typically return an error code or message indicating that the stack is empty.

How can you check if a stack is full or empty?

To check if a stack is full, compare the top index with the maximum size of the array minus one (top == MAX_SIZE - 1). To check if a stack is empty, see if the top index is -1 (top == -1).

Is it better to implement a stack using an array or a linked list?

The choice between using an array or a linked list depends on the specific requirements of your application. Arrays provide faster access and efficient memory usage but have a fixed size, while linked lists offer dynamic resizing but with additional memory and performance overhead due to pointers.

Conclusion

In this article, we've learned how stacks can be implemented using both arrays and linked lists in C programming. Each method has its benefits and challenges: arrays are straightforward and efficient for fixed-size data, while linked lists offer flexibility by allowing the stack to grow or shrink as needed. Choosing the right approach depends on your specific requirements, such as how much data you expect to handle and whether you need the ability to resize the stack dynamically.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.