Computer Science · Ch 4 — Queue
Operations on Deque
Operations on Deque
A deque (double-ended queue) is a data structure that allows insertion and deletion of elements from both ends — the front and the rear. This makes it more flexible than a standard queue, which only allows insertion at the rear and deletion from the front.
The textbook defines four core operations on a deque:
- INSERTFRONT — Adds a new element at the front of the deque.
- INSERTREAR — Adds a new element at the rear of the deque. This is identical to the normal queue's enqueue operation.
- DELETIONFRONT — Removes an element from the front of the deque. This is the same as the normal queue's dequeue operation.
- DELETIONREAR — Removes an element from the rear of the deque. This operation has no equivalent in a standard queue.
Because a deque can operate from both ends, it can mimic other data structures depending on how you restrict its operations.
The textbook includes two activities that test this idea:
- Activity 4.3: If insertion and deletion are both done from the same end (e.g., both from the front, or both from the rear), the deque behaves like a stack (Last In, First Out).
- Activity 4.4: If insertion and deletion are done from opposite ends (e.g., insert at rear, delete from front), the deque behaves like a queue (First In, First Out).
To work efficiently with a deque, you also need the same supporting operations used in a normal queue: IsEmpty (check if the deque has no elements), Peek (view the front element without removing it), and Size (count the number of elements currently in the deque).
Using a Deque to Check for a Palindrome
The textbook illustrates these operations with a concrete algorithm — checking whether a string is a palindrome (a word that reads the same forwards and backwards, like "madam").
Algorithm 4.1 (from the textbook):
- Start traversing the string (e.g., "madam") from the left side, one character at a time.
- Insert each character into the deque using INSERTREAR (treating the deque like a normal queue for insertion).
- Repeat steps 1 and 2 for all characters of the string. After this, the deque contains the entire string in order from front to rear.
- Remove one character from the front (using DELETIONFRONT) and one character from the rear (using DELETIONREAR).
- Compare these two removed characters.
- If they are the same, repeat steps 4 and 5 until the deque becomes empty or is left with only one character. If all pairs match, the string is a palindrome. If any pair does not match, stop — the string is not a palindrome. …
Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your NCERT textbook's own diagram.
This freezes the deque mid-way through inserting the characters of the word "madam" one at a time using insertrear. After four insertions, the deque holds m, a, d, a — Front still points at the very first character inserted (m), and Rear points at the most recently inserted one (the second a). …
Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your NCERT textbook's own diagram.
Continuing the same "madam" example, this shows the deque after one character has been removed from EACH end — demonstrating that a deque, unlike an ordinary queue, can delete from the front AND the rear.
removefront (m) takes the m off the front of the deque; separately, insertrear (m) places an m at the rear. What remains in between is a, d, a, with Front now pointing at the first a and Rear at the last a. …