Technique: Representation of stacks, queues, and deques

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
- 2nd ed. Addison-Wesley, 1973