Skip to content

Linear Data Structures

Short Notes

Data structures where elements are arranged in a linear sequence.

Stack (LIFO)

  • Operations: push, pop, peek.
  • Applications: Expression evaluation, Recursion management, Undo mechanisms.

Queue (FIFO)

  • Operations: enqueue, dequeue.
  • Applications: CPU scheduling, Buffer management.
  • Circular Queue: Avoids space wastage in linear arrays.

Linked Lists

  • Singly: Nodes have data and next pointer.
  • Doubly: Nodes have data, next, and prev pointers.
  • Circular: Last node points back to the first.

Key Theories & Formulas

1. Postfix/Prefix Conversions

  • Infix: \(A + B\)
  • Postfix: \(AB+\)
  • Prefix: \(+AB\)
  • GATE Rule: Use a stack for evaluation. Scan left to right for postfix; right to left for prefix.

2. Complexity Table

Operation Array Linked List Stack/Queue
Access \(O(1)\) \(O(n)\) -
Insert/Delete (Start) \(O(n)\) \(O(1)\) \(O(1)\)
Insert/Delete (End) \(O(1)\) \(O(n)*\) \(O(1)\)
(\(O(1)\) if tail pointer exists)

Example Problems

Problem: Evaluate the postfix expression: 10 2 8 * + 3 -.

  1. push 10, push 2, push 8.
  2. *: pop 8, 2. \(2 \times 8 = 16\). push 16.
  3. +: pop 16, 10$. $10 + 16 = 26$.push 26`.
  4. 3: push 3.
  5. -: pop 3, 26. \(26 - 3 = 23\). Result: 23.

Hardest GATE Questions

Topic: Minimum Stacks/Queues for Implementation Tricky Question (GATE 2013/2016): What is the minimum number of stacks required to implement a Queue?

  • Analysis: 2 stacks. One for input, one for output.
  • The "Trap": Sometimes the question asks for the minimum number of FIFO queues to implement a Priority Queue or Stack. (Stack using 2 Queues).
  • Complexity: Calculating the number of permutations that can be generated by a stack. (Catalan Number: \(\frac{1}{n+1} \binom{2n}{n}\)).
  • For \(n=3\), Catalan(3) = 5. Permutations like \((3, 1, 2)\) are impossible in a stack if inputs are \((1, 2, 3)\)

References