The StackLinkedList Class


An efficient programmer does not repeat code if possible and instead inherits attributes and behaviors of another class, defining a LinkedList class to create and manipulate a linked list. An efficient programmer might also define a StackLinkedList class to create and manipulate a stack-linked list. The StackLinkedList class inherits attributes and behaviors of the LinkedList class and then defines other behaviors that are necessary to work with a stack-linked list.

In addition to the attributes and behaviors defined in the LinkedList class, the StackLinkedList class requires five behaviors defined as member functions: a constructor and destructor, push() , pop() , and isEmpty() . The StackLinkedList class definition is shown here:

 class StackLinkedList : public LinkedList {  public:  StackLinkedList();  virtual ~StackLinkedList();  void push(int);  int pop();  bool isEmpty(); }; 

StackLinkedList Constructor and Destructor

The constructor and destructor of the StackLinkedList class may be confusing the first time you look at them because both are empty and there aren t any instructions specified in the body of the constructor and destructor, as shown here:

 StackLinkedList() { } ~StackLinkedList() { } 

The constructor is empty because the constructor of the LinkedList class is called before the constructor of the StackLinkedList class. You ll recall that the StackLinkedList class inherits the LinkedList class. The LinkedList class constructor initializes the front and back pointers of the linked list to NULL. Therefore, there is nothing else for the StackLinkedList class constructor to do.

Likewise, the destructor of the LinkedList class is called before the destructor of the StackLinkedList class. The LinkedList class constructor deletes all memory that is associated with the nodes of the linked list. Therefore, the destructor of the StackLinkedList class also has nothing to do.

Pushing a Node onto a Stack-Linked List

In Chapter 4, you learned that data is placed at the top of the stack and removed from the top of the stack. Programmers call this pushing data onto the stack and popping data off the stack. The same steps occur when using a linked list for the stack, but instead of placing data at the next available index in an array, it is placed at the back of the linked list.

You ll need to define a push() member function for the StackLinkedList class that is called whenever data is added to the stack. Remember that you are really adding a node to the linked list and not simply data. Data is contained in the node.

To add a node to the stack, you use the same steps you use to add a node to a linked list. This means that the appendNode() member function of the LinkedList class can be used to place a new node on the stack. Therefore, all you need is to call the appendNode() member function from the push() member function. Because appendNode() is public, you could just call appendNode directly to push a node onto the stack, but putting a push() function in the stack class makes this more intuitive to somebody using this class. This also helps hide the underlying implementation so using the class is a little more straightforward.

As you ll recall from Chapter 6, the appendNode() member function requires one argument, which is the data that is assigned to the new node. You must define the push() member function to accept the same data as its argument in order to pass this data to the appendNode() member function. This is illustrated in the following example. The push() member function requires an integer passed as an argument. The integer is then passed to the appendNode() member function within the body of the push() function definition.

 void push(int x) {  appendNode(x); } 

Popping a Node from a Stack-Linked List

You ll also need to define a member function to pop a node from the stack. In this example, we ll call it pop() . Because you re using the linked list as the stack, the pop() member function must remove the node from the back of the linked list.

Unfortunately, you cannot simply call a member function of the LinkedList class to pop the node off the stack because the LinkedList class doesn t define a member function that removes a node from the linked list. If you had a member function in the base class for removeBack() , you could call that to pop a node off the list. In this case, you ll need to define a pop() function in the StackLinkedList class to do this. This will give you a last in, first out access to the stack.

Here is the definition of the pop() member function. Refer to the picture of the stacked linked list in Figure 7-2 as you read to help you understand how the pop() member function works.

click to expand
Figure 7-2: The pop() member function removes the node at the top of the stack, which is the node at the front of the linked list.
 int pop() {  if (isEmpty())  {  return -1;  }  int retVal = back->data;  NODE * temp = back;  if (back->previous == NULL)  {  back = NULL;  front = NULL;  }  else  {  back = back->previous;  back->next = NULL;  }  delete temp;  return retVal; } 

First, you must determine if there is anything on the stack by calling the isEmpty() member function. We ll show you how this member function works later in this section. For now, understand that the isEmpty() member function returns a Boolean true if the stack is empty, or a Boolean false if it is not. You can see in Figure 7-2 that the stack has two nodes on the stack, so it is not empty. Therefore, the return statement in the if statement is not executed.

The pop() member function refers to the back attribute of the LinkedList class. It is important to remember that the back  attribute refers to the top of the stack. Nodes will be removed from the back of the linked list to do a pop operation. Therefore, the value of front is Node 2.

The value of Node 2 is assigned to the retVal variable, which is the value returned by the pop() member function if there is a node on the stack. This pops the value from the stack.

Next, the address of the back node, which is Node 2, is assigned to a temporary pointer. The node that the temporary pointer points to is removed from memory with the delete operator at the end of the pop() member function.

Next, you determine if the node at the back of the stack was the only node on the linked list. You make this determination by seeing if the previous attribute of the node is NULL. If the previous pointer on the back of the list is NULL, this indicates that there s only one node in the linked list.

Be careful when analyzing the pop() member function. Remember that the back of the linked list is the top of the stack and that the bottom of the stack is the top of the linked list.

If the pop() member function is removing the only node on the stack, then the front and back attributes of the LinkedList class are set to NULL, indicating there are no nodes left on the linked list after the pop() is executed.

However, if there is at least one node on the stack, statements within the else statement are executed, as in Figure 7-2. The first statement within the else statement assigns the previous attribute of the back attribute as the new back. In Figure 7-2, the previous attribute is 1. This tells you that Node 1 comes before Node 2. You then assign Node 1 as the new back of the stack.

Remember that there isn t a next node on the stack because you are always working with the back of the linked list. Therefore, you need to assign NULL to the next attribute of the back node, which is Node 1. This makes Node 1 at the top of the stack.

The next to last statement removes the node from memory using the delete operator. The temporary pointer points to the memory address of the node that was removed from the stack. The last statement returns the value of the node that was removed from the stack.

Determine If the Stack Is Empty

The pop() member function must determine if the stack is empty, or it will attempt to remove a node that isn t on the stack. The pop() member function determines if the stack is empty by calling the isEmpty() member function, which you must define as part of the StackLinkedList class.

The isEmpty() member function is a simple function, as shown next. It determines if the stack is empty by seeing if the value of the front attribute of the LinkedList class is NULL. If so, then a Boolean true is returned; otherwise , a Boolean false is returned. If the stack is empty, both front and back are equal to NULL but you only need to check one of them.

 bool isEmpty() {  if(front == NULL)  {  return true;  }  else  {  return false;  } } 



Data Structures Demystified
Data Structures Demystified (Demystified)
ISBN: 0072253592
EAN: 2147483647
Year: 2006
Pages: 90

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net