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


cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail