Unit 3: Stacks and Queues

1. Introduction to Stacks

A Stack is a linear data structure that follows a specific order for operations. The order is LIFO (Last In First Out) or FILO (First In Last Out). This means that the element inserted last will be the first one to be removed.

Key Characteristics

• Top: A pointer or index indicating the uppermost element of the stack.
• Insertion/Deletion: Both occur at the same end (the "Top").
• Analogy: A stack of plates in a cafeteria or a deck of cards.

2. Stack Representations

A. Array Representation (Static Implementation)

In this representation, a stack is implemented using a fixed-size array.

• Memory: Allocated at compile time.
• Variables needed:
  • MAX_SIZE: The maximum capacity of the stack.
  • arr[]: The array storing elements.
  • top: An integer variable initialized to -1 (indicating an empty stack).

Conditions:

• Stack Empty (Underflow): top == -1
• Stack Full (Overflow): top == MAX_SIZE - 1

B. Linked List Representation (Dynamic Implementation)

In this representation, the stack is implemented using a singly linked list. The size can grow and shrink dynamically.

• Structure: Each node contains data and a next pointer.
• Top: The head pointer of the linked list acts as the top.
• Logic: Insertions and deletions are performed at the beginning (head) of the list to ensure time complexity.

3. Operations on Stack

A. Push Operation

Adding an element to the top of the stack.

Algorithm (Array):

Procedure Push(item)
    IF top == MAX_SIZE - 1 THEN
        PRINT "Stack Overflow"
        RETURN
    END IF
    top = top + 1
    stack[top] = item
End Procedure

B. Pop Operation

Removing the top element from the stack.

Algorithm (Array):

Procedure Pop()
    IF top == -1 THEN
        PRINT "Stack Underflow"
        RETURN
    END IF
    item = stack[top]
    top = top - 1
    RETURN item
End Procedure

C. Traversal (Peeping/Display)

Viewing elements in the stack without removing them, typically from Top to Bottom.

Algorithm:

Procedure Traverse()
    IF top == -1 THEN
        PRINT "Stack is Empty"
        RETURN
    END IF
    FOR i = top TO 0 STEP -1 DO
        PRINT stack[i]
    END FOR
End Procedure

4. Arithmetic Expressions: Polish Notation

Computers prefer specific notations to evaluate arithmetic expressions without ambiguity regarding operator precedence and associativity.

A. Types of Notations

1. Infix: Operator is between operands (e.g., ). Standard human-readable form.
2. Prefix (Polish Notation): Operator precedes operands (e.g., ).
3. Postfix (Reverse Polish Notation): Operator follows operands (e.g., ).

B. Transformation of Expressions (Infix to Postfix)

To convert Infix to Postfix, we use a stack to hold operators and manage precedence.

Rules:

1. Scan expression from left to right.
2. If operand: Output it.
3. If '(': Push to stack.
4. If ')': Pop operators from stack to output until '(' is found. Discard parenthesis.
5. If Operator:
   • If stack is empty or top is '(', push operator.
   • If incoming operator > top operator precedence, push operator.
   • If incoming operator top operator precedence, pop top operator to output, then repeat comparison.

Example: Convert

• Read : Output: , Stack: Empty
• Read : Output: , Stack:
• Read : Output: , Stack:
• Read : Output: , Stack: (Multiply is higher precedence than Add)
• Read : Output: , Stack:
• End: Pop remaining. Final:

C. Evaluation of Postfix Expressions

A stack is used to solve the equation.

Algorithm:

1. Scan the postfix expression from left to right.
2. If an operand is encountered, Push it onto the stack.
3. If an operator is encountered:
   • Pop the top two elements. (First pop is Operand 2, second pop is Operand 1).
   • Perform the operation: .
   • Push the result back onto the stack.
4. The final value in the stack is the result.

Example: Evaluate

• Push 5.
• Push 3.
• Operator : Pop 3, Pop 5. Calc . Push 8.
• Push 2.
• Operator : Pop 2, Pop 8. Calc . Push 16.
• Result: 16.

5. Introduction to Queues

A Queue is a linear data structure that follows the FIFO (First In First Out) principle. The element inserted first is the first to be removed.

Key Characteristics

• Front: The end where deletions take place.
• Rear: The end where insertions take place.
• Analogy: A line of people waiting at a ticket counter.

6. Queue Representations

A. Array Representation (Linear Queue)

• Uses a fixed-size array.
• Front initialized to -1 (or 0).
• Rear initialized to -1.
• Drawback: "False Overflow". If elements are deleted from the front, the space cannot be reused in a linear array implementation unless pointers are reset, leading to the concept of Circular Queues.

B. Linked List Representation

• Uses a singly linked list.
• Front pointer: Points to the head node.
• Rear pointer: Points to the last node.
• Allows dynamic sizing and eliminates the false overflow issue.

7. Queue Operations

A. Enqueue (Insertion)

Adding an element to the Rear of the queue.

Algorithm (Array):

Procedure Enqueue(item)
    IF Rear == MAX_SIZE - 1 THEN
        PRINT "Queue Overflow"
        RETURN
    END IF
    IF Front == -1 THEN
        Front = 0;
    END IF
    Rear = Rear + 1
    Queue[Rear] = item
End Procedure

B. Dequeue (Deletion)

Removing an element from the Front of the queue.

Algorithm (Array):

Procedure Dequeue()
    IF Front == -1 OR Front > Rear THEN
        PRINT "Queue Underflow"
        RETURN
    END IF
    item = Queue[Front]
    Front = Front + 1
    RETURN item
End Procedure

C. Traversal

Displaying elements from Front to Rear.

Algorithm:

Procedure Traverse()
    IF Front == -1 THEN
        PRINT "Queue Empty"
        RETURN
    END IF
    FOR i = Front TO Rear DO
        PRINT Queue[i]
    END FOR
End Procedure

8. Advanced Queue Concepts

A. Priority Queues

A Priority Queue is a type of queue where every element has a "priority" associated with it.

Rules for Processing:

1. An element with higher priority is processed before an element with lower priority.
2. If two elements have the same priority, they are processed according to their order in the queue (FIFO).

Types:

• Ascending Priority Queue: Smallest number has highest priority.
• Descending Priority Queue: Largest number has highest priority.

Implementation: Can be implemented using Arrays, Linked Lists, or Heaps (Binary Heap is most efficient).

B. Deques (Double-Ended Queues)

A Deque (pronounced "deck") is a generalized version of a queue that allows insertion and deletion at both ends (Front and Rear).

Types of Deques:

1. Input-Restricted Deque:
   • Insertion is allowed at only one end (usually Rear).
   • Deletion is allowed at both ends.
2. Output-Restricted Deque:
   • Deletion is allowed at only one end (usually Front).
   • Insertion is allowed at both ends.

Applications of Deque:

• Undo operations in software (storing history).
• Palindrome checking.
• Job scheduling algorithms.