Deque

From Esolang
Jump to navigation Jump to search

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: