Applications of Deque

A deque (double-ended queue) is a data structure that allows insertion and deletion from both ends — front and rear. This flexibility makes it useful in real-world situations where a simple queue or stack alone is not enough.

Real-life examples from the textbook

Train ticket counter

A normal queue forms at a ticket counter. A person at the front buys a ticket and leaves. Later, that same person returns to ask a follow-up question. Since they have already purchased a ticket, they are given the privilege to re-join the queue from the front — not the rear. This is a classic case where a deque's ability to add at the front is needed.

Highway toll tax booth

Vehicles at a toll booth are served in queue order. If there are multiple parallel booths, each has its own queue. When one booth finishes serving all its vehicles, vehicles from the other booths are asked to move to the now-vacant booth. The vehicles that leave their current queue are the ones at the end of that queue (the rear), because those are the last to be served at the original booth. They then join the front of the queue at the vacant booth. So vehicles are removed from the rear of one queue and inserted at the front of another — again, a deque operation.

Computer science applications of deque

Browser history (URLs)

A stack is normally used to store recently closed tabs — pressing Ctrl+Shift+T opens the most recently closed URL first. However, the browser can only store a fixed number of URLs in history. When this list becomes too large, the oldest (least recently visited) URLs are deleted from the end of the list. So the history behaves like a deque: new URLs are added at one end (like a stack), but when space runs out, the oldest are removed from the opposite end.

Undo and Redo in text editors

The same principle applies. The most recent actions are undone first (stack behaviour), but the list of undoable actions has a fixed size. When it fills up, the oldest actions are dropped from the other end — again, a deque.

Palindrome checking

To check whether a given string is a palindrome using a deque:

1. Process the string character by character from left to right.
2. Insert each character into the deque from the tail/rear (like a normal queue). …