Stack: Definition, Applications, and Operations

1. What is a Stack?

A stack is a linear data structure in which an element may be inserted or deleted only at one end (called the top of the stack). Elements are removed from a stack in the reverse order of that in which they were inserted.

Stack follows the principle of LIFO (Last In First Out), meaning the last element inserted is the first one to be removed.

Stack uses a variable called top which always points to the topmost element in the stack.

Example: Consider a stack of plates. You can only add or remove a plate from the top.

     |  30  |  <-- top
     |  20  |
     |  10  |
     |______|

2. Applications of Stack

3. Stack Operations

There are two primary operations on a stack:

a) PUSH Operation

The PUSH operation is used to add or insert an element into the stack.

• The element is always added at the top of the stack.
• Top is incremented when PUSH operation occurs.
• Before pushing, we check for Overflow condition (stack is full).

Overflow Condition: If top == MAX - 1, the stack is full and no more elements can be pushed.

Algorithm for PUSH:

Algorithm PUSH(stack, top, MAX, item):
  Step 1: If top == MAX - 1 then
              Print "Stack Overflow"
              Return
  Step 2: top = top + 1
  Step 3: stack[top] = item
  Step 4: Return

Example of PUSH:

Push elements 10, 20, 30 one by one:

Initial Stack:        After PUSH(10):     After PUSH(20):     After PUSH(30):
  top = -1              top = 0             top = 1             top = 2
  |      |              |  10  |            |  20  |            |  30  | <-- top
  |      |              |      |            |  10  |            |  20  |
  |      |              |      |            |      |            |  10  |
  |______|              |______|            |______|            |______|

b) POP Operation

The POP operation is used to delete or remove an element from the stack.

• The element is always removed from the top of the stack.
• Top is decremented when POP operation occurs.
• Before popping, we check for Underflow condition (stack is empty).

Underflow Condition: If top == -1, the stack is empty and no element can be popped.

Algorithm for POP:

Algorithm POP(stack, top):
  Step 1: If top == -1 then
              Print "Stack Underflow"
              Return
  Step 2: item = stack[top]
  Step 3: top = top - 1
  Step 4: Return item

Example of POP:

Pop elements from the stack containing 30, 20, 10:

Initial Stack:        After POP():        After POP():        After POP():
  top = 2               top = 1             top = 0             top = -1
  |  30  | <-- top      |  20  | <-- top    |  10  | <-- top    |      |
  |  20  |              |  10  |            |      |            |      |
  |  10  |              |      |            |      |            |      |
  |______|              |______|            |______|            |______|
  Popped: 30            Popped: 20          Popped: 10          Stack Empty

c) PEEK / Top Operation

Returns the topmost element without removing it.

Algorithm PEEK(stack, top):
  Step 1: If top == -1 then
              Print "Stack is Empty"
              Return
  Step 2: Return stack[top]

4. Complete Example: Infix to Postfix Conversion Using Stack

Convert infix expression (A + B / C * D + E) - F to postfix using stack.

The precedence rules used:

• ^ or $ -- Highest (Level 1)
• *, / -- Medium (Level 2)
• +, - -- Lowest (Level 3)

When the second + is scanned, the * already on the stack and the + below it both have precedence at least as high as the incoming +, so both are popped to the output before the new + is pushed. Emptying the stack at the end gives

Postfix: A B C / D * + E + F -

The stack made this conversion possible because operators must be held back until an operator of lower or equal precedence, or a closing parenthesis, appears, and a stack returns them in exactly the reverse order in which they were held.

5. Conclusion

A stack is a linear structure restricted to a single access point, the top, which gives it LIFO behaviour and makes PUSH, POP and PEEK all constant time operations once the overflow and underflow conditions have been checked. That single restriction is precisely what makes it useful: function calls and recursion unwind in reverse order of their invocation, undo history is replayed backwards, backtracking abandons the most recent choice first, and expression conversion and evaluation need operators released in reverse order of their being held. Whether it is implemented over an array with an integer top or over a linked list with a head pointer, the behaviour seen by the user of the ADT stays the same.

Short Notes: Tail Recursion and Collision Resolution Techniques

a. Tail Recursion (2.5 marks)

Definition: Tail recursion is a special form of recursion in which the recursive call is the last operation performed in the function. There is no pending computation left to be done after the recursive call returns.

Key Characteristics:

• The recursive call appears at the tail (end) of the function body.
• Since no task is left after the recursive call, the current stack frame does not need to be preserved.
• As stated in the notes: "Tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to organize and optimize the code."

Example:

// Non-tail recursive factorial
int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n-1);   // pending multiplication after call
}

// Tail recursive factorial
int fact_tail(int n, int acc) {
    if (n == 0) return acc;
    return fact_tail(n-1, n * acc);  // last operation is the call itself
}

Advantages over Normal Recursion:

• Compiler can optimize tail recursion into iteration (tail call optimization), saving stack space.
• Avoids stack overflow for large inputs.
• More memory efficient since intermediate results need not be stored on the system stack.

b. Collision Resolution Techniques (2.5 marks)

Collision: A collision occurs when two distinct keys produce the same hash value and map to the same slot in a hash table.

Collision Resolution: When two items hash to the same slot, a systematic method is needed to place the second item. This process is called collision resolution.

The major techniques are:

1. Open Addressing

When a collision occurs, another location in the array is sought. It has three main methods:

i) Linear Probing:

• The colliding item is placed in the next empty slot in the array.
• Formula: h(x) = (hash value + i) % table size for i = 1, 2, 3, ...
• Disadvantage: Causes primary clustering (long chains of occupied slots).

Example: Insert {89, 49, 18, 58} with h(x) = x % 10

ii) Quadratic Probing:

• Eliminates primary clustering by using a quadratic function.
• Formula: h(x) = (hash value + j²) % table size for j = 1, 2, 3, ...
• On 1st collision: (hash value + 1²) % table size
• On 2nd collision: (hash value + 2²) % table size

iii) Double Hashing:

• Uses a second hash function to determine the step size when a collision occurs.
• Reduces clustering more effectively than linear or quadratic probing.

2. Chaining

• Each slot in the hash table holds a linked list of all elements that hash to that slot.
• Colliding elements are simply appended to the list at that index.
• Easy to implement and handles multiple collisions gracefully.

3. Rehashing

• When a collision occurs, a new hash function is applied to find an alternate location.

4. Hashing Using Buckets

• Each hash table slot points to a bucket (array or block) that can hold multiple values.

Summary Table: