Lab 8 - part 4

Lab 8 - part 4 - Stacks

A stack is a data structure that retrieves items in the reverse of the order in which they are stored. Suppose you have placed letters 'A', 'B', and 'C' in a stack. When you take these letters out of the stack, they will be removed in the order 'C', then 'B', and at last 'A'. A good example of stack is the container that usually keeps three tennis balls. The first ball can be retrieved from the container was the last to be placed into the container. The ball at the bottom of the container was the first to be placed into the container. So, the one that was pushed last will pop first. This structure is also referred to as "LIFO" = "Last In, First Out".

There are two main operations associated with stacks; 1) putting things on the stack which is referred to as push, and 2) taking things from the stack which is referred to as pop. We can create a stack using linked lists if we allow nodes to be added or removed only at the top of the list. One use of a stack is when you want to write a word backward. In that case, you will read the letters of the word one-by-one and as you read them will push them onto a stack. Once all letters are pushed onto the stack, then pop them back one-by-one. This will produce the letters of the word in reverse order.

Exercise 15.4
Use the previous two programs, to write a new program that implements a stack. Your program will ask users to input a word letter-by-letter and then displays the word backward. Please note that you are working with letters to build the stack, thus when you read the word, you will push the letters onto the stack and when you write them, you will pop those letters one-by-one.

Please note that a very detailed version of this program is shown in Display 15.13 of the text book. In that program a stack class is used for this purpose.

Back to part 3