Data Structures (AD-303) - Unit 2 Short Notes

How unit 2 is examined

This unit covers stack and queue ADTs, their array and linked implementations, infix-to-postfix conversion, circular queue and priority queue; infix-to-postfix, circular queue and the array stack and queue programs carry the marks.

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">Low weight</span>

Definition. <mark>A stack is an abstract data type in which insertion and deletion happen only at one end, called the top, so the last element pushed is the first popped (LIFO).</mark>

Key points.

1. The ADT is defined by its operations, not its storage: push(x) inserts at the top, pop() removes and returns the top, peek() reads the top without removing it, and isEmpty() tests whether the stack is empty; isFull() is only an array helper.
2. In the array implementation top starts at -1, push does stack[++top] = x, pop returns stack[top--], overflow is top == MAX-1 and underflow is top == -1.
3. In the linked implementation top points to the first node, so push and pop are head insertion and deletion in O(1).
4. The array version has a fixed size; the linked version grows dynamically at the cost of one pointer per node.

Asked: [7 marks] (Dec 2025) Define Stack as an ADT. Explain the array and linked list implementation of stacks.

Different implementation of stack

<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. A stack can be implemented with a one-dimensional array stack[MAX] and an integer top, initialised to -1 to show that the stack is empty.

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 424 209" width="424" height="209" role="img" aria-label="Array stack of size MAX with top = 2; indices 0..MAX-1, elements at 0,1,2 filled, T is the top pointer"><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="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="M59,169 L107,169"/><path class="e" d="M145,169 L193,169"/><path class="e" d="M231,169 L279,169"/><path class="e" d="M317,169 L365,169"/><path class="e hi" d="M212,59 L212,148" marker-end="url(#ahh9)"/><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">I0</text><circle class="n" cx="126" cy="169" r="18"/><text class="t" x="126" y="169" dy=".35em" text-anchor="middle">I1</text><circle class="n" cx="212" cy="169" r="18"/><text class="t" x="212" y="169" dy=".35em" text-anchor="middle">I2</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">I3</text><circle class="n" cx="384" cy="169" r="18"/><text class="t" x="384" y="169" dy=".35em" text-anchor="middle">I4</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">T</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Array stack of size MAX with top = 2; indices 0..MAX-1, elements at 0,1,2 filled, T is the top pointer</figcaption></figure>

Key points.

1. The stack is stored in int stack[MAX] and the index top always holds the position of the latest element, with top = -1 meaning empty.
2. Push first checks overflow (top == MAX-1); if not full it increments top and stores the value at stack[top].
3. Pop first checks underflow (top == -1); if not empty it returns stack[top] and decrements top.
4. Peek returns stack[top] without changing top (underflow if top == -1); isEmpty tests top == -1 and isFull tests top == MAX-1.
5. Every operation takes O(1) time, but the size is fixed at compile time, so memory is wasted or overflow occurs.

#include <stdio.h>
#define MAX 5
int stack[MAX], top = -1;
void push(int x){ if(top==MAX-1) printf("Overflow\n"); else stack[++top]=x; }
int pop(){ if(top==-1){ printf("Underflow\n"); return -1; } return stack[top--]; }
int peek(){ if(top==-1){ printf("Underflow\n"); return -1; } return stack[top]; }
int main(){ int c, x;
  while(printf("1.Push 2.Pop 3.Peek 5.Exit\n"), scanf("%d",&c)==1 && c!=5){
    if(c==1){ scanf("%d",&x); push(x); }
    else if(c==2) printf("%d\n", pop());
    else if(c==3) printf("%d\n", peek());
    else printf("Bad\n"); }
  return 0; }
// Input: 1 10 1 20 3 2 5  Output: 20 20
int isEmpty(){ return top==-1; }
int isFull(){ return top==MAX-1; }

Trace, MAX = 5: push 10, 20, 30 (top 2); pop gives 30 (top 1); peek gives 20 (top 1); pop 20, pop 10 (top -1); another pop prints Underflow.

Linked stack. top points to the newest node, the last node's next is NULL, and top == NULL means empty.

<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 288 58" width="288" height="58" role="img" aria-label="list diagram"><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="ah10" 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="ahh10" 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(#ah10)"/><rect class="n hi" 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(#ah10)"/><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(#ah10)"/><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></figure>

struct node { int data; struct node *next; } *top = NULL;
void push(int x){ struct node *n = malloc(sizeof *n);
  if(n==NULL){ printf("Overflow\n"); return; }
  n->data = x; n->next = top; top = n; }
int pop(){ if(top==NULL){ printf("Underflow\n"); return -1; }
  struct node *t = top; int x = t->data; top = top->next; free(t); return x; }
int peek(){ return top==NULL ? -1 : top->data; }
int isEmpty(){ return top==NULL; }

Diagram: draw top as a box with an arrow to the newest node; each node box has a data field and a next field, arrows run downwards, and the last node holds NULL. Peek returns top->data after the NULL check, and isEmpty returns top == NULL. Push checks malloc for NULL, then new->next = top; top = new; pop checks top == NULL, saves the data, advances top and frees the node, in O(1).

Answer frame. Open with the LIFO definition; draw the array and top arrow; develop points 1-5 and give the program; for the linked version draw the chain and give struct, push and pop; close with "all operations are O(1)".

Pitfall: Checking overflow with top == MAX instead of top == MAX-1 allows a write outside the array. Asked: [7 marks] (Dec 2024, Dec 2025) Explain the array implementation of stack ADT in detail.

Multiple stacks

<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">Not asked since 2022</span>

Definition. Multiple stacks means keeping two or more stacks in one array so that unused space is shared.

Key points.

1. Two stacks share one array a[MAX]: stack 1 starts at index 0 and grows right, stack 2 starts at MAX-1 and grows left.
2. The tops are top1 = -1 and top2 = MAX, and the array is full exactly when top1 + 1 == top2.
3. Unlike two separate arrays, neither stack overflows while free space remains.

Application of Stack: Conversion of infix to postfix

<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">High weight</span>

Definition. <mark>Infix has the operator between its operands (A+B), postfix has it after them (AB+); a stack holds operators until their turn so that precedence and associativity are respected without brackets.</mark>

Key points.

1. Precedence from highest to lowest is ^, then * and /, then + and -; operators of equal precedence are resolved by associativity.
2. + - * / are left-to-right associative, so an equal-precedence operator on the stack is popped first; ^ is right-to-left, so an equal ^ is not popped.
3. An operand is written straight to the output, because the order of operands never changes between infix and postfix.
4. An incoming operator pops every stack operator of higher precedence (or equal and left-associative) to the output, and is then pushed.
5. A ( is always pushed, and it has the lowest precedence while on the stack so nothing pops it except ).
6. A ) pops operators to the output until ( is found, and the ( is discarded; at the end of input everything left on the stack is popped to the output.
7. Each symbol is read once and each operator is pushed and popped at most once, so the conversion takes O(n) time for n symbols.

Steps.

Step 1: Scan left to right with an empty stack; append operands to the postfix string.
Step 2: Push '('; on ')' pop to the output until '(' and discard it.
Step 3: On an operator, pop while the top has higher precedence (or equal, left-associative); then push it.
Step 4: At the end, pop all remaining operators to the output.

Example. Convert $(A+B)*C-D/E$.

Answer: AB+C*DE/-

Answer frame. Open with infix and postfix; state precedence and associativity; write the steps; draw the three-column trace; close with the result and O(n).

Pitfall: Popping an equal-precedence ^ (it is right-associative) or forgetting to discard ( gives a wrong string. Asked: [7 marks] (Dec 2022, Dec 2025) How can you convert an infix expression to postfix operation using stack? Give one example. Asked: [7 marks] (Jun 2023, Jun 2024) Write an algorithm to convert infix expression into postfix form using stack. Also evaluate the given postfix form using stack: 2 3 9 * + 2 3 ^ - 6 2 / + Asked: [7 marks] (Dec 2025) Explain the algorithm to convert an infix expression to a postfix notation using a stack.

Evaluation of postfix expression

<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">Not asked since 2022</span>

Definition. Postfix is evaluated with an operand stack: push operands, and on an operator pop two, apply it and push the result.

Key points.

1. Scan left to right; a number is pushed, and an operator pops the top as the right operand b and the next as the left operand a, then pushes a op b.
2. The single value left at the end is the answer.
3. The 2022-2025 expression 2 3 9 * + 2 3 ^ - 6 2 / + runs as follows.

Answer: 24

Balanced parentheses use the same stack: push each opening bracket, and on a closing bracket pop and check that it is the matching opener. Each symbol is handled once, so the check is O(n).

Three error cases: (1) pop from an empty stack, as in a+b); (2) mismatch, as in (]; (3) stack not empty at the end, as in ((a+b). Valid trace for {[()]}:

Invalid ((]: push (, push (, then ] pops (, a mismatch, so Not balanced. For ((a+b) the input ends with ( left on the stack, so it is not balanced.

int balanced(char *s){ char st[100]; int t=-1;
  for(int i=0; s[i]; i++){ char c=s[i];
    if(c<mark>'('||c</mark>'{'||c=='[') st[++t]=c;
    else if(c<mark>')'||c</mark>'}'||c==']'){
      if(t==-1) return 0;                    /* empty stack */
      char o=st[t--];
      if((c==')'&&o!='(')||(c=='}'&&o!='{')||(c==']'&&o!='[')) return 0; } }
  return t==-1; }                            /* leftover opener */

Asked: [7 marks] (Dec 2024) Explain an algorithm to check whether the parentheses in an expression are balanced using a stack.

Recursion

<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">Not asked since 2022</span>

Definition. Recursion is a function calling itself on a smaller input until a base case stops it.

Key points.

1. Every recursive function needs a base case, such as fact(0)=1, and a recursive case that moves towards it, such as fact(n)=n*fact(n-1).
2. Each call pushes a frame (parameters, locals, return address) on the system call stack, and the frames are popped in reverse order as calls return.
3. Missing base case gives stack overflow; recursion can always be replaced by an explicit stack.

Queues 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">Not asked since 2022</span>

Definition. A queue is a linear ADT in which insertion (enqueue) is at the rear and deletion (dequeue) is at the front, so the first element in is the first out (FIFO).

Key points.

1. The operations are enqueue(x), dequeue(), front(), isEmpty() and isFull().
2. front and rear are both -1 when the queue is empty; overflow and underflow are checked as in the next section.
3. Enqueue and dequeue each take O(1) time.

Different implementation of queue

<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. A linear queue is implemented with an array queue[MAX] and two integers front and rear, both initialised to -1.

Key points.

1. Enqueue checks overflow (rear == MAX-1); on the first insertion it sets front = 0, then does rear++ and stores the element.
2. Dequeue checks underflow (front == -1 || front > rear), returns queue[front] and increments front.
3. Display prints elements from front to rear.
4. Freed slots at the front are never reused, which is the drawback fixed by the circular queue.
5. Limitations of the linear queue: false overflow, wasted front slots, fixed size, and no way to reset except when it becomes empty.

#include <stdio.h>
#define MAX 5
int queue[MAX], front = -1, rear = -1;
void enqueue(int x){
  if(rear == MAX-1){ printf("Overflow\n"); return; }
  if(front == -1) front = 0;
  queue[++rear] = x; }
void dequeue(){
  if(front == -1 || front > rear){ printf("Underflow\n"); return; }
  printf("%d\n", queue[front++]); }
void display(){ for(int i=front; front!=-1 && i<=rear; i++) printf("%d ", queue[i]); }
int main(){ int c,x;
  while(1){ printf("\n1.Enqueue 2.Dequeue 3.Display 4.Exit: "); if(scanf("%d",&c)!=1||c==4) break;
    if(c==1){ printf("Value: "); scanf("%d",&x); enqueue(x); }
    else if(c==2) dequeue(); else display(); }
  return 0; }

Sample run: choice 1, value 10; choice 1, value 20; choice 3 prints 10 20; choice 2 prints 10; choice 3 prints 20; choice 4 exits.

Answer frame. Open by defining the queue and FIFO; declare array, front and rear; write enqueue, dequeue, display and a menu main() as above; close by noting the wasted front space.

Asked: [7 marks] (Jun 2023, Jun 2024) Write a program in 'C' to implementation of QUEUE.

Circular queue

<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 circular queue is an array queue in which the last position is joined to the first, using $(rear+1)\%MAX$, so freed slots at the front are reused.</mark>

Formula. $rear=(rear+1)\%MAX$, $front=(front+1)\%MAX$. Full: $(rear+1)\%MAX<mark>front$. Empty: $front</mark>-1$.

Key points.

1. A linear queue suffers false overflow: rear == MAX-1 says full although dequeued front slots are free.
2. Modulo arithmetic makes rear wrap from MAX-1 to 0, so every slot is usable.
3. Enqueue reports overflow if (rear+1)%MAX == front; the first insertion sets front = rear = 0.
4. Dequeue reports underflow if front == -1; removing the only element (front == rear) resets both to -1.

void enqueue(int x){
  if((rear+1)%MAX==front){ printf("Overflow"); return; }
  if(front==-1) front=rear=0; else rear=(rear+1)%MAX;
  q[rear]=x; }
int dequeue(){
  if(front==-1){ printf("Underflow"); return -1; }
  int x=q[front];
  if(front==rear) front=rear=-1; else front=(front+1)%MAX;
  return x; }

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 320.8" width="338" height="320.8" role="img" aria-label="Circular queue, MAX = 5; slots 0-4 form a ring and rear moves 4 to 0 through (rear+1)%MAX"><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="ah11" 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="ahh11" 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(#ah11)"/><path class="e" d="M292.9,144.3 L260.6,260.6" marker-end="url(#ah11)"/><path class="e" d="M236,280.8 L104,280.8" marker-end="url(#ah11)"/><path class="e" d="M77.9,262.5 L45.6,146.2" marker-end="url(#ah11)"/><path class="e hi" d="M55.8,115.5 L151.5,51.6" marker-end="url(#ahh11)"/><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="255" cy="280.8" r="18"/><text class="t" x="255" y="280.8" dy=".35em" text-anchor="middle">Q2</text><circle class="n" cx="83" cy="280.8" r="18"/><text class="t" x="83" y="280.8" dy=".35em" text-anchor="middle">Q3</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Q4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Circular queue, MAX = 5; slots 0-4 form a ring and rear moves 4 to 0 through (rear+1)%MAX</figcaption></figure>

Example. Wrap-around trace for MAX = 5.

Now $(1+1)\%5 = 2 = front$, so the queue is full; a linear queue would have reported false overflow at 60.

Answer frame. Open with the false overflow of the linear queue and define the circular queue; draw the ring; write the formula, the routines and the trace; add the comparison table; close with "it reuses space in O(1) operations".

Asked: [7 marks] (Dec 2023, Dec 2024) How do you implement a circular queue in C using array? Write routines to implement operations for it. Differentiate between Linear Queue and Circular Queue. What are the limitations of queue? Explain the algorithms for various operations of circular queue.

Concept of Dqueue and Priority Queue

<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">Low weight</span>

Definition. A deque is a queue where insertion and deletion are allowed at both ends; a priority queue removes the element with the highest priority first, whatever the arrival order.

Key points.

1. A deque has four operations, insert-front, insert-rear, delete-front and delete-rear; input-restricted and output-restricted deques limit one end.
2. A priority queue can be an unsorted array or list (insert O(1), delete O(n) by searching the highest priority), a sorted list (insert O(n), delete O(1)), or a heap (both O(log n)).
3. In a heap, insert places the item at the last position and sifts it up; delete takes the root, moves the last item to the root and sifts it down.
4. A heap is stored in an array with 1-based indices: for node $i$, parent $= \lfloor i/2 \rfloor$, left child $= 2i$, right child $= 2i+1$.
5. Convention: in a descending-priority queue the largest number is served first (max-heap), in an ascending-priority queue the smallest number is served first (min-heap); state which one you use.
6. Ties are served FIFO only in the sorted-list and queue-per-priority versions; a binary heap needs an arrival-number tiebreak to keep FIFO.

Sorted linked list (highest priority first):

Insert(x, p): Step 1: Create node N(x, p); if malloc fails, report overflow.
Step 2: If front == NULL or p > front->pri: N->next = front, front = N, stop.
Step 3: T = front; while T->next != NULL and T->next->pri >= p: T = T->next.
Step 4: N->next = T->next, T->next = N (>= keeps ties FIFO).
Delete: Step 1: If front == NULL, report underflow.
Step 2: T = front, x = T->data, front = front->next, free T, return x.

Sift-up: while i > 1 && h[i/2] < h[i] swap h[i] with h[i/2] and set i = i/2. Sift-down: with i = 1, while 2i <= n pick the larger child c, and if h[c] > h[i] swap and set i = c, else stop. Linked example: inserting (A,2), (B,5), (C,3) gives B(5) -> C(3) -> A(2); delete returns B.

Example. Max-heap [50, 30, 40, 10, 20]. Insert 45 at index 6; parent 3 holds 40, so swap; parent 1 holds 50, so stop: [50, 30, 45, 10, 20, 40]. Delete: remove 50, move last item 40 to the root, swap with larger child 45: [45, 30, 40, 10, 20].

<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 316 198" width="316" height="198" role="img" aria-label="Max-heap after inserting 45 at index 6 and sifting it up; after the delete it is 45 over 30 (10, 20) and 40"><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="ah12" 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="ahh12" 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><line class="e" x1="168" y1="39" x2="80" y2="103"/><line class="e" x1="168" y1="39" x2="256" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="124" y2="167"/><line class="e" x1="256" y1="103" x2="212" y2="167"/><circle class="n" cx="168" cy="39" r="17"/><text class="t" x="168" y="39" dy=".35em" text-anchor="middle">50</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">20</text><circle class="n hi" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">40</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Max-heap after inserting 45 at index 6 and sifting it up; after the delete it is 45 over 30 (10, 20) and 40</figcaption></figure>

Asked: [7 marks] (Dec 2022) Write an algorithm for insertion and deletion in priority Queues.

Queue simulation

<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">Low weight</span>

Definition. Queue simulation is a discrete-event simulation: a clock advances tick by tick, and arrivals (enqueue) and service completions (dequeue) are the events, used to study waiting time and service.

Key points.

1. Arriving customers are enqueued at the rear and the next one served is dequeued from the front (FIFO).
2. At a ticket counter, arrivals are random, each service takes some time, and the program measures average waiting time and queue length.
3. A printer queue works the same way: jobs are printed in arrival order.
4. The results help decide how many counters or servers are needed; applications include a bank counter, CPU scheduling and a call centre.
5. Average waiting time $= \frac{\sum (\text{start} - \text{arrival})}{\text{customers served}}$.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-05" viewBox="0 0 510 80" width="510" height="80" role="img" aria-label="Waiting line; C1 at the FRONT is served next by the server, new arrivals join at the REAR (C3)"><style>#dsfig-u2-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-05 .t{fill:#16181D;font-weight:500}#dsfig-u2-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-05 .dot{fill:#16181D}#dsfig-u2-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-05 .ah{fill:#454C5A}#dsfig-u2-05 .ah.hi{fill:#2340B8}#dsfig-u2-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-05 .e{stroke:#B1B7C3}html.dark #dsfig-u2-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-05 .t{fill:#E6E8ED}html.dark #dsfig-u2-05 .t.inv{fill:#0F1115}html.dark #dsfig-u2-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-05 .dot{fill:#E6E8ED}html.dark #dsfig-u2-05 .ann{fill:#8FA3FF}html.dark #dsfig-u2-05 .lbl{fill:#858D9C}html.dark #dsfig-u2-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-05 .ah{fill:#B1B7C3}html.dark #dsfig-u2-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah13" 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="ahh13" 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="M451,40 L362,40" marker-end="url(#ah13)"/><path class="e" d="M322,40 L276,40" marker-end="url(#ah13)"/><path class="e" d="M236,40 L190,40" marker-end="url(#ah13)"/><path class="e hi" d="M150,40 L61,40" marker-end="url(#ahh13)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Srv</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">C1</text><circle class="n" cx="255" cy="40" r="18"/><text class="t" x="255" y="40" dy=".35em" text-anchor="middle">C2</text><circle class="n" cx="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">C3</text><circle class="n" cx="470" cy="40" r="18"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">Arr</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Waiting line; C1 at the FRONT is served next by the server, new arrivals join at the REAR (C3)</figcaption></figure>

Step 1: clock = totalWait = served = 0; server free; queue empty.
Step 2: If a customer arrives at this tick, enqueue it with its arrival time.
Step 3: If the server is free and the queue is not empty, dequeue it, totalWait += clock - arrival, served++, busy until clock + service.
Step 4: clock++; repeat from Step 2 until time ends.
Step 5: Average wait = totalWait / served.

Example. One counter, five customers.

Average waiting time = 11 / 5 = 2.2 minutes.

Asked: [7 marks] (Dec 2025) Explain the concept of Queue simulation with a real-world example.

Application of queues

<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">Not asked since 2022</span>

Definition. Queues are used wherever items must be processed in arrival order.

Key points.

1. CPU and job scheduling, and printer spooling, serve requests in FIFO order.
2. Breadth-first search uses a queue to visit nodes level by level.
3. Buffers for keyboard input, streaming and network packets are queues.

Last-minute revision

• Stack is LIFO; queue is FIFO.
• Array stack: top = -1 empty, overflow at top == MAX-1.
• Linear queue: front = rear = -1, overflow at rear == MAX-1.
• Circular queue: rear = (rear+1)%MAX; full when (rear+1)%MAX == front.
• Precedence: ^ > * / > + -; ^ is right-associative.
• (A+B)*C-D/E gives AB+C*DE/-.
• 2 3 9 * + 2 3 ^ - 6 2 / + evaluates to 24.
• Balanced brackets: push openers, match on closers, stack empty at end.

Memory hooks

• Stack of plates: last on, first off.
• "Operand out, operator wait": operands go straight to the output.
• Circular queue: modulo makes the line a ring.
• Postfix evaluation: pop b first, then a.

Coverage checklist

• Stacks as ADT: Q9.
• Different implementation of stack: Q7.
• multiple stacks: covered, not asked.
• Application of Stack: Conversion of infix to postfix notation using stack: Q1, Q2, Q3.
• evaluation of postfix expression: Q2 evaluation, Q10 balanced parentheses.
• Recursion: covered, not asked.
• Queues: Queues as ADT: covered, not asked.
• Different implementation of queue: Q6.
• Circular queue: Q4.
• Concept of Dqueue and Priority Queue: Q5.
• Queue simulation: Q8.
• Application of queues: covered, not asked.