Your Progress

5/30 completed

17% complete. Continue learning to master DSA!

Stacks in Data Structures

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates: the last plate placed on top is the first one to be removed.

Key Takeaways

Stacks follow the LIFO (Last-In-First-Out) principle
Main operations: push (add), pop (remove), peek (view top element)
All stack operations have O(1) time complexity
Stacks can be implemented using arrays or linked lists
Common applications include function call management, expression evaluation, and undo mechanisms

What is a Stack?

A stack is a linear data structure that follows a particular order for operations. The order may be LIFO (Last In First Out) or FILO (First In Last Out). In a stack, insertion and deletion operations are performed at only one end, called the "top" of the stack.

Key Characteristics of Stacks

Stacks are simple yet powerful data structures that enforce a specific order of operations. They have a fixed set of operations and can be efficiently implemented with arrays or linked lists. Stacks are fundamental to many algorithms and system processes.

Visual Representation of a Stack

Item 3 (Top)

Item 2

Item 1 (Bottom)

A stack with 3 elements, with push and pop operations at the top

Note: The element at the top of the stack is the only one accessible at any time. To access elements deeper in the stack, you must first remove the elements above them.

Basic Stack Operations

A stack supports the following basic operations:

Operation	Description	Time Complexity
Push	Adds an element to the top of the stack	O(1)
Pop	Removes the top element from the stack	O(1)
Peek (or Top)	Returns the top element without removing it	O(1)
isEmpty	Checks if the stack is empty	O(1)
isFull	Checks if the stack is full (for array-based implementations)	O(1)
Size	Returns the number of elements in the stack	O(1)

Efficiency Insight

All stack operations have O(1) time complexity, making stacks highly efficient for their intended use cases. This constant-time performance is a key reason why stacks are used in various system processes and algorithms.

Stack Implementation

Stacks can be implemented in two main ways: using arrays or linked lists. Let's explore both approaches:

Array-based Stack

Simple implementation using a regular array
Size is typically fixed unless using dynamic arrays
Memory efficient as no extra references are stored
May waste space if allocated array is too large
Can lead to stack overflow if fixed size is exceeded

Linked List-based Stack

Dynamic size that grows and shrinks as needed
No risk of overflow (memory permitting)
Uses more memory due to storage of pointers/references
Slightly more complex implementation
Allocates memory as needed, no wastage

Let's implement stacks in different programming languages:

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_SIZE 100
6
7// Array-based stack implementation
8typedef struct {
9    int items[MAX_SIZE];
10    int top;
11} Stack;
12
13// Initialize stack
14void initialize(Stack *s) {
15    s->top = -1;
16}
17
18// Check if stack is full
19bool isFull(Stack *s) {
20    return s->top == MAX_SIZE - 1;
21}
22
23// Check if stack is empty
24bool isEmpty(Stack *s) {
25    return s->top == -1;
26}
27
28// Push operation
29bool push(Stack *s, int value) {
30    if (isFull(s)) {
31        printf("Stack Overflow!\n");
32        return false;
33    }
34    
35    s->items[++(s->top)] = value;
36    return true;
37}
38
39// Pop operation
40int pop(Stack *s) {
41    if (isEmpty(s)) {
42        printf("Stack Underflow!\n");
43        return -1; // Assuming -1 is not a valid stack element
44    }
45    
46    return s->items[(s->top)--];
47}
48
49// Peek operation
50int peek(Stack *s) {
51    if (isEmpty(s)) {
52        printf("Stack is empty!\n");
53        return -1;
54    }
55    
56    return s->items[s->top];
57}
58
59// Size of stack
60int size(Stack *s) {
61    return s->top + 1;
62}
63
64int main() {
65    Stack stack;
66    initialize(&stack);
67    
68    push(&stack, 10);
69    push(&stack, 20);
70    push(&stack, 30);
71    
72    printf("Top element: %d\n", peek(&stack));
73    printf("Stack size: %d\n", size(&stack));
74    
75    printf("Popped element: %d\n", pop(&stack));
76    printf("Popped element: %d\n", pop(&stack));
77    
78    printf("Stack size after popping: %d\n", size(&stack));
79    printf("Top element after popping: %d\n", peek(&stack));
80    
81    return 0;
82}

Common Stack Issues

Be aware of these common issues when working with stacks:
- Stack Overflow: Occurs when trying to push to a full stack (in fixed-size implementations)
- Stack Underflow: Occurs when trying to pop from an empty stack
- Memory Leaks: In languages without garbage collection, improper stack implementation can lead to memory leaks

Applications of Stacks

Stacks are used in a wide variety of applications due to their LIFO nature:

Function Call Management

Programming languages use a call stack to keep track of function calls. When a function is called, its context is pushed onto the stack. When the function returns, its context is popped, and control returns to the calling function.

Expression Evaluation

Stacks are used to evaluate expressions (infix, postfix, prefix). For example, in postfix expression evaluation, operands are pushed onto a stack, and when an operator is encountered, the required operands are popped, the operation is performed, and the result is pushed back.

Undo Mechanism

Many applications use stacks to implement undo functionality. Each action is pushed onto a stack, and when the user wants to undo, the most recent action is popped and reversed.

Backtracking Algorithms

In problems like maze solving, stacks are used to keep track of the path taken. When a dead end is reached, backtracking is done by popping from the stack.

Parsing and Syntax Analysis

Compilers and interpreters use stacks for parsing and syntax checking. For example, stacks are used to check if parentheses are balanced in an expression.

Browser History

Web browsers use stacks to implement the back button functionality. Each page you visit is pushed onto a stack, and when you click the back button, the current page is popped, and the previous page is displayed.

Next Steps

Now that you understand stacks, you're ready to explore more complex data structures and algorithms:

Queues-Learn about the First-In-First-Out (FIFO) data structure
Recursion-Understand how stacks are used in recursive function calls
Expression Evaluation-Learn how to use stacks to evaluate mathematical expressions

Introduction to DSA

Basic Data Structures

Advanced Data Structures

Searching Algorithms

Sorting Algorithms

Advanced Algorithms