Stacks

After studying this section you should be able to:

explain the concept of a stack
describe methods of representing a stack
describe the algorithms used to manipulate a stack

Implementing stacks

A stack can be implemented as a linked list or an array. In the case of a linked list, a new item is added to the front of the list and Pop takes an item from the front of the list. An array implementation will have an array plus a variable to record the top of the stack

There will be another variable to indicate the maximum number of items that can be stored in the stack (say MaxItems). The procedure to add an item to the stack (Push) might be:

PROCEDURE Push(inItem)

     IF TopOfStack = MaxItems

          THEN Output "Stack is Full"

     ELSE

          Add 1 to TopOfStack

          Stack[TopOfStack] := inItem

     ENDIF

ENDPROC

To remove an item (Pop):

PROCEDURE Pop(outItem)/* outItem must be passed by reference */

     IF TopOfStack = 0

          THEN Output "Stack is empty"

     ELSE

          outItem := Stack[TopOfStack]

          Subtract 1 from TopOfStack

     ENDIF

ENDPROC

Log in