Section 1 - Stack Data Structures

Introduction to Week Nine

We have used arrays outside of classes used to sort numbers.  We even replaced numbers with a Student class and watched arrays sort those objects.  Finally, we saw an array appear inside a class where it was used to store the frequency of a given letter as it occurred in a String.

An array is an example of something computer scientists call a data structure, and sorting is an example of something those same practitioners call an algorithm.

This lesson, we will introduce another common kind of data structure, a stack.  Then, we will talk about a new algorithm called a linear search. In the second lesson of the week, we'll investigate how to make the search more efficient by introducing a refined algorithm, the binary search.

Reading

As usual, first study this module completely. Then, if you want more, look up the relevant topics in your text.

9A.1.1 An Array-Based Stack

A stack satisfies these rules:

• It stores data for us; if we have a stack object, say s, then when we want s to store a String, say "hotdog", we push it onto the stack with a call: s.push("hotdog"). "hotdog" is then placed into the stack s and then joins the other items that were on the stack.
• Whenever we go to retrieve data (called popping) from the stack, the item we get will always be the most recent item that we pushed. So if we call s.pop() right after the above push, the item returned by the pop() method would be "hotdog". This also has the effect of removing "hotdog" from the stack, so it is no longer there.

Notice that in the last paragraph, we said "the item returned by pop()."  That means pop() returns a value to the client - it does not make an independent decision to, say, print the popped item to the screen. 

An exception for our purposes is that pop() could output a console error message if the stack were empty. However, this is not ideal, and eventually we will use a technique called exceptions to do this. For now, we allow console error messages to be output from certain methods.

Let's say that we have defined a Stack class, and we have instantiated a Stack object, s.  Then, using s, if we push three times:

s.push("four");
s.push("nine");
s.push("two");

Then the Stack s looks like this:

top ->
"two"
"nine"
"four"

If you then pop() once, the "two" is returned from the stack and it will then contain:

top ->
"nine"
"four"

If you push() another item:

s.push("7.3");

the stack becomes:

top ->
"7.3"
"nine"
"four"

If you pop() now, the "7.3" will be returned and if you pop() immediately after that, the "nine" will be returned, leaving only the "four" on the stack. I think you get the idea.

Since s is an object of class Stack, we should be able to instantiate more than one Stack at a time, say s1 and s2, and push() and pop() from them independently. 

9A.1.2 A Stack Example

This example defines the Stack class using techniques we have already learned, and mixes up the pushing and popping of the two stacks.  You'll have to compare the output to the source code carefully so you can associate the pops with the output that results.  Also, there are a couple interesting comments and questions in the source code itself.

#include <iostream>
#include <string>
using namespace std;

// ---------- Class MyStack Prototype -----------
class MyStack
{
private:
static const int SIZE = 10;
string stck[SIZE];
int tos;

public:
MyStack();
bool push( string item );
string pop();
}; // end of  MyStack prototype -----------------

// main method (client) -------------------------
int main()
{
MyStack s1, s2;
int k;

// Test the Stack -----
cout << s1.pop();

s1.push( "money" );
s1.push( "in" );
s1.push( "the" );
s2.push( "bank" );
s1.push( "a penny saved is" );
s1.push( "123456789.123456789" );

s2.push( "a penny earned" );
s2.push( "2" );
s1.push( "3" );
s2.push( "4" );

cout << "\n--------- First Stack ---------\n";
for (k=0; k<8; k++)
cout << s1.pop() << " : ";
cout << endl;

cout << "\n--------- Second Stack ---------\n";
for (k=0; k<8; k++)
cout << s2.pop() + " : "; // why can we use + here?
cout << endl << endl;

return 0;
}
// end of client -------------------------------------

// ----------- Class MyStack Definitions ------------
MyStack::MyStack()
{
tos = 0;
}

// ---------------------------------------------------
// since you can assign a literal to a string variable,
// you can also pass a literal argument to a method that takes
// a string formal parameter
bool MyStack::push( string item )
{
if (tos == SIZE)
return false;
stck[tos++] = item;
return true;
}

// ---------------------------------------------------
string MyStack::pop()
{
if (tos==0)
return string("Stack Empty");  // anonymous object

return stck[--tos];
}
// end of  MyStack definitions -------------------------

And the output:

You should easily be able to make the following improvements to this example:

• Allow the client to specify the size of the stack in an overloaded constructor (unless that size is larger than SIZE).
• Use the return bool of push() in the client to report a full stack.
• Add a method that could be called init(), whose job would be to reset the stack object, effectively removing all existing items on the stack, preparing it for a fresh reuse.