Previous Section
 < Free Open Study > 
Next Section


5.1 Implementing a Stack as a Linked Structure

Let's see how we might use the concept of dynamic storage allocation to implement the class StackType.

The Function Push

We can modify the function Push to allocate space for each new element dynamically.

Implementing the first part of this operation is simple. We use the built-in C++ operator new to allocate space dynamically:

// Allocate space for new item.
itemPtr = new ItemType;

The new operator allocates a block of memory large enough to hold a value of type ItemType (the type of data contained in the stack) and returns the block's address, which is copied into the variable itemPtr. Let's say for the moment that itemPtr has been declared to be of type ItemType*. Now we can use the dereference operator (*) to put newItem into the space that was allocated: *itemPtr = newItem. The situation at this point is pictured in Figure 5.1, with newItem being 'E'.

Click To expand
Figure 5.1: Putting new element into the allocated space

The third part of the Push operation is to "put the allocated space into the stack." How do we complete this task? Think for a minute about what happens after we have pushed a few characters. Space is allocated for each new element, and each character is put into the space. Figure 5.2 shows the results of calling Push to add the characters 'D', 'A', 'L', and 'E' 7to the stack.

Click To expand
Figure 5.2: After four calls to Push

Whoops-we see our data in the dynamically allocated space, but it's not a stack! There's no order. Even worse, because we haven't returned the pointers to the dynamically allocated space from the function Push, we can no longer access any of the elements. Clearly, the third part of the Push operation needs to do something to fix this situation. Where can we store the pointers to our data?

One possibility is to declare the stack as an array of pointers and to put the pointer to each new item into this array, as shown in Figure 5.3. This solution would keep track of the pointers to all elements in the correct order, but it wouldn't solve our original problem: We still need to declare an array of a particular size. Where else could we put the pointers? It would be nice if we could just chain the elements together somehow, as shown in Figure 5.4. We call each element in this "linked" stack a node.

Click To expand
Figure 5.3: One way to keep track of the pointers
Click To expand
Figure 5.4: Chaining the stack elements together

This solution looks promising. Let's see how we might use this idea to implement the stack. First, we push the character 'D'. Push uses the operator new to allocate space for the new node and puts 'D' into the space. Now the stack contains one element. We don't want to lose the pointer to this element, so we need a data member in our stack class in which to store the pointer to the top of the stack (topPtr). Figure 5.5 illustrates the first Push operation.

Click To expand
Figure 5.5: Pushing the first element

Next, we call Push to add the character 'A' to the stack. Push applies new to allocate space for the new element and puts 'A' into the space. Now we want to chain 'A' to 'D', the existing stack element. We can establish a link between the two elements by letting one element "point" to the next; that is, we can store into each stack element the address of the next element. To do so, we need to modify the stack node type. Let's make each node in the stack contain two parts: info and next. The info member contains the stack user's data-a character, for instance. The next member contains the address of the next element in the stack. Figure 5.6 pictures a single node.

Click To expand
Figure 5.6: A single node

As you can see in the figure, the next member of each node points to the next node in the stack. What about the next member of the last node? We cannot leave it unassigned. The next member of the last node in the stack must contain some special value that is not a valid address. NULL, a special pointer constant available in <cstddef>, says, "This pointer doesn't point to anything." We can put NULL in the next member of the last node, thereby marking the end of the stack. Graphically, we use a slash across the next member to represent a NULL pointer.

In fact, in Chapter 3 we introduced a list design terminology that incorporated the abstraction of a node. Let's review this terminology that allows us to refer to the parts of a node in our algorithms (see Figure 5.7).

Click To expand
Figure 5.7: Node terminology

Node(location) refers to all the data at location, including implementation-specific data.

Info(location) refers to the user's data at location.

Info(last) refers to the user's data at the last location in the list.

Next(location) gives the location of the node following Node(location).

Click To expand
Figure 5.8: The second Push operation

In the array-based implementation, location is an index; in our pointer-based implementation, it must be a pointer to a record that contains both the user's information and a pointer to the next node on the stack.

Now let's return to our Push algorithm. We have allocated a node to contain the new element 'A' using the operator new (Figure 5.8a). Let's revert to our design terminology, and call the pointer location.

The new value 'A' is put into the node (Figure 5.8b):

Now we are ready to link the new node to the stack. Where should we link it? Should the new node come before or after the node containing 'D'? To answer that question, consider how the stack is accessed: We add elements to the top (Push) and remove elements from the top (Pop). Last in, first out. Therefore, it would be a good idea to have the new node come first, so that we can access it directly. Linking the new node to the (previous) top node in the stack is a two-step process:

Note that the order of these tasks is critical. If we changed the topPtr pointer before making Next(location) point to the top of the stack, we would lose access to the stack nodes! (See Figure 5.9.) This situation is generally true when dealing with a linked structure: You must be very careful to change the pointers in the correct order, so that you do not lose access to any of the data.

Click To expand
Figure 5.9: Be careful when you change pointers

Before we code this algorithm, let's see how we declare the stack data. From the stack user's point of view, nothing has changed; the prototype for member function Push is the same as it was for the array-based implementation.

void Push(ItemType newItem);

ItemType is still the type of data that the user wants to put in the stack. The class StackType, however, needs new definitions. It no longer is a class with a top member and an array member to hold the items; instead, its only member is topPtr, the pointer to a single node at the top of the stack. The node to which topPtr points has two parts, info and next, which suggests a C++ struct or class representation. We choose to make NodeType a struct rather than a class, because the nodes in the structure are passive. That is, they are acted upon by the member functions of StackType.

To concentrate on the manipulation of the class objects, we implement the stack as a stack of char, rather than making it a template class, by inserting a typedef statement.

// Header file for Stack ADT.
typedef char ItemType;
struct NodeType;

class StackType
{
public:
  StackType();
  ~StackType();
  void Push(ItemType) const;
  void Pop();
  ItemType Top();
  bool IsEmpty() const;
  bool IsFull() const;
private:
  NodeType* topPtr;
};

NodeType will be a struct containing the user's data as well as a pointer to the next node. We alert the compiler that we plan to use a pointer to NodeType data before we have defined NodeType by using the statement

struct NodeType;

This statement, called a forward declaration, is analogous to a function prototype: The compiler is told the nature of an identifier before the identifier is fully defined. The definition of NodeType (shown below) comes later in either the header file or the implementation file.

struct NodeType
{
  ItemType info;
  NodeType* next;
};

To summarize, StackType is a class with only one data member, a pointer to the top node in the stack. We omit the parameterized constructor that allowed the client to specify a maximum stack size. With our dynamically allocated linked structure, no specific limit applies to the size of the stack.

Now let's code the Push algorithm. We use a local variable, location, of type NodeType*. The first two tasks are simple:

Click To expand
Figure 5.10: Pointer dereferencing and member selection
// Allocate space for new item.
location = new NodeType;

// Put new item into the allocated space.
location->info = newItem;

Here location is a pointer to a node containing an info member and a next member. We reference this node with *location, a struct with two members. Because *location is a struct, we can access its members in the usual way-by adding a period, followed by the desired member name. Thus (*location) .info refers to the info member of the struct on the free store pointed to by location. The parentheses are necessary because the dot operator has higher precedence than the dereferencing operator (*). As we said in Chapter 4, C++ provides the -> operator, which both dereferences the pointer and accesses a member. In other words, the expression (*location). info is equivalent to location->info. The dark shaded area in Figure 5.10(a) corresponds to location, the dark shaded area in (b) corresponds to *location, and the dark shaded area in (c) corresponds to location ->info.

Because location->info is the same type as the user's data, we can assign newItem to it. So far, so good.

Now for the linking task:

Next(location) is the next member of the node pointed to by location. We can access it just as we accessed the info member: location->next. What can we put into this field? It is declared as a pointer, so we can assign another value of the same pointer type to it. We want to make this member point to the stack's top node. Because we have a pointer to the stack's top node (topPtr), this assignment is simple:

location->next = topPtr;

Finally, we need to complete the linking by making topPtr point to the new node. Because topPtr is declared as a pointer, we can assign another value of the same pointer type to it. Because we have a pointer to the new node (the local variable location), this assignment can be made:

topPtr = location;

Here is the complete function Push:

void StackType::Push(ItemType newItem)
// Adds newItem to the top of the stack.
// Pre:  Stack has been initialized.
// Post: If stack is full, FullStack exception is thrown;
//       else, newItem is at the top of the stack.

{
  if (IsFull())
    throw FullStack();
  else
  {
    NodeType* location;
    location = new NodeType;
    location->info = newItem;
    location->next = topPtr;
    topPtr = location;
  }
}

You have seen how this code works on a stack that contains at least one value. What happens if we call this function when the stack is empty? Space is allocated for the new element and the element is put into the space (Figure 5.11a). Does the function correctly link the new node to the top of an empty stack? Let's see. The next member of the new node is assigned the value of topPtr. What is this value when the stack is empty? It is NULL, which is exactly what we want to put into the next member of the last node of a linked stack (Figure 5.11b). Then topPtr is reset to point to the new node (Figure 5.11c). Thus this function works for an empty stack as well as a stack that contains at least one element.

The coded version of the function Push uses pointer-variable terminology where our algorithm used our special node terminology. Table 5.1 summarizes the relationship between the design and code terminology.

Table 5.1: Comparing Node Design Notation to C++ Code

Design Notation

C++ Code

Node(location)

*location

Info(location)

location -> info

Next(location)

location -> next

Set location to Next(location)

location = location->next

Set Info(location) to value

location->info = value

Click To expand
Figure 5.11: Pushing onto an empty stack

The Function Pop

Now let's look at the Pop operation. The algorithm for Pop follows:

Let's try out this algorithm on the stack depicted in Figure 5.12. How do we "unlink" the top node from the stack? If we reset topPtr to point to the node following the top node, the resulting stack should be correct. Now we can free the space occupied by the old top node by using the C++ delete operation.

Click To expand
Figure 5.12: Popping the top element

Whoops! The problem with this algorithm is that it leaves the former top node inaccessible-we no longer have a pointer to this node. Without a pointer, we cannot use the delete operation to free the space. When we code the function, let's add a local pointer variable to save the address of this node before we reset topPtr.

void StackType::Pop()
// Removes top item from stack
// Pre:  Stack has been initialized.
// Post: If stack is empty, EmptyStack exception is thrown;
//       else, top element has been removed.
{
  if (IsEmpty())
    throw EmptyStack();
  else
  {
    NodeType* tempPtr;
    tempPtr = topPtr;
    topPtr = topPtr->next;
    delete tempPtr;
  }
}

Let's walk through this function, using the stack depicted in Figure 5.13. We save a pointer to the first node, so that we can access it later to delete it (Figure 5.13a). Then the external pointer to the stack is advanced to jump over the first node, making the second node become the new top item. How do we know the address of the second node? We get it from the next member of the first node (topPtr->next). This value is assigned to topPtr to complete the unlinking task (Figure 5.13b). Finally, we free the space occupied by the old top node by using the delete operator, giving it the address we saved in tempPtr (Figure 5.13c).

Click To expand
Figure 5.13: Popping the stack

Does this function work if the stack contains only one node when Pop is called? Let's see. We unlink the first/last node from the stack. We save a pointer to the node, as before, and then try to assign topPtr->next to topPtr (Figure 5.14). What is the value of topPtr->next? Because it is the last node in the list, its next member should contain NULL. This value is assigned to topPtr, which is exactly what we want, because a NULL stack pointer means that the stack is empty. Thus the function works for a stack containing only one element.

Click To expand
Figure 5.14: Popping the last element on the stack

What happens if Pop does not check for the empty stack? If topPtr contains NULL, then the assignment statement

topPtr = topPtr->next;

results in a run-time error. On some systems, you get the message ATTEMPT TO DEREFERENCE NULL POINTER; on other systems, the screen freezes. This result cannot occur, however, because our code does check for the empty stack before continuing with the operation.

The Function Top

A glance at any of the previous figures shows that the information in the top of the stack appears in the info member of the first node.

ItemType StackType::Top() const
// Returns a copy of the top item in the stack.
// Pre:  Stack has been initialized.
// Post: If stack is empty. EmptyStack exception is thrown;
//       else, a copy of the top element is returned.
{
  if (IsEmpty())
    throw EmptyStack();
  else
    return topPtr->info;
}

Other Stack Functions

In the explanation of pushing the first element, we noted that an empty stack is indicated by a NULL pointer. This fact has implications for other stack operations. To initialize a stack to the empty state, we merely need to set topPtr to NULL.

StackType::StackType()     // Class constructor.
{
  topPtr = NULL;
}

That was simple; and the function IsEmpty is correspondingly simple. If we initialize an empty stack by setting topPtr to NULL, then we can detect an empty stack by checking for a NULL pointer.

bool StackType::IsEmpty() const
// Returns true if there are no elements on the stack and false otherwise.
{
  return (topPtr == NULL);
}

What about the function IsFull? Using dynamically allocated nodes rather than an array, we no longer have an explicit limit on the stack size. We can continue to get more nodes until we run out of memory on the free store. The ISO/ANSI C++ Standard dictates that the new operator in C++ throw a bad_alloc exception when there is no more space to allocate. The bad_alloc exception is defined in the <new> header. This exception needs to be handled because an unhandled exception carries a death sentence for the program.

bool StackType::IsFull() const
// Returns true if there is no room for another NodeType object
//  on the free store and false otherwise.
(
  NodeType* location;
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

Our class definition also provides a class destructor. Do we need one? Yes, we do. If the stack is a local variable, the space for the data member topPtr is deallocated when the stack goes out of scope, but the nodes to which topPtr points do not. The class destructor must loop through the stack, returning the nodes to the free store with the delete operator. How do we know when there are "more nodes in the stack"? As long as topPtr is not NULL, the stack is not empty. Thus the resulting condition on the loop is while(topPtr != NULL).

StackType::~StackType()
// Post: Stack is empty; all items have been deallocated.
{
   NodeType* tempPtr;

   while (topPtr != NULL)
   {
     tempPtr = topPtr;
     topPtr = topPtr->next;
     delete tempPtr;
   }
}

We can test the linked implementation of the Stack ADT by using the same test plan that we wrote for the array-based version. The test driver and files have the same names as those in Chapter 4.

Comparing Stack Implementations

We have looked at three different implementations of the Stack ADT. The first two were similar in that they used an array to store the items; one used a static array and one used a dynamically allocated array. The third implementation is very different, in that it uses dynamic allocation for each item in the stack. We can compare these implementations in terms of storage requirements and efficiency of the algorithms. An array variable of the maximum stack size takes the same amount of memory, no matter how many array slots are actually occupied; we need to reserve space for the maximum number of slots possible. This is true no matter how we allocate space for the array. The linked implementation using dynamically allocated storage requires space only for the number of elements actually on the stack at run time. Note, however, that the elements are larger because we must store the link as well as the user's data.

We can compare the relative "efficiency" of the three implementations in terms of Big-O notation. In all three implementations, the class constructor, IsFull, and IsEmpty clearly have O(1) complexity. They always take a constant amount of work. What about Push, Top, and Pop? Does the number of elements in the stack affect the amount of work done by these operations? No, it does not. In all three implementations, we directly access the top of the stack, so these operations also take a constant amount of work. They, too, have O(1) complexity.

The class destructors do differ from one implementation to the other. The array-based implementation in static storage does not need a destructor, whereas the array-based implementation in dynamic storage does need one. The destructor for the dynamically allocated array returns a single block of storage; the size of the block of cells does not change the amount of work. The complexity is, therefore, O(1). The linked implementation must process every node in the stack to free the node space. This operation, therefore, has O(N) complexity, where N is the number of nodes in the stack.

Overall, the three stack implementations are roughly equivalent in terms of the amount of work they do, differing in only one of the five operations and the class destructor. Note that if the difference had occurred in the Push, Top, or Pop operation, rather than the less frequently called destructor, it would be more significant. Table 5.2 summarizes the Big-O comparison of the stack operations. The operation that differs between the three implementations appears in boldface in the table.

Table 5.2: Big-O Comparison of Stack Operations
 

Static Array Implementation

Dynamic Array Implementation

Linked Implementation

Class constructor

O(1)

O(1)

O(1)

IsFull

O(1)

O(1)

O(1)

IsEmpty

O(1)

O(1)

O(1)

Push

O(1)

O(1)

O(1)

Pop

O(1)

O(1)

O(1)

Top

O(1)

O(1)

O(1)

Destructor

NA

O(1)

O(N)

So which approach is better? The answer, as usual, is: It depends. The linked implementation certainly gives more flexibility, and in applications where the number of stack items can vary greatly, it wastes less space when the stack is small. In situations where the stack size is totally unpredictable, the linked implementation is preferable, because size is largely irrelevant. Why, then, would we ever want to use an array-based implementation? Because it is short, simple, and efficient. If pushing and popping occur frequently, the array-based implementation executes more quickly because it does not incur the run-time overhead of the new and delete operations. When maxStack (MAX_ITEMS in the ADT specification) is small and we never need to exceed the declared stack size, the array-based implementation is a good choice. Also, if you are programming in a language that does not support dynamic storage allocation, an array implementation may be the only good choice.



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