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 ("doubleended 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
Literature
Knuth D. E.,
Fundamental Algorithms, vol. 1 of The Art of Computer Programming  2nd ed. AddisonWesley, 1973