Previous Section
 < Free Open Study > 
Next Section


4.1 Stacks

Logical Level

Consider the items pictured in Figure 4.1. Although the objects are all different, each illustrates the same concept-a stack. At the logical level, a stack is an ordered group of homogeneous items or elements. The removal of existing items and the addition of new items can take place only at the top of the stack. For instance, if your favorite blue shirt is underneath a faded, old, red one in a stack of shirts, you must first remove the red shirt (the top item) from the stack. Only then can you remove the desired blue shirt, which is now the top item in the stack. The red shirt may then be replaced on the top of the stack or thrown away.

Click To expand
Figure 4.1: Real-life stacks

Stack An abstract data type in which elements are added and removed from only one end; a "last in, first out" (LIFO) structure

The stack may be considered an "ordered" group of items because elements occur in a particular sequence organized according to how long they've been in the stack. The items that have been present in the stack the longest are at the bottom; the most recent are at the top. At any time, given any two elements in a stack, one is higher than the other. (For instance, the red shirt was higher in the stack than the blue shirt.)

Because items are added and removed only from the top of the stack, the last element to be added is the first to be removed. A handy mnemonic can help you remember this rule of stack behavior: A stack is a LIFO (Last In, First Out) structure.

The accessing protocol for a stack is summarized as follows: Both to retrieve elements and to store new elements, access only the top of the stack.

Operations on Stacks The logical picture of the structure provides only half of the definition of an abstract data type. The other half consists of a set of operations that allows the user to access and manipulate the elements stored in the structure. Given the logical view of a stack, what kinds of operations do we need to use a stack?

The operation that adds an element to the top of a stack is usually called and the operation that removes the top element from the stack is referred to as . Because we may need to examine the item at the top of the stack we can have return the top element or we can use a separate operation to return a copy of the top element without removing it. When we begin using a stack, it should be empty, so we need an operation that sets the stack to empty: . We must also be able to tell whether a stack contains any elements before we pop it, so we need a Boolean operation . As a logical data structure, a stack is never conceptually "full," but for a particular implementation you may need to test whether a stack is full before pushing. We call this Boolean operation . Figure 4.2 shows how a stack, envisioned as a stack of building blocks, is modified by several and operations.

Click To expand
Figure 4.2: The effects of Push and Pop operations

We now have a logical picture of a stack and are almost ready to use it in a program. The part of the program that uses the stack, of course, won't care how the stack is actually implemented-we want the implementation level to be hidden, or encapsulated. The accessing operations such as Push, Pop, and Top serve as windows into the stack encapsulation, through which the stack's data are passed. The interfaces to the accessing operations are described in the following specification for the Stack ADT.

Application Level

Now let's look at an example of how we might use the stack operations in a program. Stacks are very useful ADTs that are often used in situations where we must process nested components.

For example, programming language systems typically use a stack to keep track of operation calls. The main program calls operation A, which in turn calls operation B, which in turn calls operation C. When C finishes, control returns to B; when B finishes, control returns to A; and so on. The call-and-return sequence is essentially a LIFO sequence, so a stack is the perfect structure for tracking it. When an exception is thrown, this sequence of operation calls is followed while looking for an appropriate catch statement.

Compilers often use stacks to perform syntax analysis of language statements. The definition of a programming language usually consists of nested components-for example, for loops can contain if-then statements that contain while loops that contain for loops. As a compiler works through such nested constructs, it "saves" information about what it is currently working on in a stack. When it finishes its work on the innermost construct, the compiler can "retrieve" its previous status from the stack, and pick up where it left off. Similarly, an operating system sometimes saves information about the currently executing process on a stack, so that it can work on a higher-priority interrupting process. If that process becomes interrupted by an even higher-priority process, its information can also be pushed onto the process stack. When the operating system finishes its work on the highest-priority process, it pops the information about the most recently stacked process, and continues working on it.

Let's look at a simpler problem related to nested components-the problem of determining whether a set of parentheses is "well formed." For this classic problem, a stack is an appropriate data structure. The general problem can be stated as follows: Determine whether a set of paired symbols is used appropriately. The specific problem is: Given a set of different types of paired symbols, determine whether the opening and closing versions of each type are paired correctly. For our example, we consider parenthesis pairs (), [], and {}.[1] Any number of other characters may appear in the input, but a closing parenthesis symbol must match the last unmatched opening parenthesis symbol and all parenthesis symbols must be matched when the input is finished. Figure 4.3 shows examples of both well-formed and ill-formed expressions.

Click To expand
Figure 4.3: Well-formed and ill-formed expressions

The program reads an expression character by character. For each character, it does one of three tasks, depending on whether the character is an opening special symbol, a closing special symbol, or not a special symbol. If the character is not a special symbol, it is discarded and another character is read. If the character is an opening special symbol, it is saved on the stack. If the character is a closing special symbol, it must be checked against the last opening special symbol, which is on the top of the stack. If they match, the character and the last opening special symbol are discarded and the program processes the next character. If the closing special symbol does not match the top of the stack or if the stack is empty, then the expression is ill formed. When the program has processed all of the characters, the stack should be empty-otherwise, extra opening special symbols are present.

Now we are ready to write the main algorithm, where stack is an instance of StackType and symbol is the character being examined.

The algorithm follows this basic pattern:

It uses this processing pattern for both the lines of expressions (if there is more than one) and the characters within each line. Your programming proficiency will increase as you recognize such patterns and "reuse" them when appropriate.

The only part of the algorithm that may require expansion before moving on to the coding stage is the "Process symbol" command. Earlier, we described how to handle each type of character. Here are those steps in algorithmic form:

We are now ready to code this algorithm as the program Balanced. We make use of stack of the class StackType. We could code a class SymbolType with member functions IsOpen, IsClosed, and Matches and one data item of type char. However, because a symbol is just a built-in data type, a procedural solution is simpler.

#include "StackType.h"
#include <iostream>
bool IsOpen(char symbol);
bool IsClosed(char symbol);
bool Matches(char symbol, char openSymbol);

int main()
{
  using namespace std;
  char symbol;
  StackType stack;
  bool balanced = true;
  char openSymbol;

  cout << "Enter an expression and press return." << end1;
  cin.get(symbol);
  while (symbol != '\n' && balanced)
  {
    if (IsOpen(symbol))
      stack.Push(symbol);
    else if (IsClosed(symbol))
    {
      if (stack. IsEmpty() )
        balanced = false;
      else
      {
        openSymbol = stack.Top();
        stack.Pop();
        balanced = Matches(symbol, openSymbol);
      }
    }
    cin.get(symbol);
  }
  if (balanced)
    cout << "Expression is well formed." << end1;
  else
    cout << "Expression is not well formed." << end1;
  return 0;
}
bool IsOpen(char symbol)
{
  if ((symbol  = =  '(')  ||  (symbol  = =  '{')  ||  (symbol  = =  '['))
    return true;
  else
    return false;
}

bool IsClosed(char symbol)
{
  if ((symbol  = =  ')')  ||  (symbol  ==  '}') || (symbol  ==  ']'))
    return true;
  else
    return false;
}

bool  Matches(char symbol, char openSymbol)
{
  return   (((openSymbol  = =  '(')  &&  symbol  = =  ')')
        ||  ((openSymbol  = =  '{')  &&  symbol  = =  '}')
        ||  ((openSymbol  = =  '[')  &&  symbol  = =  ']')):
}
Click To expand
Click To expand

In this expression checker, we have acted as stack users. We have written an interesting stack application, without even considering how the stack is implemented. The stack user doesn't need to know the implementation! The details of the implementation remain hidden inside the StackType class. As users, however, we did not adhere to the specifications carefully. We should have included Push, Pop, and Top with a try/catch statement. We leave this correction as an exercise.

Implementation Level

Next, we consider the implementation of our Stack ADT. After all, our functions Push, Pop, and Top are not magically available to the C++ programmer. We need to write these routines to include them in a program.

Because all elements of a stack are of the same type, an array seems like a reasonable structure to hold them. We can put elements into sequential slots in the array, placing the first element pushed into the first array position, the second element pushed into the second array position, and so on. The floating "high-water" mark is the top element in the stack. Why, this approach sounds just like our Unsorted List ADT implementation! Here info [length - 1] is the top of the stack.

Be careful: We are not saying that a stack is an unsorted list. A stack and an unsorted list are two entirely different abstract data types. We are saying, however, that we can use the same implementation strategy for both.

Definition of the Stack Class We implement our Stack ADT as a C++ class. Just as we did for the various versions of the List ADT, we require the user to provide us with a class called ItemType, which defines the items on the stack. However, we do not need a comparison function because none of the operations requires comparing two items on the stack.

Which data members does our Stack ADT need? We need the stack items themselves and a variable indicating the top of the stack (which behaves in the same way as length in the List ADT). What about error conditions? Our specifications leave error checking to the user (client) by having the ADT throw an exception when a push operation is attempted but the stack is full or when a pop or top operation is attempted but the stack is empty. We include two exception classes, FullStack and EmptyStack, in the following specification file, StackType.h.

#include ItemType.h
// ItemType.h must be provided by the user of this class.
// This file must contain the following definitions:
//   MAX_ITEMS:     the maximum number of items on the stack.
//   ItemType:      the definition of the objects on the stack.

class FullStack
// Exception class used by Push when stack is full.
{} ;

class EmptyStack
// Exception class used by Pop and Top when stack is empty.
{}:
class StackType
{
public:
   StackType();
   bool IsEmpty() const;
   bool IsFull() const;
   void Push(ItemType item);
   void Pop();
   ItemType Top() const;
private:
   int top;
   ItemType items[MAX_ITEMS];
};

Definitions of Stack Operations In the List ADT, length indicated how many items were present on the list. In the Stack ADT, top indicates which element is on top. Thus our analogy to the List ADT is off by one. The MakeEmpty operation is implemented with a class constructor that sets top to -1 rather than 0. IsEmpty should compare top with - 1, and IsFull should compare top with MAX_ITEMS - 1.

StackType::StackType()
{
  top = -1;
}

bool StackType::IsEmpty() const
{
  return (top == -1);
)

bool StackType::IsFull() const
{
  return (top == MAX_ITEMS-1) ;
}

Now we must write the algorithm to Push an item on the top of the stack, Pop an item from the top of the stack, and return a copy of the top item. Push must increment top and store the new item into items [top].If the stack is already full when we invoke Push, the resulting condition is called stack overflow. We can handle error checking for overflow conditions in a number of ways. Our specification states that overflow causes an exception to be thrown; thus the client is responsible for handling overflow by enclosing the operation within a try/catch statement. Alternatively, we could pass an error flag as a parameter, which Push sets to true if overflow occurs.

Stack overflow The condition resulting from trying to push an element onto a full stack

void StackType::Push(ItemType newItem)
{
  if (IsFull())
    throw FullStack();
  top++;
  items[top] = newItem;
}

The constructor for the exception class is called in the throw statement, because C++ requires us to throw an object of an exception type. Because the documentation states that the functions Push, Pop, and Top can throw exceptions, calls to them must be enclosed within a try block. The following example shows what the client code might do with the exception:

try
{
  // Code
  stack.Push(item) ;
  stack.Pop();
  // More code
}
catch (FullStack exceptionObject)
{
  cerr << "FullStack exception thrown"  << end1;
}
catch (EmptyStack exceptionObject)
{
  cerr << "EmptyStack exception thrown"  << end1;
}

In this case, the FullStack or EmptyStack object that is thrown is not accessed. If the exception class has member functions, they could be applied to exceptionObject. If the exception is so severe that the program should halt, the exit function can be used.

catch (EmptyStack exceptionObject)
{
  cerr << "EmptyStack exception thrown"  << end1
     << "Exiting with error code 2" << end1;
exit(2);
}
C++: The Error Stream cerr
Start example

You already know about cin and cout, which are defined in the <iostream> header file. A third stream defined in <iostream>, cerr, is called the error output stream. As its name suggests, cerr is intended specifically for error messages.

Use of exit(n)

Calling exit(n), which is available in <cstdlib>, anywhere in a program cleans up and then terminates the program. We cannot use return to terminate a program in any function other than main. Using return in a function returns to the caller, which would not end the program. In main, exit(n) has the same effect as return n.

End example

Pop is essentially the reverse of Push: We decrement top. If the stack is empty when we invoke Pop or Top, a stack underflow results. As with the Push function, the specifications for the operations say to throw an exception in this event.

Here is the code for Pop and Top:

Stack underflow The condition resulting from trying to pop an empty stack

void StackType::Pop()
{
  if(IsEmpty())
    throw EmptyStack();
  top- - ;
}

ItemType StackType::Top() const
{
  if (IsEmpty())
    throw EmptyStack();
  return items[top];
}

Figure 4.4 shows the result of pushing and popping where the stack items are characters.

Click To expand
Figure 4.4: The effect of a Pop following a series of Pushes

Test Plan The test plan for the Stack ADT closely resembles the test plan for the List ADT. Because we are testing the implementation of an abstract data type that we have just written, we use a clear-box strategy, checking each operation. Unlike with the List ADT, however, we do not have an iterator that allows us to cycle through the items and print them. Instead, we must use a combination of calls to Top and Pop to print what is in the stack, destroying it in the process.

Because the type of data stored in the stack has no effect on the operations that manipulate the stack, we can define ItemType to represent int values and set MAX_ITEMS to 5, knowing that the code will work the same way whether MAX_ITEMS is 5 or 1,000.

Operation to Be Tested and Description of Action

Input Values

Expected Output or Program Behavior

Class constructor

   
  • Apply IsEmpty immediately

 

Stack is empty

Push, Pop, and Top

   
  • Push 4 items, top, pop, and print

5, 7, 6, 9

9, 6. 7. 5

  • Push with duplicates and pop, top, and print

2, 3, 3, 4

4. 3, 3, 2

Push, Pop, and Top interlace operations

   
  • Push

5

 
  • Pop

   
  • Push

3

 
  • Push

7

 
  • Pop

   
  • Top and print

 

3

IsEmpty

   
  • Invoke when empty

 

Stack is empty

  • Push and invoke

 

Stack is not empty

  • Pop and invoke

 

Stack is empty

IsFull

   
  • Push 4 items and invoke

1, 2, 3. 4

Stack is not full

  • Push another item and invoke

5

Stack is full

throwFullstack

 

Caught by driver

  • Push 5 items then

1, 2, 3, 4, 5

 
  • Push another item

6

 

throw EmptyStack

 

Caught by driver

  • When stack is empty,

   
  • Attempt to pop

   
  • Attempt to top

   

On the Web, the program StackDr.cpp is the test driver, the input file is StackType. in, and the output files are StackType.out and StackType.screen. Examine StackDr. cpp to see how the try/catch statement is used.

[1]An overzealous copyeditor once changed parenthesized expressions in a Pascal program from plain parentheses to alternating parentheses and square brackets. Fortunately, when all of the programs were tested, this change was caught.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)