Stacks and Queues

Stacks and Queues

Stacks and queues are linear data structures that follow specific insertion and deletion rules.

Stack

Stack is a LIFO (Last In First Out) data structure.

Stack Operations

Basic Operations:

• push(x): Insert element x at top - O(1)
• pop(): Remove and return top element - O(1)
• peek()/top(): Return top element without removing - O(1)
• isEmpty(): Check if stack is empty - O(1)
• size(): Return number of elements - O(1)

Stack Implementation

Using Array

#define MAX 100
int stack[MAX];
int top = -1;

void push(int x) {
    if (top == MAX - 1) {
        printf("Stack Overflow");
        return;
    }
    stack[++top] = x;
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow");
        return -1;
    }
    return stack[top--];
}

int peek() {
    if (top == -1) return -1;
    return stack[top];
}

Using Linked List

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

struct Node* top = NULL;

void push(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (top == NULL) {
        printf("Stack Underflow");
        return -1;
    }
    struct Node* temp = top;
    int data = top->data;
    top = top->next;
    free(temp);
    return data;
}

Stack Applications

1. Expression Evaluation

• Infix to postfix conversion
• Postfix evaluation
• Parenthesis matching

1. Function Calls

• Recursion uses call stack
• Stack frame management

1. Undo/Redo Operations

• Text editors
• Browsers

1. Backtracking

• DFS implementation
• Maze solving

Expression Evaluation

Infix Notation: A + B (operator between operands)

Postfix Notation: AB+ (operator after operands)

Prefix Notation: +AB (operator before operands)

Infix to Postfix Algorithm:

1. Scan expression left to right
2. If operand, output it
3. If '(', push to stack
4. If ')', pop until '('
5. If operator:

• Pop operators with higher/equal precedence
• Push current operator

1. Pop remaining operators

Postfix Evaluation:

1. Scan expression left to right
2. If operand, push to stack
3. If operator:

• Pop two operands
• Apply operator
• Push result

1. Final result is stack top

Queue

Queue is a FIFO (First In First Out) data structure.

Queue Operations

Basic Operations:

• enqueue(x): Insert element x at rear - O(1)
• dequeue(): Remove and return front element - O(1)
• front(): Return front element without removing - O(1)
• isEmpty(): Check if queue is empty - O(1)
• size(): Return number of elements - O(1)

Queue Implementation

Using Array (Circular Queue)

#define MAX 100
int queue[MAX];
int front = -1, rear = -1;

void enqueue(int x) {
    if ((rear + 1) % MAX == front) {
        printf("Queue Full");
        return;
    }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    queue[rear] = x;
}

int dequeue() {
    if (front == -1) {
        printf("Queue Empty");
        return -1;
    }
    int data = queue[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % MAX;
    }
    return data;
}

Using Linked List

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

struct Node* front = NULL;
struct Node* rear = NULL;

void enqueue(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = NULL;
    
    if (rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

int dequeue() {
    if (front == NULL) {
        printf("Queue Empty");
        return -1;
    }
    struct Node* temp = front;
    int data = front->data;
    front = front->next;
    if (front == NULL) rear = NULL;
    free(temp);
    return data;
}

Queue Variations

1. Circular Queue

• Rear wraps around to front
• Efficient space utilization
• Prevents overflow

2. Priority Queue

• Elements dequeued by priority
• Can be implemented using heap
• Used in scheduling algorithms

3. Deque (Double-ended Queue)

• Insert/delete from both ends
• Can be used as stack or queue

Queue Applications

1. BFS (Breadth-First Search)

• Graph traversal
• Level-order tree traversal

1. Scheduling

• Process scheduling
• Task scheduling

1. Buffering

• I/O buffering
• Network packet queuing

1. Print Spooling

• Print job management

Stack vs Queue

GATE CS Important Points

1. Operations: Know all operation complexities
2. Implementation: Understand both array and linked list implementations
3. Applications: Expression evaluation, BFS, recursion
4. Parenthesis Matching: Stack-based solution
5. Circular Queue: Understand wrap-around logic

Practice Tips

1. Implement Both: Code stack and queue from scratch
2. Expression Evaluation: Practice infix to postfix conversion
3. Parenthesis Matching: Solve using stack
4. BFS Implementation: Use queue for graph traversal
5. Previous Year Questions: Solve GATE stack/queue questions