Data Structure (CS-303) Unit 2 Notes - RGPV

How unit 2 is examined

Stacks and queues: array and linked implementations, infix-to-postfix conversion (heaviest), recursion with Tower of Hanoi, circular queue, deque and priority queue.

Stacks as ADT

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A stack is an ordered linear list in which insertion and deletion take place only at one end, called the top, so the element inserted last is removed first (LIFO: Last In First Out).</mark>

Key points.

As an ADT a stack is defined by its operations, not its storage: push(x), pop(), peek(), isEmpty() and isFull().
It is called LIFO because the last element pushed sits on top and is the first to be popped, like a pile of plates where only the top plate can be taken.
push on a full stack gives overflow, and pop on an empty stack gives underflow; both must be checked.
The variable top holds the index of the last element and is -1 for an empty stack.
change(i, x) replaces the i-th element from the top by x; it needs a check that top - i + 1 >= 0.
Every operation touches only the top, so each costs O(1).

Steps.

PUSH(S, MAX, x):  Step 1: if top == MAX-1 then print "Overflow", stop.
                  Step 2: top = top + 1.   Step 3: S[top] = x.
POP(S):           Step 1: if top == -1 then print "Underflow", stop.
                  Step 2: x = S[top].      Step 3: top = top - 1.   Step 4: return x.
CHANGE(S, i, x):  Step 1: if top - i + 1 < 0 then print "Underflow", stop.
                  Step 2: S[top - i + 1] = x.

Comparison.

Basis	Stack	Queue
Order	LIFO	FIFO
Ends used	One end (top)	Two ends (front, rear)
Insert / delete	push / pop at top	enqueue at rear / dequeue at front
Pointers	`top`	`front` and `rear`
Uses	Recursion, expression conversion, undo	Scheduling, buffering, BFS
Empty test	`top == -1`	`front == -1` or `front > rear`

Answer frame. Define and explain LIFO; write the three algorithms with checks; for "differentiate" draw the table; close with O(1).

Asked: [7 marks] (Jun 2023, Jun 2024) Differentiate between the stack and queue. Asked: [7 marks] (Dec 2020) What is Stack? Why it is known as LIFO? Write algorithm of PUSH, POP and CHANGE operation on Stack.

Different implementation of stack

Definition. <mark>A stack is implemented either as an array with an index top (static, fixed size) or as a singly linked list whose head node is the top (dynamic, grows on demand).</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 288 58" width="288" height="58" role="img" aria-label="Linked stack, top points to the last pushed node (30)"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">top</text><line class="e" x1="44" y1="29" x2="67" y2="29" marker-end="url(#ah6)"/><rect class="n" x="68" y="14" width="46" height="30" rx="3"/><text class="t" x="83" y="29" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="98" y1="14" x2="98" y2="44"/><circle class="dot" cx="106" cy="29" r="2.6"/><line class="e" x1="106" y1="29" x2="147" y2="29" marker-end="url(#ah6)"/><rect class="n" x="148" y="14" width="46" height="30" rx="3"/><text class="t" x="163" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="178" y1="14" x2="178" y2="44"/><circle class="dot" cx="186" cy="29" r="2.6"/><line class="e" x1="186" y1="29" x2="227" y2="29" marker-end="url(#ah6)"/><rect class="n" x="228" y="14" width="46" height="30" rx="3"/><text class="t" x="243" y="29" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="258" y1="14" x2="258" y2="44"/><line class="kd" x1="261" y1="41" x2="271" y2="17"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Linked stack, top points to the last pushed node (30)</figcaption></figure>

Key points.

Array stack: int S[MAX]; int top = -1; push increments top and stores, pop reads and decrements.
Array overflow occurs when top == MAX-1 and underflow when top == -1, so the size is fixed in advance.
Linked stack: each node has data and next; a pointer top points to the head node.
Linked push allocates a node, sets new->next = top, then top = new; pop saves top, moves top = top->next and frees the old node.
Linked underflow is top == NULL; overflow happens only if malloc fails.
Both push and pop are O(1) in both implementations.
Array: simple and fast, no pointer memory, but wastes space or overflows. Linked: no size limit and no waste, but extra space for next and malloc cost.

PUSH_LL(x):  Step 1: new = malloc(node); if new == NULL then Overflow.
             Step 2: new->data = x.   Step 3: new->next = top.   Step 4: top = new.
POP_LL():    Step 1: if top == NULL then Underflow, stop.
             Step 2: t = top; x = t->data.   Step 3: top = top->next.
             Step 4: free(t); return x.

Program (array stack).

#define MAX 5
int S[MAX], top = -1;
void push(int x){ if(top==MAX-1) printf("Overflow\n"); else S[++top]=x; }
int pop(){ if(top==-1){ printf("Underflow\n"); return -1; } return S[top--]; }
void display(){ for(int i=top;i>=0;i--) printf("%d ",S[i]); }  /* 30 20 10 */

Reverse a stack using one extra stack T and variables x, i, count.

Step 1: n = number of elements in S.
Step 2: for i = 1 to n: x = pop(S); count = n - i.
Step 3: move count elements from S to T; push(S, x); move all of T back to S.

Trace, S = [1, 2, 3] (3 on top): pass 1 gives [3, 1, 2]; pass 2 gives [3, 2, 1]; pass 3 leaves [3, 2, 1] with 1 on top. Time $O(n^2)$, space $O(n)$.

Answer frame. Operations with program: define stack and LIFO, list push, pop, peek, overflow and underflow, give the program. Linked algorithm: draw the linked stack, node structure, push, pop, O(1). ADT with array and linked: add a 4-row comparison of points 2, 5, 7. Close with "all operations are O(1)".

Pitfall: In linked pop, freeing the node before saving top->next (or the data) loses the rest of the stack. Asked: [7 marks] (Jun 2020, Dec 2024) Write an algorithm which reverses the order of elements of stack using one additional stack and some additional variables. Asked: [7 marks] (Nov 2022, Dec 2025) Explain the operations performed on stack with a program. Asked: [14 marks] (Jun 2023) Write short notes on any two: i) Stack using linked list ii) Indexing iii) B tree iv) Priority queue. Asked: [7 marks] (Dec 2024) Write an algorithm for Push and Pop operations on Stack using linked list. Asked: [7 marks] (Dec 2025) Define Stack as an ADT. Explain the array and linked list implementation of stacks.

Multiple stacks

Definition. Multiple stacks means keeping two or more stacks in one array so that unused space of one stack can be used by another.

Key points.

Two stacks in an array of size n grow towards each other: stack 1 starts at index 0 (top1 = -1) and stack 2 starts at index n-1 (top2 = n).
Overflow occurs only when top1 + 1 == top2, i.e. the whole array is really full.
For m stacks the array is divided into m segments, each with its own top[i]; a full segment needs its neighbours shifted.

Application of Stack: infix to postfix conversion

Definition. <mark>Infix has the operator between operands (A+B), postfix has it after them (AB+); a stack holds operators until their operands are complete, and postfix needs no brackets or precedence rules to evaluate.</mark>

Rules. Precedence: ^ or $ (highest, right-to-left) > * / > + - (lowest), the last two left-to-right.

Steps.

Step 1: Scan the infix expression left to right.
Step 2: Operand: send it to the output.
Step 3: '(' : push it on the stack.
Step 4: ')' : pop operators to the output until '(' is met; discard both brackets.
Step 5: Operator: while the stack top is not '(' and has higher precedence than the scanned
        operator (or equal precedence and the scanned operator is left-associative), pop it to output.
        Then push the scanned operator.  (For ^ and $, equal precedence is NOT popped.)
Step 6: At the end pop all remaining operators to the output.

Example. Convert $A+(B+D)/E-F*(G+H/K)$ (Dec 2023):

Token	Stack after	Output so far
A	empty	A
+ ( B + D	+ ( +	ABD
)	+	ABD+
/ E	+ /	ABD+E
-	- (pops / then +)	ABD+E/+
F * ( G + H / K	- * ( + /	ABD+E/+FGHK
)	- * (pops / then +)	ABD+E/+FGHK/+
end	empty	ABD+E/+FGHK/+*-

(Rows group tokens that only push or output.)

Postfix = $ABD+E/+FGHK/+*-$

Other papers. $a-b/c*d+e*f/g$ gives $abc/d*-ef*g/+$ (Dec 2020). $A+B-CDE$F$G$ gives $AB+CD*EFG\$$*-$ (Nov 2022): the first $ stays on the stack because $ is right-associative.

Infix to prefix (Nov 2018). Reverse the expression and swap brackets, apply the same algorithm (pop only on strictly higher precedence, and on equal precedence only for right-associative operators), then reverse the result. Reading | as the division operator /:

(i) $A^B*C-D+E/F/(G+H)$ gives $+-*^ABCD//EF+GH$.
(ii) $(A+B)*(C^(D-E)+F)-G$ gives $-*+AB+^C-DEFG$.

Program.

#include <stdio.h>
#include <ctype.h>
char st[50]; int top = -1;
int prec(char c){ return c<mark>'^'?3 : (c</mark>'*'||c<mark>'/')?2 : (c</mark>'+'||c=='-')?1 : 0; }
int main(){
  char in[50], c; int i, k = 0; char out[50];
  scanf("%s", in);
  for(i=0; (c=in[i]); i++){
    if(isalnum(c)) out[k++]=c;
    else if(c=='(') st[++top]=c;
    else if(c==')'){ while(st[top]!='(') out[k++]=st[top--]; top--; }
    else { while(top>=0 && prec(st[top])>=prec(c) && c!='^') out[k++]=st[top--];
           st[++top]=c; }
  }
  while(top>=0) out[k++]=st[top--];
  out[k]='\0'; printf("%s\n", out);   /* a+b*c -> abc*+ */
}

prec('(') is 0, so a bracket is never popped by an operator.

Answer frame. Define infix and postfix with the precedence table; write the 6 steps; show the token/stack/output table with the final postfix; close with "the stack holds operators only". For the C program give the algorithm, then prec and the loop handling ( and ).

Pitfall: Popping an equal-precedence ^ or $; it is right-associative, so A^B^C becomes ABC^^. Asked: [7 marks] (Jun 2020, Jun 2024, Dec 2025) How can you convert an infix expression to postfix expression using stack? Give one example. Asked: [7 marks] (Dec 2025) Explain the algorithm to convert an Infix expression to a Postfix notation using a stack. Asked: [7 marks] (Jun 2023, Jun 2024) Write a 'C' program to convert the infix expression to postfix expression. Asked: [7 marks] (Nov 2018) Convert the infix expressions to prefix, showing all steps: i) $A^B*C-D+E|F|(G+H)$ ii) $(A+B)*(C^(D-E)+F)-G$. Asked: [7 marks] (Dec 2020) Write an algorithm for converting parenthesized infix to postfix and convert $a-b/c*d+e*f/g$. Asked: [7 marks] (Nov 2022) Convert to postfix: $A+B-CDE$F$G$. Asked: [10 marks] (Dec 2023) i) Transform $A+(B+D)/E-F*(G+H/K)$ to postfix. ii) Evaluate $ABC*D/+$ with A=2, B=3, C=4, D=6.

Evaluation of postfix expression

Definition. Postfix evaluation scans the expression left to right using a stack of operands.

Key points.

An operand is pushed; an operator pops two values, the first popped being the right operand (op2) and the second the left (op1), and pushes op1 op op2.
The single value left at the end is the result.
Example (Dec 2023): $ABC*D/+$ with A=2, B=3, C=4, D=6 is $2\,3\,4*6/+$: push 2, 3, 4; * gives 12; push 6; / gives 2; + gives 4. Result = 4.

Recursion

Definition. <mark>Recursion is a technique in which a function calls itself, on a smaller version of the same problem, until a base case is reached that stops the calls.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 492.8 80" width="492.8" height="80" role="img" aria-label="Call stack for fact(3): F3 = fact(3) etc.; calls go down to the base case, then return values 1, 1, 2, 6 unwind back"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L156.6,40" marker-end="url(#ah7)"/><path class="e" d="M196.6,40 L294.2,40" marker-end="url(#ah7)"/><path class="e" d="M334.2,40 L431.8,40" marker-end="url(#ah7)"/><g class="wl"><rect x="85.3" y="31" width="47.1" height="18" rx="9"/><text class="t" x="108.8" y="40" dy=".35em" text-anchor="middle">calls</text></g><g class="wl"><rect x="222.8" y="31" width="47.1" height="18" rx="9"/><text class="t" x="246.4" y="40" dy=".35em" text-anchor="middle">calls</text></g><g class="wl"><rect x="360.5" y="31" width="47.1" height="18" rx="9"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">calls</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">F3</text><circle class="n" cx="177.6" cy="40" r="18"/><text class="t" x="177.6" y="40" dy=".35em" text-anchor="middle">F2</text><circle class="n" cx="315.2" cy="40" r="18"/><text class="t" x="315.2" y="40" dy=".35em" text-anchor="middle">F1</text><circle class="n" cx="452.8" cy="40" r="18"/><text class="t" x="452.8" y="40" dy=".35em" text-anchor="middle">F0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Call stack for fact(3): F3 = fact(3) etc.; calls go down to the base case, then return values 1, 1, 2, 6 unwind back</figcaption></figure>

Key points.

Every recursive function needs a base case (stops recursion) and a recursive case (calls itself with a smaller argument); without a base case it never ends and the stack overflows.
Each call pushes an activation record (parameters, local variables, return address) on the system stack, and each return pops it, so recursion is stack-based.
Factorial: $n! = n \times (n-1)!$ with $0! = 1$.
Fibonacci: $F(n) = F(n-1) + F(n-2)$ with $F(0)=0$, $F(1)=1$.
Advantages: short, clear code for problems like trees and Hanoi; disadvantages: extra stack memory and slower than loops.
Stack applications: expression conversion, recursion, backtracking, undo, bracket matching.

int fact(int n){ if(n==0) return 1;  return n * fact(n-1); }   /* fact(3) = 6 */

Trace: fact(3) = 3 x fact(2) = 3 x (2 x fact(1)) = 3 x (2 x (1 x fact(0))) = 3 x 2 x 1 x 1 = 6.

Tower of Hanoi. Three pegs: source A, auxiliary B, destination C, n disks of different size on A. Rules: move one disk at a time, only the top disk of a peg, and never place a larger disk on a smaller one. Goal: move all disks A to C.

HANOI(n, A, C, B): Step 1: if n == 1 then move disk from A to C, return.
                   Step 2: HANOI(n-1, A, B, C).     (n-1 disks A to B using C)
                   Step 3: move disk n from A to C.
                   Step 4: HANOI(n-1, B, C, A).     (n-1 disks B to C using A)

Recurrence $T(n) = 2T(n-1)+1$ gives $T(n) = 2^n - 1$ moves, time $O(2^n)$. For n = 3 there are 7 moves:

Move	1	2	3	4	5	6	7
Disk	1	2	1	3	1	2	1
From to	A to C	A to B	C to B	A to C	B to A	B to C	A to C

Final state: all three disks on C, largest at the bottom.

Answer frame. Recursion: define with base and recursive case, draw the call chain, trace factorial, close with advantages and disadvantages. Hanoi: state rules, draw three pegs before and after, algorithm, 7-move table, $2^n-1$. Applications plus factorial: list applications first, then the factorial trace.

Asked: [7 marks] (Nov 2018, Nov 2019, Jun 2024) Explain the concept of recursion with example. Asked: [7 marks] (May 2019, Dec 2023) Explain Tower of Hanoi with all necessary steps by considering basic rules. Asked: [7 marks] (Dec 2020) List the applications of Stack. What is Recursion? Explain Recursion for find a factorial of number in detail.

Queues as ADT

Definition. A queue is a linear list where insertion is at the rear and deletion at the front, so the first element inserted is the first removed (FIFO).

Key points.

Operations: enqueue(x) at rear, dequeue() at front, front(), isEmpty(), isFull().
Empty queue: front = rear = -1; overflow at rear == MAX-1, underflow when the queue is empty.
In a linear array queue, freed front cells are never reused, which is fixed by the circular queue.

Different implementation of queue

Definition. A queue is implemented by an array with front and rear indices or by a linked list with front and rear pointers.

Key points.

Linked queue node: struct node { int data; struct node *next; }; front points to the first node and rear to the last.
Enqueue: create a node with next = NULL; if the queue is empty set front = rear = new, else rear->next = new; rear = new.
Dequeue: if front == NULL print Underflow; else t = front; x = t->data; front = front->next; if front becomes NULL set rear = NULL; free t.
Both operations are O(1) and the linked queue has no size limit.

Circular queue

Definition. <mark>A circular queue is a queue in which the last position of the array is connected back to the first, so front and rear wrap around and freed cells are reused.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 338 424" width="338" height="424" role="img" aria-label="Circular array of size 6 (Q0 to Q5); Q5 links back to Q0. Front marks the first element, rear the last."><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M184.8,50.5 L280.5,114.4" marker-end="url(#ah8)"/><path class="e" d="M298,145 L298,277" marker-end="url(#ah8)"/><path class="e" d="M282.2,308.5 L186.5,372.4" marker-end="url(#ah8)"/><path class="e" d="M153.2,373.5 L57.5,309.6" marker-end="url(#ah8)"/><path class="e" d="M40,279 L40,147" marker-end="url(#ah8)"/><path class="e" d="M55.8,115.5 L151.5,51.6" marker-end="url(#ah8)"/><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">Q0</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">Q1</text><circle class="n" cx="298" cy="298" r="18"/><text class="t" x="298" y="298" dy=".35em" text-anchor="middle">Q2</text><circle class="n" cx="169" cy="384" r="18"/><text class="t" x="169" y="384" dy=".35em" text-anchor="middle">Q3</text><circle class="n" cx="40" cy="298" r="18"/><text class="t" x="40" y="298" dy=".35em" text-anchor="middle">Q4</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Q5</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Circular array of size 6 (Q0 to Q5); Q5 links back to Q0. Front marks the first element, rear the last.</figcaption></figure>

Formula. $rear = (rear+1) \bmod MAX$, $front = (front+1) \bmod MAX$.

Key points.

A linear queue cannot reuse cells vacated at the front, so it reports full while space exists; the circular queue removes this waste.
Empty: front == -1. Full: (rear+1) % MAX == front.
Insertion is at rear and deletion at front; only these two pointers move, using modulo arithmetic to wrap.
Inserting the first element sets front = rear = 0; deleting the last resets both to -1.

INSERT(x):  Step 1: if (rear+1) % MAX == front then print "Overflow", stop.
            Step 2: if front == -1 then front = rear = 0
                    else rear = (rear+1) % MAX.
            Step 3: Q[rear] = x.
DELETE():   Step 1: if front == -1 then print "Underflow", stop.
            Step 2: x = Q[front].
            Step 3: if front == rear then front = rear = -1
                    else front = (front+1) % MAX.
            Step 4: return x.

Example (MAX = 5): insert 10, 20, 30, 40, 50 gives front = 0, rear = 4; delete twice gives front = 2; insert 60 gives rear = (4+1)%5 = 0, so 60 goes to cell 0.

Answer frame. Open with the definition; draw the circle with front and rear; state full and empty conditions; write INSERT then DELETE; close with the MAX = 5 example. If priority queue is also asked, add its definition from the next section.

Asked: [7 marks] (Nov 2018, Dec 2024) How elements are inserted and deleted in a circular queue? Explain with diagram. Asked: [7 marks] (Dec 2020) What are Circular Queue and Priority Queue? Write an algorithm to insert and delete an element from a Circular Queue.

Concept of Dqueue and Priority Queue

Definition. <mark>A deque (double-ended queue) allows insertion and deletion at both front and rear; a priority queue removes the element of highest priority first, whatever its arrival order.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-04" viewBox="0 0 467 80" width="467" height="80" role="img" aria-label="Deque: F = front end, R = rear end; insert and delete are allowed at both ends"><style>#dsfig-u2-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-04 .t{fill:#16181D;font-weight:500}#dsfig-u2-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-04 .dot{fill:#16181D}#dsfig-u2-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-04 .ah{fill:#454C5A}#dsfig-u2-04 .ah.hi{fill:#2340B8}#dsfig-u2-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-04 .e{stroke:#B1B7C3}html.dark #dsfig-u2-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-04 .t{fill:#E6E8ED}html.dark #dsfig-u2-04 .t.inv{fill:#0F1115}html.dark #dsfig-u2-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-04 .dot{fill:#E6E8ED}html.dark #dsfig-u2-04 .ann{fill:#8FA3FF}html.dark #dsfig-u2-04 .lbl{fill:#858D9C}html.dark #dsfig-u2-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-04 .ah{fill:#B1B7C3}html.dark #dsfig-u2-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M61,40 L148,40" marker-end="url(#ah9)" marker-start="url(#ah9)"/><path class="e" d="M188,40 L279,40"/><path class="e" d="M319,40 L406,40" marker-end="url(#ah9)" marker-start="url(#ah9)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">R</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Deque: F = front end, R = rear end; insert and delete are allowed at both ends</figcaption></figure>

Key points.

Deque operations: insertFront, insertRear, deleteFront, deleteRear.
Input-restricted deque: insertion only at one end, deletion at both ends. Output-restricted deque: deletion only at one end, insertion at both ends.
A deque acts as a stack (use one end) or a queue (use both), and is used for palindrome checking and undo lists.
Priority queue: each element has a priority; deletion removes the highest priority (or lowest number), and equal priorities go in FIFO order.
Types: ascending (smallest first) and descending (largest first) priority queue.
Implementations: sorted linked list (insert in order, delete at front), unsorted array, or heap; applications are CPU scheduling and Dijkstra's algorithm.

PQ-INSERT(x, p):  Step 1: create node (x, p).
                  Step 2: if list empty or p is better than the first node, put it at the front.
                  Step 3: else move ahead until the next node has lower priority; link the node there.
PQ-DELETE():      Step 1: if list empty then Underflow, stop.
                  Step 2: t = front; x = t->data; front = front->next; free(t); return x.

Deque example: insertRear(5), insertRear(7), insertFront(3) gives 3, 5, 7; deleteRear() removes 7; deleteFront() removes 3, leaving 5.

Answer frame. Short note: define both, deque operations and types, then priority queue rules, algorithm, applications. Deque: define, draw, four operations, two types, example. Priority queue algorithm: definition, ordered insert, delete from front, example.

Asked: [7 marks] (Nov 2018) Write a short note on D queue and priority queue. Asked: [7 marks] (Jun 2020) Write an algorithm for insertion and deletion in Priority Queues. Asked: [7 marks] (Dec 2024) What is a DeQueue? Explain its operation with example.

Queue simulation

Definition. Queue simulation uses a queue data structure to model a real waiting line and study its behaviour over time.

Key points.

Customers arrive at random times and are enqueued at the rear; the server serves the customer at the front and dequeues, following FIFO.
A simulation clock advances, and each event (arrival, start of service, departure) updates the queue.
Real example: at a ticket counter the length of the queue and each person's waiting time are measured to decide how many counters are needed.
Other examples are a printer queue and bank tellers; results give average waiting time and server utilisation.

Application of queues

Definition. Queues are used wherever items must be processed in the order in which they arrive.

Key points.

CPU and disk scheduling keep waiting processes in a ready queue.
Printer spooling and keyboard buffers hold jobs in arrival order.
Breadth-first search of a graph and level-order traversal of a tree use a queue.
Simulation of real waiting lines, and data transfer between two processes (pipes, IO buffers).

Last-minute revision

Stack is LIFO, one end (top); empty top = -1; overflow top == MAX-1; push and pop are O(1).
Queue is FIFO; insert at rear, delete at front; circular queue full when (rear+1)%MAX == front.
Linked stack: push new->next = top; top = new; pop top = top->next; free.
Precedence: ^ (right-assoc.) > * / > + -; ( is pushed, ) pops to (.
$A+(B+D)/E-F*(G+H/K)$ = $ABD+E/+FGHK/+*-$; $a-b/c*d+e*f/g$ = $abc/d*-ef*g/+$.
$A+B-CDE$F$G$ = $AB+CD*EFG\$$*-$.
Postfix evaluation: $234*6/+$ (A=2, B=3, C=4, D=6) = 4; first popped is the right operand.
Recursion needs a base case; each call uses the system stack; fact(3) = 6.
Tower of Hanoi: $T(n) = 2T(n-1)+1 = 2^n-1$ moves; 7 moves for 3 disks.
Deque: four operations, input- and output-restricted; priority queue removes the highest priority first.

Memory hooks

Plates on a table: last placed, first taken (stack); a ticket line is first come, first served (queue).
"Operand out, operator wait": operands go straight to output, operators wait on the stack.
Hanoi: move n-1 away, move the big one, move n-1 back.
Circular queue: rear + 1 modulo MAX, like a clock wrapping at 12.

Coverage checklist

Stacks as ADT: 2 questions
Different implementation of stack: 5 questions
multiple stacks: definition and layout
Application of Stack: Conversion of infix to postfix notation using stack: 7 questions
evaluation of postfix expression: rules and Dec 2023 evaluation
Recursion: 3 questions
Queues: Queues as ADT: definition
Different implementation of queue: 1 question
Circular queue: 2 questions
Concept of Dqueue and Priority Queue: 3 questions
Queue simulation: 1 question
Application of queues: uses listed

Account

Data Structure (CS-303) - Unit 2 Short Notes

How unit 2 is examined

Stacks as ADT

Different implementation of stack

Multiple stacks

Application of Stack: infix to postfix conversion

Evaluation of postfix expression

Recursion

Queues as ADT

Different implementation of queue

Circular queue

Concept of Dqueue and Priority Queue

Queue simulation

Application of queues

Last-minute revision

Memory hooks

Coverage checklist