Part Ⅲ Elementary Data Structure

Stacks

last-in, first-out (LIFO)

insertion operation: Push
deletion operation:Pop

If an empty stack is popped, then stack underflows
If top［S ］ exceeds n, then stack overflows.

Pseudo code of stack empty

 STACK -EMPTY
if  top[S]＝0
 then  return  ture
else  return  false

 PUSH(S, x)
  top[S]←top [S ]+1
  S[top[S]]←x

Pop(S)
if STACK-EMPTY(S)
   then error "underflows"
else top[S] ←top[S]－1
   return S[top[S]+1]

Each of the three stack operations takes Ο（1） tim.

Queue
First in, first out( FIFO)

Enqueue (Q, x )

Q[tail[Q]]←x
if tail[Q]=length[Q]
   then tail[Q]←1
  else tail[Q]←tail[Q]+1

Dequeue(Q)

x←Q[head[Q]]
if head[Q]=length [Q]
   then head[Q]=1
else head[Q]←head[Q]+1
   return x

Inserting into a linked list

LIST -Insert (L, x)
next [x ]←head [L]
if head [L]≠NIL 
then prev [head [L ]]←x 
head [L]←x 
prev [x]←NIL