Data Structures using C

Stacks

PreviousNext

Module III: Stacks. A Stack is a linear data structure that follows the Last In First Out (LIFO) principle. The element inserted last is removed first.

Introduction to Stacks

A Stack is a linear data structure in which insertion and deletion operations occur only from one end called TOP. The most recently added element is removed first.

  • Follows Last In First Out (LIFO)
  • Insertion and deletion occur at TOP
  • Simple linear structure
  • Efficient operations

Characteristics of Stack

  • Follows LIFO principle
  • Insertion and deletion occur at one end
  • Can be implemented using arrays or linked lists
  • Fast push and pop operations
  • Useful for temporary data storage

Components of Stack

  • TOP → Points to the topmost element
  • Stack Array/Nodes → Stores data elements
  • Size → Maximum capacity of stack

Stack Representation

TOP
 |
30
20
10

The TOP pointer always indicates the most recently inserted element in the stack.

Need for Stack

Stacks are useful when data needs to be processed in reverse order or when temporary storage is required.

  • Function call management
  • Undo operations
  • Expression evaluation
  • Memory management

Types of Stack

Stacks can be implemented using different techniques.

  • Array Implementation
  • Linked List Implementation

Basic Operations on Stack

Different operations are performed to store, access, and manipulate elements in a stack.

Push Operation

Push inserts a new element into the stack.

top++;
stack[top]=value;

Time Complexity: O(1)

Pop Operation

Pop removes the topmost element from the stack.

top--;

Time Complexity: O(1)

Peek Operation

Peek displays the top element without removing it.

printf("%d",stack[top]);

Time Complexity: O(1)

isEmpty()

Checks whether the stack contains any elements.

if(top==-1)
 printf("Stack Empty");

Time Complexity: O(1)

isFull()

Checks whether the stack has reached maximum capacity.

if(top==MAX-1)
 printf("Stack Full");

Time Complexity: O(1)

Overflow and Underflow

Overflow occurs when inserting into a full stack.

Underflow occurs when removing from an empty stack.

if(top==MAX-1)
 printf("Stack Overflow");

if(top==-1)
 printf("Stack Underflow");

Stack Implementation in C

Array Implementation

In array implementation, elements are stored in a fixed-size array and the TOP variable keeps track of the topmost element.

#include<stdio.h>

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

void push(int value){

 if(top==4)
   printf("Overflow");

 else{
   top++;
   stack[top]=value;
 }
}

void pop(){

 if(top==-1)
   printf("Underflow");

 else
   top--;
}

Linked List Implementation

In linked list implementation, each node stores data and a pointer to the next node. It avoids fixed-size limitations present in array implementation.

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

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

struct Node* top=NULL;

void push(int value){

    struct Node* newNode=
    (struct Node*)malloc(sizeof(struct Node));

    newNode->data=value;
    newNode->next=top;
    top=newNode;
}

void pop(){

    if(top==NULL)
        printf("Underflow");

    else{
        struct Node* temp=top;
        top=top->next;
        free(temp);
    }
}

Complexity Analysis (Array and Linked List Implementation)

Operation      Complexity

Push            O(1)
Pop             O(1)
Peek            O(1)
isEmpty         O(1)
isFull          O(1)
Search          O(n)

The time complexity remains the same for both array and linked list implementations of stacks. The major difference lies in memory allocation and storage.

Comparison: Array vs Linked List Implementation

  • Arrays use fixed memory size
  • Linked Lists use dynamic memory allocation
  • Arrays are easier to implement
  • Linked Lists avoid fixed-size limitations
  • Linked Lists require extra memory for pointers

Applications of Stack

  • Undo and Redo operations
  • Function call management
  • Expression evaluation
  • Browser back and forward history
  • Backtracking algorithms

Real Life Examples of Stack

  • Stack of plates in a cafeteria
  • Browser back button history
  • Undo and Redo operations in text editors
  • Function call management
  • Checking balanced parentheses

Checking Balanced Parentheses using Stack

Stacks are commonly used to check whether brackets in an expression are balanced.

Expression: { [ ( ) ] }

Step 1: Push {
Stack: {

Step 2: Push [
Stack: { [

Step 3: Push (
Stack: { [ (

Step 4: Match ) with (
Stack: { [

Step 5: Match ] with [
Stack: {

Step 6: Match } with {
Stack: Empty

Result: Balanced

Advantages of Stack

  • Easy implementation
  • Fast push and pop operations
  • Efficient memory usage

Limitations of Stack

  • No random access
  • Only the top element can be accessed directly
  • Overflow and underflow possible

Interview Questions

1. What is LIFO?

LIFO stands for Last In First Out. The element inserted last into the stack is removed first.

Push: 10 → 20 → 30

Pop removes: 30

2. What is the difference between Stack and Queue?

A Stack follows the LIFO principle whereas a Queue follows the FIFO principle.

Stack : Last In First Out
Queue : First In First Out

3. What causes Stack Overflow?

Stack Overflow occurs when an insertion operation is performed on a full stack.

4. How are stacks used in function calls?

Function calls are managed using a call stack. Whenever a function is called, its information is pushed onto the stack and removed when execution finishes.

5. How can stacks be implemented?

Stacks can be implemented using:

  • Arrays
  • Linked Lists

6. Why is stack preferred in recursion?

Recursion uses the call stack to store function calls. Each recursive call is pushed into the stack and removed after execution completes.

Linked ListsQueues