Lab 15: Experiment 1

Working with a stack

The Problem

You've now had several labs to write a variety of programs, often with a variety of code provided to you. For this last lab, you'll write all of the code.

Here's the problem: what happens if we read in a bunch of words, push them all onto a stack, and then, as we pop them off, display them?

The Prediction

So what will happen to the words when they're printed out? Try this out on paper first:

Question #15.1.1: Suppose the words in the sentence "Madam, I'm Adam." were pushed one after the other onto the same stack, and then they were printed as they were popped off. What would be printed?

Now, granted, this is only one example, but perhaps it's enough to make a prediction:

Question #15.1.2: What will the (eventual) program do in general to any sequence of words?


The behavior is quite simple:

The program will create a new empty stack. The program will prompt for and read in a file name from the keyboard, and then it will open that file for input. For each word read in, push it onto the stack. When the end-of-file is reached, the file is closed. Then words are popped off the stack until the stack is empty, and each word that is popped off is printed to the screen.

You can use an output file if you like. We're not really interested in solving this precise problem since it's a little silly. We're really interested in what the stack will do in this situation.

The objects are straightforward:
Description Type Kind Name
the stack of words stack<string> varying theStack
the file name string varying inFileName
the keyboard istream varying cin
the input stream ifstream varying inStream
a word string varying word
the screen ostream varying cout

The operations are fairly straightforward as well. The following list omits the file operations, but you can look them up from previous labs.

Description Predefined? Name Library
create a new stack yes stack() constructor stack
push a word onto the stack yes push() stack
test if stack is empty yes empty() stack
get top value from stack yes top() stack
pop top value from stack yes pop() stack

Declaring a stack is just like declaring a vector or list. Use the exact same syntax, substituting in "stack" appropriately. All of the other operations here will be methods invoked on theStack.

So we end up with this algorithm:

  1. Create a new, empty stack theStack.
  2. Display a prompt for the program.
  3. Read in inFileName.
  4. Open inStream (using inFileName), and test that it opened properly.
  5. Loop:
    1. Read in word from inStream.
    2. If inStream is at the end-of-file, terminate the loop.
    3. Push word onto theStack.
  6. Close inStream.
  7. While theStack is not empty:
    1. Display the top of theStack on the screen (followed by some whitespace).
    2. Pop the top value from theStack.

Write the program, compile it, and run it.

The Analysis

Compare your prediction with the actual outcome.

Question #15.1.3: How closely did your prediction match the actual outcome?

A stack is sometimes known as a LIFO container---Last In, First Out. The first item you push onto a stack will be the last one out.

Question #15.1.4: How does LIFO explain the behavior you see from your program?


Back to the Lab Exercise  |  Forward to the Next Experiment
© 2003 by Prentice Hall. All rights reserved.
Report all errors to Jeremy D. Frens.