A deque, also known as a double-ended queue, is an ordered collection of items that allows the addition or removal of elements from either end of the queue. Deques are a generalization of stacks and queues and are often implemented as a doubly-linked list.
Deques support the following operations:
push(x)
: Adds an item x to the back of the deque.pop()
: Removes and returns the item at the back of the deque.unshift(x)
: Adds an item x to the front of the deque.shift()
: Removes and returns the item at the front of the deque.In JavaScript, we can implement a deque using an array:
function Deque() {
this.dataStore = [];
this.push = push;
this.pop = pop;
this.unshift = unshift;
this.shift = shift;
}
function push(element) {
this.dataStore.push(element);
}
function pop() {
return this.dataStore.pop();
}
function unshift(element) {
this.dataStore.unshift(element);
}
function shift() {
return this.dataStore.shift();
}
We can use a deque to implement a queue, where the unshift()
and shift()
operations are used:
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
}
function enqueue(element) {
this.dataStore.unshift(element);
}
function dequeue() {
return this.dataStore.shift();
}
We can also use a deque to implement a stack, where the push()
and pop()
operations are used:
function Stack() {
this.dataStore = [];
this.push = push;
this.pop = pop;
}
function push(element) {
this.dataStore.push(element);
}
function pop() {
return this.dataStore.pop();
}
Implement a queue using a deque.
Implement a stack using a deque.
Implement a palindrome checker using a deque.