Deque

A deque (a double-ended queue) is a data structure that can behave both like a queue and a stack. It allows data to be pushed to either the front or the back, and data to be popped from either the front or the back of the list. 'Deque' is often pronounced "deck".

This data structure can also be considered identical to a tape loop that can be expanded and contracted. The differences may become significant if the operations on the tape-loop (or deque) are specifically limited in some way.

Operations

There are a few basic Deque operations:

Name	Function
INJECT	Insert element at back of deque (equivalent to the queue's enqueue)
PUSH	Insert element at front of deque
POP	Remove element from front of queue and return
EJECT	Remove element from back of queue

These operations, together with a few (about three max) scalar variables form the additional operations for deques.

Additional Operations

In addition to INJECT, PUSH, POP, and EJECT, there are a few other deque manipulation operations, which include both the stack and queue operations, that deques can use that are generally accomplished through scalar variables.

The following table lists them, including the operation, its name, its traditional (or completely made up) laconic representation, its meaning, and an example in "Generic Deque Language" (GDQL), a language used solely for example purposes.

Stack Operations
Op	Laconic	Name	Meaning	GDQL
PEEK	N/A	Peek	Return the top of the stack without removing it.	POP→a; PUSH a; RETURN a;
DROP	$	Drop	Remove the top item of the stack and discard it	POP;
DUP	:	Duplicate	Duplicate the value on the top of the stack.	PEEK→a; PUSH a;
SWAP	\	Swap	Swap the positions of the top two values on the stack.	POP→a; POP→b; PUSH a; PUSH b;
OVER	^	Over	Put the second item on the stack on the top of the stack WITHOUT removing it from its original location.	SWAP; DUP; ROT;
ROT	[	Rotate	Rotate the top three items on the stack clockwise.	POP→a; POP→b; POP→c; PUSH a; PUSH c; PUSH b;
ROTCC	]	Rotate Counterclockwise (anticlockwise)	Rotate the top three items on the stack counterclockwise.	POP→a; POP→b; POP→c; PUSH b; PUSH a; PUSH c;
Queue Operations
Op	Laconic	Name	Meaning	GDQL
ROLL	N/A	Roll	Move the value from the front of the queue to the back	DEQUEUE→a; ENQUEUE a;
Deque-Specific Operations
Op	Laconic	Name	Meaning	GDQL
BACKPEEK	???	Peek at back	View the item at the left of the deque without removing it	EJECT;
REVROLL	N/A	Reverse Roll	Eject a value then push it.	EJECT→a; PUSH a;
PUD	N/A	Reverse Duplicate	Duplicate the value at the right of the deque.	EJECT→a; INJECT a; INJECT a;
BACKSWAP	N/A	Reverse Swap	Swap the two values at the left of the queue	EJECT→a; EJECT→b; INJECT a; INJECT b
UNDER	N/A	UNDER	Put the second item on the stack on the top of the stack WITHOUT removing it from its original location.	BACKSWAP; PUD; BACKROT;
BACKROT	N/A	Rotate Back	Rotate the three items at the let of the queue clockwise.	EJECT→a; EJECT→b; EJECT→c; INJECT a; INJECT c; INJECT b;
BACKROTCC	N/A	Rotate Back Counterclockwise (anticlockwise)	Rotate the top three items on the stack counterclockwise.	EJECT→a; EJECT→b; EJECT→c; INJECT b; INJECT a; INJECT c;
PORD	???	Pord or Reverse Drop	Remove an item from the back of the deque	EJECT;
PAD	???	Pad	Peek at the item in the front of the deque and duplicate it to the back	PEEK→a; INJECT a;
REVPAD	???	Reverse Pad	Peek at the item at the back of the deque and duplicate it to the front	EJECT→a; PUSH a;

Esoteric Implementations

Here is the list of esoteric programming languages that use a deque as a central data structure:

• Category:Deque-based