Introduction to Stack Data Structure

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. In linear data structures, elements are stored sequentially, where each element has a unique predecessor and successor (except for the first and last elements). Other common linear data structures include arrays and linked lists. A stack works by adding (pushing) elements to the top and removing (popping) elements from the top, making it a simple yet powerful structure for managing data where the most recently added item is needed first.

The following diagram shows, how the elements are pushed into the stack. Stack maximum size = 03.

Fixed Size (03) Stack push Operation

Following diagram shows, hows the elements are poped from the stack

Fixed Size (03) Stack pop Operation

Real Life Example: When plates are stacked one on top of another, the last plate added is the first one to be removed, following the Last In, First Out (LIFO) principle. Removing a plate from the middle is not possible without first rearranging the plates above it.

You cannot directly access the any element (or any arbitrary element) of a stack in its standard implementation because stacks follow the Last-In-First-Out (LIFO) principle. This means you can only access or remove the topmost element of the stack.

C programming Example: If you need to access the 3rd element specifically, you would have to:

  • Pop elements from the stack one by one until you reach the 3rd element.
  • Store the popped elements temporarily.
  • After accessing the desired element, push the popped elements back onto the stack in their original order to restore the stack.

Key Operations of a Stack

The key operations of a stack are:

  1. Push: Add an element to the top of the stack.
  2. Pop: Remove and return the element from the top of the stack.
  3. Peek (or Top): Return the element at the top of the stack without removing it.
  4. IsEmpty: Check if the stack is empty (i.e., it contains no elements).
  5. IsFull: Check if the stack is full (i.e., no more elements can be added).
  6. Size: Return the Maximum capacity of the stack..
  7. count(): Returns the total number of elements present in the stack.
  8. change(): Updates the element at the specified position in the stack.
  9. display(): Displays all the elements currently in the stack.

Types of Stack

Stack can either be Fixed-size or Dynamic size just like array. 

1. Fixed-size Stack

A fixed-size stack uses a predefined amount of memory to store elements. The size of the stack is determined when it is created and cannot be changed during execution. The maximum capacity is set at the time of creation (e.g., MAX = 3).

Fixed Size Advantages are

  • Simple Implementation: A fixed-size stack is easier to implement since it relies on a predefined array size.
  • Memory Efficiency: It uses a fixed amount of memory, so the memory allocation is known in advance and can be optimized.
  • Faster Execution: Operations like push and pop are faster because there’s no need to manage memory dynamically.
  • Predictable: The maximum size is predetermined, so it provides a predictable, consistent performance.

Fixed Size Disadvantages are

  • Limited Capacity: If the stack reaches its maximum size, you can’t add more elements, which may lead to overflow.
  • Wasted Memory: If the stack is not filled to its maximum capacity, memory may go unused, leading to inefficiency.
  • Inflexible: The size cannot be adjusted during runtime, making it unsuitable for cases where the number of elements is unknown or varies greatly.

2. Dynamic Size Stack:

A dynamic stack adjusts its size as needed, often using a linked list or dynamically allocated array. This allows it to grow and shrink based on the number of elements at runtime. Memory is allocated dynamically at runtime (e.g., using malloc in C or new in C++).

Dynamic Stack Advantages are

  • Flexible Size: The stack can grow and shrink dynamically, allowing it to handle an unknown or varying number of elements.
  • No Wasted Memory: Memory is allocated as needed, ensuring that only the required amount is used.
  • Better for Large Data: Since the stack size is not limited, it can handle large amounts of data more effectively.

Dynamic Stack Disadvantages are

  • Complex Implementation: It requires more complex code, usually involving pointers and dynamic memory allocation.
  • Memory Overhead: The dynamic memory allocation process introduces overhead for each operation, making it slower compared to a fixed-size stack.
  • Potential Memory Leaks: If memory is not managed correctly, it can lead to memory leaks (unreleased memory).
  • Fragmentation: Over time, if the stack grows and shrinks frequently, it can lead to memory fragmentation.

Stack Implementation

Stacks can also be implemented using other data structures:

  1. Arrays: A stack can be implemented using an array, where elements are added and removed from one end (usually called the top). This implementation is simple, but resizing the array can become costly if the stack grows too large or shrinks too small.
  2. Linked Lists: A stack can be implemented using a linked list where each node represents an element. The head (or top) of the linked list serves as the top of the stack, and elements are added or removed by manipulating the head pointer.

Applications of Stack

Stacks have various applications in computer science and everyday computational tasks. Here are some of the primary applications of stack:

  • Function Call Management: Manages recursive function calls using the call stack.
  • Expression Evaluation: Evaluates postfix or prefix expressions efficiently.
  • Expression Conversion: Converts infix expressions to postfix or prefix forms.
  • Undo Mechanism: Implements undo/redo operations in text editors.
  • Backtracking: Supports algorithms like DFS and maze-solving by storing paths.
  • Syntax Parsing: Validates and parses code structures like parentheses or braces.
  • Browser Navigation: Tracks web page history for back and forward navigation.
  • Memory Management: Allocates runtime memory for function calls and local variables.
  • Symbol Balancing: Ensures balanced parentheses, brackets, and braces in expressions.
  • Pathfinding Algorithms: Implements backtracking to find paths in grids or mazes.
  • Sorting Algorithms: Manages iterative quicksort and similar algorithms.

Stack Implementation Code in C

#include <stdio.h>
#define MAX 3 // Define the maximum size of the stackint stack[MAX];
int top = -1;

// Push function
void push(int value) {
if (top == MAX – 1) {
printf(“Stack Overflow\n”);
} else {
stack[++top] = value;
}
}

// Pop function
int pop() {
if (top == -1) {
printf(“Stack Underflow\n”);
return -1; // Indicates error
} else {
return stack[top–];
}
}

// Function to print stack elements
void printStack() {
if (top == -1) {
printf(“Stack is empty\n”);
} else {
printf(“Stack elements: “);
for (int i = 0; i <= top; i++) {
printf(“%d “, stack[i]);
}
printf(“\n”);
}
}

int main() {
// Push elements onto the stack
push(5);
push(10);
push(40);

// Print the stack
printStack();

// Pop an element
int poppedValue = pop();
printf(“Popped value: %d\n”, poppedValue);

// Print the stack again
printStack();

return 0;
}

Output:

Stack elements: 5 10 40
Popped value: 40
Stack elements: 5 10

Important: In many stack implementations, an array is used to store the stack elements. So, first element index should 0 for convenience.