9.1 The Stack ADT

A stack is used to store data such that the last item inserted is the first item removed. It is used to implement a last-in first-out (LIFO) type protocol. The stack is a linear data structure in which new items are added, or existing items are removed from the same end, commonly referred to as the top of the stack. The opposite end is known as the base. Consider the example in Figure 9.1.1, which illustrates new values being added to the top of the stack and one value being removed from the top.

Figure 9.1.1: Abstract view of a stack: (a) pushing value 19; (b) pushing value 5; (c) resulting stack after 19 and 5 are added; and (d) popping top value.

The Stack ADT

A stack is a data structure that stores a linear collection of items with access limited to a last-in first-out order. Adding and removing items is restricted to one end known as the top of the stack. An empty stack is one containing no items.

Stack()

Creates a new empty stack.
isEmpty()

Returns a boolean value indicating if the stack is empty. </item.

<item opx=length> Returns the number of items in the stack.
pop()

Removes and returns the top item of the stack, if the stack is not empty. Items cannot be popped from an empty stack. The next item on the stack becomes the new top item.
peek()

Returns a reference to the item on top of a non-empty stack without removing it. Peeking, which cannot be done on an empty stack, does not modify the stack contents.
push(item)

Adds the given item to the top of the stack.

To illustrate a simple use of the Stack ADT, we apply it to the problem of reversing a list of integer values. The values will be extracted from the user until a negative value is entered, which flags the end of the collection. The values will then be printed in reverse order from how they were entered. We could use a simple list for this problem, but a stack is ideal since the values can be pushed onto the stack as they are entered and then popped one at a time to print them in reverse order. A solution for this problem follows.

PROMPT = "Enter an int value (<0 to end):"

myStack = Stack()

value = int(input( PROMPT ))

while value >= 0 :

  myStack.push( value )

  value = int(input( PROMPT ))

while not myStack.isEmpty() :

  value = myStack.pop()

  print( value )

Suppose the user enters the following values, one at a time:

 7  13  45  19  28  -1

When the outer while loop terminates after the negative value is extracted, the contents of the stack will be as illustrated in Figure 9.1.2. Notice the last value entered is at the top and the first is at the base. If we pop the values from the stack, they will be removed in the reverse order from which they were pushed onto the stack, producing a reverse ordering.

Figure 9.1.2: Resulting stack after executing the sample application.

Chapter 9. Stacks

9.2 Implementing the Stack