A Complete Guide on Stack Using Array in C

A stack is a form of linear data structure that has a group of the same type elements arranged in a particular sequence. It operates on the basic principle of "Last In, First Out" (LIFO). As a result, the most recent addition will be the first item removed from the stack.

Important Elements of Stack 

• Push: This process places a new element at the top of the stack.
• Pop: The element at the top of the stack is removed with this action.
• isEmpty: Checking whether the stack is empty.
• isFull: Checking whether the stack is full.
• Top: Displaying the topmost element of the stack.
• Size: Returns the number of elements currently in the stack.
• Peek: The top element is retrieved without eliminating it.

Characteristics of a Stack 

• LIFO Principle: The most recently added item is always the first to be removed.
• Single Endpoint: All operations (push and pop) are performed at one end, known as the "top" of the stack.
• Dynamic Size: The size of the stack changes as elements are pushed or popped, which allows it to grow or shrink as needed.
• Sequential Access: Items can only be accessed sequentially, starting from the top and going down.
• Memory Efficient: In some implementations, a stack uses memory only when elements are pushed, avoiding wastage by growing or shrinking as needed.
• Last-Added Access: You can always access only the last added element without needing to traverse through other elements.
• Atomic Operations: Stack operations such as push and pop are atomic, meaning they are performed as single, uninterrupted actions.
• Data Integrity: The stack ensures that elements are processed in the correct order, especially useful in function calls and recursion scenarios.

Applications of the Stack Using Array in C

Stacks are highly used in computer programming and algorithms because of their efficient way of handling data. Some common applications include:

• Function Call Management (Call Stack): During program execution, function calls and their local variables are managed using a stack to keep track of active functions.
• Undo Mechanism: In applications like text editors, stacks are used to store previous states that enable the undo feature.
• Syntax Parsing: Stacks help in evaluating mathematical expressions and checking for balanced symbols like parentheses in code.
• Backtracking Algorithms: Algorithms that involve exploring different possibilities, such as solving mazes or puzzles, use stacks to keep track of paths or states that need to be revisited.
• In Browsers: Web browsers use stacks to control browsing history. The previous and consecutive web pages are stacked as you travel back or forth, making it simple to go back or forward.

Implementing a stack using array in C offers several advantages, especially for beginners. Here's why:

1. Simplicity in Implementation

Arrays are fundamental data structures in most programming languages, making them straightforward to use for implementing stacks. This simplicity is beneficial for beginners learning data structures.

2. Efficient Memory Usage

Arrays allocate memory in contiguous blocks, which can be more memory-efficient compared to other structures like linked lists that require additional memory for pointers.

3. Constant Time Operations

Operations like push (insertion) and pop (deletion) can be executed in constant time, O(1), when using arrays, as they only involve adding or removing elements at the end of the array. (This will be covered in more detail in the later sections).

4. Ease of Access

Accessing elements in an array is straightforward using indices, which can be helpful for certain stack operations like peek (viewing the top element).

5. Predictable Memory Allocation

Since arrays have a fixed size, the memory allocation is predictable, which can be advantageous in systems where memory management is critical.

Advantages of Stack Using Array in C

1. Efficient Memory Usage

Arrays do not require additional memory for pointers, leading to efficient memory utilization compared to linked lists.

2. Easy Implementation

Arrays provide a simple way to implement stacks, making them ideal for beginners learning data structures.

3. Improved Cache Performance

The contiguous memory allocation of arrays enhances cache locality, resulting in faster access times.

4. Predictable Memory Allocation

Since the size of the array is defined at the start, memory allocation is predictable and managed efficiently.

5. Simplified Memory Management

With arrays, there's no need for dynamic memory allocation or deallocation during stack operations, reducing complexity.

Disadvantages of Stack Using Array in C

1. Fixed Size Limitation

The stack size must be predetermined, which can lead to a stack overflow if the limit is exceeded.

2. Lack of Flexibility

Arrays cannot dynamically resize during runtime, making it challenging to handle varying data loads efficiently.

3. Complex Resizing Process

To increase the stack size, a new larger array must be created, and existing elements copied over, which is time-consuming.

4. Limited Access Operations

Only the top element of the stack is accessible directly; accessing other elements requires additional operations.

5. Not Ideal for Frequent Size Changes

For applications where the stack size changes frequently, array-based implementation can be less efficient compared to dynamic structures.

Here is an example program of a stack using array in C:

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

#define MAX 100

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

// Sample array to be pushed into stack
int inputArray[] = {10, 20, 30, 40, 50};
int inputSize = sizeof(inputArray) / sizeof(inputArray[0]);
int inputIndex = 0;

// Check if stack is empty
int isEmpty() {
    return top == -1;
}

// Check if stack is full
int isFull() {
    return top == MAX - 1;
}

// Push operation
void push() {
    if (inputIndex >= inputSize) {
        printf("No more elements to push from array.\n");
        return;
    }
    if (isFull()) {
        printf("Stack Overflow! Cannot push more elements.\n");
        return;
    }
    int value = inputArray[inputIndex++];
    stack[++top] = value;
    printf("Pushed %d into the stack.\n", value);
}

// Pop operation
void pop() {
    if (isEmpty()) {
        printf("Stack Underflow! Nothing to pop.\n");
    } else {
        printf("Popped %d from the stack.\n", stack[top--]);
    }
}

// Peek operation
void peek() {
    if (isEmpty()) {
        printf("Stack is empty.\n");
    } else {
        printf("Top element is: %d\n", stack[top]);
    }
}

// Display stack
void display() {
    if (isEmpty()) {
        printf("Stack is empty.\n");
    } else {
        printf("Stack elements: ");
        for (int i = 0; i <= top; i++) {
            printf("%d ", stack[i]);
        }
        printf("\n");
    }
}

int main() {
    int choice;

    while (1) {
        printf("\n--- Stack Using Array (with predefined input) ---\n");
        printf("1. Push Next Element from Array\n");
        printf("2. Pop\n");
        printf("3. Peek (Top Element)\n");
        printf("4. Display Stack\n");
        printf("5. Exit\n");
        printf("Enter your choice (1-5): ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                push();
                break;

            case 2:
                pop();
                break;

            case 3:
                peek();
                break;

            case 4:
                display();
                break;

            case 5:
                printf("Exiting... Thank you!\n");
                exit(0);

            default:
                printf("Invalid choice! Please enter between 1 to 5.\n");
        }
    }

    return 0;
}

Explanation

1. The above stack program in C using array starts with a list of numbers: 10, 20, 30, 40, 50.
2. You can push these numbers into the stack one by one by choosing the "Push" option.
3. The "Pop" option removes the last pushed number from the top of the stack.
4. The "Peek" option shows which number is currently at the top, without removing it.
5. The "Display" option shows all the numbers currently in the stack, from bottom to top.
6. The "Exit" option ends the program.

The program also checks if:

• The stack is full before pushing (so you don’t add too many).
• Before popping or peeping, the stack is empty to ensure that nothing is removed.

Output

--- Stack Using Array (with predefined input) ---
1. Push Next Element from Array
2. Pop
3. Peek (Top Element)
4. Display Stack
5. Exit
Enter your choice (1-5): 1
Pushed 10 into the stack.

--- Stack Using Array (with predefined input) ---
1. Push Next Element from Array
2. Pop
3. Peek (Top Element)
4. Display Stack
5. Exit
Enter your choice (1-5): 2
Popped 10 from the stack.

--- Stack Using Array (with predefined input) ---
1. Push Next Element from Array
2. Pop
3. Peek (Top Element)
4. Display Stack
5. Exit
Enter your choice (1-5): 3
Stack is empty.

Stack Operations in C

Stacks provide multiple operations that allow us to manage data effectively. One of the most important operations is the Push operation, especially when implementing a stack using array in C.

1. Push Operation In C

​In a stack, the push operation adds a new element to the top. Before performing this operation, it is essential to check if there is enough space in the stack to avoid overflow.

Example

void push(int value) {
    stack[++top] = value; // Add value to top
    printf("Pushed %d\n", value);
}

2. Pop Operation

By using the pop operation, the element at the top of the stack is removed. Before performing this operation in stack, it is important to check whether the stack is empty to prevent underflow errors.

Example

void pop() {
    top--; // Remove top element
    printf("Popped element\n");
}

3. Peek Operation

This operation lets you view the top element of the stack without eliminating it. This is useful when you need to check the current top value but want to keep the stack unchanged. When implementing a stack using array in C, this operation ensures that you can access the top element efficiently without modifying the data structure.

Example

void peek() {
    printf("Top element: %d\n", stack[top]); // Show top element
}

4. Display Operation

Every element in the stack is printed by the display action, starting at the top. This helps in visualizing the stack's present condition.

Example

void display() {
    for (int i = 0; i <= top; i++) { // Print each element
        printf("%d ", stack[i]);
    }
    printf("\n");
}

5. isEmpty() Implementation

To check if the stack in an array is empty, the isEmpty() function is used. It gives 0 (false) otherwise, and 1 (true) if the stack is empty. This function helps in avoiding underflow errors during operations like pop() and peek().

Example

int isEmpty() {
    return top == -1; // Returns true if empty
}

6. isFull() Implementation

The isFull() function is used to check whether the stack has reached its maximum capacity in stack using array in C. This helps prevent stack overflow errors when attempting to add new elements.

Example

int isFull() {
    return top == MAX - 1; // Returns true if full
}

Here is the time and space complexity for the operations of stack using array in C:

Implementing a stack using array in C programming provides a strong foundation for understanding stack operations. Although array-based stacks have limitations, such as a fixed size and potential memory wastage, they are straightforward to implement and highly efficient for applications that do not require dynamic resizing.

Mastering stack operations allows you to use this data structure in various algorithms and programming scenarios. Thus, making it an essential concept in computer science and software development.

1. What is a stack in C?

A stack is a data structure that stores items in a Last In, First Out (LIFO) order, which means the last item added is the first one removed.

2. How do you implement a stack using an array in C?

You can create a stack using an array by tracking the top element’s index. Essential operations are push (add), pop (remove), and peek (view top item).

3. What are the basic stack operations in C?

• Push: Add an item to the top.
• Pop: Remove the top item.
• Peek: View the top item without removing it.
• isEmpty: Check if the stack is empty.
• isFull: Check if the stack is full.

4. What happens when you try to pop from an empty stack?

Popping from an empty stack causes an underflow error, which means there’s nothing to remove. This should be handled with error checks in the code.

5. What is stack overflow?

Stack overflow happens when you try to push an item onto a full stack, exceeding its storage limit.

6. Can a stack be implemented using linked lists instead of arrays?

Yes, stacks can be built with linked lists, which allows dynamic size and avoids overflow. But they need extra memory for pointers.