Technique: Representation of stacks, queues, and deques

A linear list is a set of N>=0 nodes A.1,A.2,...,A.N. Linear lists in which insertions, deletions, and accesses to nodes occurs at the first or the last node are:

Stack
- A stack is a linear list for which all insertions and deletions are made at one end of the list.

Queue
- A queue is a linear list for which all insertions are made at one end of the list; all deletions are made at the other end.

Deque
- A deque ("double-ended queue") is a linear list for which all insertions and deletions are made at the ends of the list.

EXTERNAL DATA QUEUE

The following very simple routines give a possibility to represent basic type of linear lists:

Stack
by INSERT_ON_RIGHT and DELETE_FROM_RIGHT

Queue
by INSERT_ON_LEFT and DELETE_FROM_RIGHT

Output restricted Deque
by INSERT_ON_RIGHT, INSERT_ON_LEFT,
DELETE_FROM_RIGHT

 INITIALIZE: do while \EMPTY(); pull; end; return   INSERT_ON_RIGHT: push ARG(1); return   INSERT_ON_LEFT: queue ARG(1); return   DELETE_FROM_RIGHT: if EMPTY()   then do     call UNDERFLOW     return ""   end   else do     pull X     return X   end   EMPTY: return QUEUED() = 0   UNDERFLOW: return

ARRAY

The simplest and most natural way to keep a stack inside a computer is to put the list items in an array.

Stack
We can represent it by INSERT_ON_RIGHT and DELETE_FROM RIGHT routines.

 INITIALIZE: procedure expose R R = 0; return   INSERT_ON_RIGHT: procedure expose A. R R = R + 1; A.R = ARG(1) return   DELETE_FROM_RIGHT: procedure expose A. R if EMPTY()   then do     call UNDERFLOW     return ""   end   else do     S = R; R = R - 1     return A.S   end   EMPTY: procedure expose R; return R = 0   UNDERFLOW: return

STRING

When items of a list are words than we can use a string as stack, queue, or deque.

Stack
by INSERT_ON_LEFT and DELETE_FROM_LEFT

Queue
by INSERT_ON_RIGHT and DELETE_FROM_LEFT

Output restricted Deque
by INSERT_ON_RIGHT, INSERT_ON_LEFT,
DELETE_FROM_LEFT

 INITIALIZE: procedure expose A A = ""; return   INSERT_ON_RIGHT: procedure expose A A = A ARG(1); return   INSERT_ON_LEFT: procedure expose A A = ARG(1) A; return   DELETE_FROM_LEFT: procedure expose A if EMPTY()   then do     call UNDERFLOW     return ""   end   else do     parse var A X A     return X   end   EMPTY: procedure expose A return A = ""   UNDERFLOW: return ""

COMPARISON
With the following program I compared the time complexity of the various representations of the stack for K=1 and K=10000, where K is the number of chars in stack's element.

 Seed = RANDOM(,,481989); K = 10000 String = COPIES("*", K) call TIME "R" call INITIALIZE do 1000000   Rnd = RANDOM(1)   if Rnd = 0 then call INSERT_ON_LEFT String              else X = DELETE_FROM_LEFT() end say TIME("R") seconds exit ...

The results are included into the following table

Time complexity in seconds
Representation K = 1 K = 10000
External Data Queue 37.96 464.78
Array 67.39 241.51
String 59.32 ?*)

*) I halted the computation after 3600 seconds.

CONNECTIONS
Topological sorting - using various representations of a queue.
QUICKSORT and Recursion elimination - using a stack.

Literature
Knuth D. E., Fundamental Algorithms, vol. 1 of The Art of Computer Programming