Deque & Priority Queue · Data Structures

Deque (double-ended queue)

A deque (pronounced "deck") allows insertion and deletion at both ends. It can act as a stack or a queue.

Operation	Effect
`pushFront(x)` / `pushBack(x)`	insert at the front / rear
`popFront()` / `popBack()`	remove from the front / rear

Special cases: an input-restricted deque allows insertion at one end only; an output-restricted deque allows deletion at one end only.

A circular array makes every deque operation O(1):

#include <stdio.h>
#define N 8

int d[N], front = 0, size = 0;

void pushBack(int x)  { d[(front + size) % N] = x; size++; }
void pushFront(int x) { front = (front - 1 + N) % N; d[front] = x; size++; }
int popFront(void)    { int x = d[front]; front = (front + 1) % N; size--; return x; }
int popBack(void)     { size--; return d[(front + size) % N]; }

void show(const char *msg) {
    printf("%-14s [", msg);
    for (int i = 0; i < size; i++) printf(i ? " %d" : "%d", d[(front + i) % N]);
    printf("]\n");
}

int main(void) {
    pushBack(20); pushBack(30); show("pushBack x2:");
    pushFront(10); show("pushFront 10:");
    pushBack(40); show("pushBack 40:");
    printf("popFront -> %d\n", popFront());
    printf("popBack  -> %d\n", popBack());
    show("now:");
    return 0;
}

Output

pushBack x2:   [20 30]
pushFront 10:  [10 20 30]
pushBack 40:   [10 20 30 40]
popFront -> 10
popBack  -> 40
now:           [20 30]

Try it Yourself

Priority queue

In a priority queue, each element has a priority, and dequeue always removes the element with the highest priority (or lowest, for a min-priority queue) — not the oldest. Hospital emergency rooms, CPU scheduling and Dijkstra's shortest-path algorithm all use one.

Possible implementations:

Implementation	Insert	Remove highest
Unsorted array	O(1)	O(n) — scan for the max
Sorted array	O(n) — shift into place	O(1)
Binary heap	O(log n)	O(log n)

A sorted array is simple and fine for small inputs:

#include <stdio.h>

typedef struct { char name[12]; int priority; } Patient;
Patient pq[10];
int n = 0;

void insert(const char *name, int pr) {           // keep sorted by priority, highest last
    int i = n - 1;
    while (i >= 0 && pq[i].priority > pr) { pq[i + 1] = pq[i]; i--; }
    snprintf(pq[i + 1].name, sizeof pq[i + 1].name, "%s", name);
    pq[i + 1].priority = pr;
    n++;
}

Patient removeMax(void) { return pq[--n]; }

int main(void) {
    insert("Anil", 2);     // 1 = mild ... 5 = critical
    insert("Bhavna", 5);
    insert("Chetan", 1);
    insert("Divya", 4);
    while (n > 0) {
        Patient p = removeMax();
        printf("treating %-7s (priority %d)\n", p.name, p.priority);
    }
    return 0;
}

Output

treating Bhavna  (priority 5)
treating Divya   (priority 4)
treating Anil    (priority 2)
treating Chetan  (priority 1)

Try it Yourself

For large inputs, use a binary heap, which gives O(log n) for both operations — covered in Heaps & Heap Sort.

Test yourself

4 questions · pick an answer to check it instantly

1
Which structure allows insertion and deletion at both ends?
2
In a max-priority queue, which element is removed first?
3
What is the best common implementation of a priority queue?
4
An output-restricted deque allows deletion at...

#Deque (double-ended queue)

#Priority queue

Test yourself

Deque (double-ended queue)

Priority queue