Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Circular queue of size N: full condition? from Lesson 3.3.2
• How many valid stack permutations do 3 items have? from Lesson 3.2.3
• What does O(1) amortized mean in plain words? (Hint: Lesson 2.2 counts total work.) from Lesson 2.2

1 · The Hook

🎣

In a hospital emergency room, patients are not seen strictly by arrival: a heart attack goes before a sprained wrist. At a bus stop, someone may join at the back but an elderly passenger may be let in at the front. Real waiting lines bend the FIFO rule, and each variant has its own structure.

2 · Predict First

🤔

Two stacks, in and out, act as a queue: enqueue pushes onto in; dequeue pops from out, first pouring all of in into out if out is empty. After enqueue 1, 2, 3, dequeue, enqueue 4, and three dequeues, what is printed, and how many single moves from in to out happened?

int in[20], out[20], ti = -1, to = -1, moves = 0;

void enqueue(int x) { in[++ti] = x; }

int dequeue(void)
{
    if (to == -1)                       /* refill only when out is empty */
        while (ti != -1) { out[++to] = in[ti--]; moves++; }
    return out[to--];
}

int main(void)
{
    enqueue(1); enqueue(2); enqueue(3);
    printf("%d ", dequeue());
    enqueue(4);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("| moves=%d\n", moves);
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

1 2 3 4 | moves=4

Pouring reverses the order, so the oldest item ends up on top of out: FIFO. Each item is moved at most once from in to out.

Deque (double-ended queue)

A deque allows insertion and deletion at both ends: insertFront, insertRear, deleteFront, deleteRear, all O(1) with a circular array (or with linked structures, Phase 3.4). Restricted versions: input-restricted (insert at one end only, delete at both) and output-restricted (insert at both, delete at one). A deque can act as a stack or as a queue.

Example: start empty; insertRear 5, insertFront 3, insertRear 8, insertFront 1, deleteRear, deleteFront, insertRear 9 → 3 5 9.

Priority queue

A priority queue stores items with priorities; deletion always removes the item with the highest priority (or lowest key), not the oldest. Simple implementations:

Queue from two stacks

As in Predict First. Costs: enqueue O(1). A dequeue that finds out empty costs O(k) to pour k items, but every item is pushed and popped at most twice in total, so n operations cost O(n): O(1) amortized per operation, O(n) worst case for one dequeue.

A simpler but slower variant pours back and forth on every operation: O(n) per operation.

Stack from two queues

Push: enqueue into q1. Pop: dequeue all but the last item of q1 into q2, take the last item, then swap the roles of q1 and q2. Push O(1), pop O(n). (Or make push O(n) and pop O(1).) Unlike the two-stack queue, there is no amortized saving: each pop really moves n − 1 items.

4 · Visual

Queue from two stacks (enqueue 1 2 3, dequeue, enqueue 4, dequeue x3):

            in          out        printed
enq 1,2,3   1 2 3       -
deq         -           3 2 1      pour 3 items (moves = 3), pop -> 1
            -           3 2
enq 4       4           3 2
deq         4           3          pop -> 2
deq         4           -          pop -> 3
deq         -           4          out empty: pour 1 item (moves = 4), pop -> 4

Deque:   insertFront/deleteFront <-> [ 3 | 5 | 9 ] <-> insertRear/deleteRear

Pouring reverses the order; each item is poured at most once.

Two stacks make a queue.

5 · Worked Examples

Example 1 Easy

A deque starts empty: insertRear 5, insertFront 3, insertRear 8, insertFront 1, deleteRear, deleteFront, insertRear 9. What is in the deque, front to rear?

Solution

After the inserts: 1 3 5 8. deleteRear removes 8, deleteFront removes 1, then 9 joins the rear: 3 5 9.

Example 2 Medium

Unsorted array priority queue with n items: what are the costs of insert and of delete-max? Why is a sorted array the opposite?

Solution

Unsorted: insert O(1) (append), delete-max O(n) (find the maximum, then fill the gap). Sorted: insert O(n) (shift to keep order), delete-max O(1) (it sits at the end).

Example 3 GATE

A queue is built from two stacks (pour-when-empty method). n enqueues are followed by n dequeues. How many push and pop operations on the stacks happen in total?

Solution

n enqueues: n pushes onto in. The first dequeue pours n items: n pops + n pushes. The n dequeues pop from out: n pops. Total pushes 2n, pops 2n: 4n stack operations, O(1) amortized per queue operation.

6 · GATE Traps

⚠️

• A priority queue removes by priority, not by arrival time.
• Queue from two stacks: one dequeue can cost O(n), but the amortized cost is O(1).
• Stack from two queues: each pop costs O(n) (or each push), with no amortized saving.
• Input-restricted deque: insert at one end only; output-restricted: delete at one end only.
• Pour from in to out only when out is empty, or FIFO order breaks.

8 · Memory Hook

🧠

“Emergency room, bus door, double stack.” Priority queues serve the sickest first; a deque opens doors at both ends; two stacks back to back flip the order twice and give a queue.

9 · Connect the Dots

Phase 3 so far used arrays for everything: fixed size, cheap indexing, expensive insertion in the middle. Lesson 1.6 showed records that point to each other, and Lesson 1.7 memory requested at run time. Next lesson answers: how do pointers and run-time memory build a list that grows one item at a time and inserts anywhere without shifting?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markPriority queue

A priority queue’s delete operation removes:

• (A) the oldest item
• (B) the item with the highest priority
• (C) a random item
• (D) the newest item

Q2MCQ2 marksTwo stacks

What does this print?

int in[20], out[20], ti = -1, to = -1, moves = 0;

void enqueue(int x) { in[++ti] = x; }

int dequeue(void)
{
    if (to == -1)                       /* refill only when out is empty */
        while (ti != -1) { out[++to] = in[ti--]; moves++; }
    return out[to--];
}

int main(void)
{
    enqueue(1); enqueue(2); enqueue(3);
    printf("%d ", dequeue());
    enqueue(4);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("| moves=%d\n", moves);
    return 0;
}

• (A) 1 2 3 4 | moves=4
• (B) 1 2 3 4 | moves=3
• (C) 3 2 1 4 | moves=4
• (D) 1 2 3 4 | moves=7

Q3NAT2 marksStack from queues

A stack is built from two queues with O(1) push and O(n) pop (move all but the last item). With 5 items in the stack, how many items are moved from one queue to the other during one pop?

Numerical answer: ________

Q4MCQ1 markDeque

An output-restricted deque allows:

• (A) insertion and deletion at one end only
• (B) insertion at both ends, deletion at one end
• (C) insertion at one end, deletion at both ends
• (D) no deletions

Q5MSQ2 marksCosts

Which are true?

• (A) A sorted-array priority queue has O(1) delete-highest.
• (B) An unsorted-array priority queue has O(1) delete-highest.
• (C) Queue from two stacks has O(1) amortized dequeue.
• (D) A deque supports O(1) insertion at both ends.

11 · Rule Card

• Deque: insert/delete at both ends, O(1); input-/output-restricted variants.
• Priority queue: delete highest priority; unsorted O(1)/O(n), sorted O(n)/O(1); Phase 5 gives O(log n)/O(log n).
• Queue from 2 stacks: enqueue push(in); dequeue pop(out), pour in → out only when out empty; O(1) amortized.
• Stack from 2 queues: push O(1), pop O(n) (or the reverse).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

dequeinput-/output-restricted dequepriority queuequeue from two stacksstack from two queuesamortized cost

13 · Answer Vault