19.5 Stacks

A stack may be viewed as a constrained version of a linked list—it receives new nodes and releases nodes only at the top. For this reason, a stack is referred to as a last-in, first-out (LIFO) data structure.

The primary operations to manipulate a stack are push and pop. Operation push adds a new node to the top of the stack. Operation pop removes a node from the top of the stack and returns the data item from the popped node.

Stacks have many interesting applications. For example, when a program calls a method, the called method must know how to return to its caller, so the return address is pushed onto the method-call stack. If a series of method calls occurs, the successive return values are pushed onto the stack in last-in, first-out order so that each method can return to its caller. Stacks support recursive method calls in the same manner that they do conventional nonrecursive method calls.

In our next example, we take advantage of the close relationship between lists and stacks to implement a stack class by reusing a list class. We demonstrate two different forms of reusability. First, we implement the stack class by inheriting from class List of Fig. 19.4. Then we implement an identically performing stack class through composition by including a List object as a private member of a stack class. The System.Collections.Generic namespace contains class Stack for implementing and manipulating stacks that can grow and shrink during program execution.

Stack Class That Inherits from List

The code in Fig. 19.13 creates a stack class by inheriting from class List of Fig. 19.4 (line 8 of Fig. 19.13). We want the stack to have methods Push, Pop, IsEmpty and Display. Essentially, these are the methods InsertAtFront, RemoveFromFront, IsEmpty and Display of class List. Of course, class List contains other methods (such as InsertAtBack and RemoveFromBack) that we would rather not make accessible through the public interface of the stack. It’s important to remember though that all methods in the public inter-face of class List are also public methods of the derived class StackInheritance (Fig. 19.13).

Fig. 19.13 Implementing a stack by inheriting from class List.

Alternate View 

  1   // Fig. 19.13: StackInheritanceLibrary.cs
  2   // Implementing a stack by inheriting from class List.
  3   using LinkedListLibrary;
  4
  5   namespace StackInheritanceLibrary
  6   {
  7      // class StackInheritance inherits class List's capabilities
  8      public class StackInheritance : List
  9      {
 10         // pass name "stack" to List constructor
 11         public StackInheritance() : base("stack") { }
 12
 13         // place dataValue at top of stack by inserting
 14         // dataValue at front of linked list
 15         public void Push(object dataValue)
 16         {
 17            InsertAtFront(dataValue);
 18         }
 19
 20         // remove item from top of stack by removing
 21         // item at front of linked list
 22         public object Pop()
 23         {
 24            return RemoveFromFront();
 25         }
 26      }
 27   }

The implementation of each StackInheritance method calls the appropriate List method—method Push calls InsertAtFront, method Pop calls RemoveFromFront. Class StackInheritance does not define methods IsEmpty and Display, because StackInheritance inherits these methods from class List into StackInheritance’s public interface. Class StackInheritance uses namespace LinkedListLibrary (Fig. 19.4); thus, the class library that defines StackInheritance must have a reference to the LinkedListLibrary class library.

StackInheritanceTest’s Main method (Fig. 19.14) uses class StackInheritance to create a stack of objects called stack (line 12). Lines 15–18 define four values that will be pushed onto the stack and popped off it. The program pushes onto the stack (lines 21, 23, 25 and 27) a bool containing true, a char containing '$', an int containing 34567 and a string containing "hello". An infinite while loop (lines 33–38) pops the elements from the stack. When the stack is empty, method Pop throws an EmptyListException, and the program displays the exception’s stack trace, which shows the program-execution stack at the time the exception occurred. The program uses method Display (inherited by StackInheritance from class List) to output the contents of the stack after each operation. Class StackInheritanceTest uses namespace LinkedListLibrary (Fig. 19.4) and namespace StackInheritanceLibrary (Fig. 19.13); thus, the solution for class StackInheritanceTest must have references to both class libraries.

Fig. 19.14 Testing class StackInheritance.

Alternate View 

  1   // Fig. 19.14: StackInheritanceTest.cs
  2   // Testing class StackInheritance.
  3   using System;
  4   using StackInheritanceLibrary;
  5   using LinkedListLibrary;
  6
  7   // demonstrate functionality of class StackInheritance
  8   class StackInheritanceTest
  9   {
 10      static void Main()
 11      {
 12         StackInheritance stack = new StackInheritance();
 13
 14         // create objects to store in the stack
 15         bool aBoolean = true;
 16         char aCharacter = '$';
 17         int anInteger = 34567;
 18         string aString = "hello";
 19
 20         // use method Push to add items to stack
 21         stack.Push(aBoolean);
 22         stack.Display();
 23         stack.Push(aCharacter);
 24         stack.Display();
 25         stack.Push(anInteger);
 26         stack.Display();
 27         stack.Push(aString);
 28         stack.Display();
 29
 30         // remove items from stack
 31         try
 32         {
 33            while (true)
 34            {
 35               object removedObject = stack.Pop();
 36               Console.WriteLine($"{removedObject} popped");
 37               stack.Display();
 38            }
 39         }
 40         catch (EmptyListException emptyListException)
 41         {
 42            // if exception occurs, write stack trace
 43            Console.Error.WriteLine(emptyListException.StackTrace);
 44         }
 45      }
 46   }


The stack is: True

The stack is: $ True

The stack is: 34567 $ True

The stack is: hello 34567 $ True


hello popped
The stack is: 34567 $ True

34567 popped
The stack is: $ True

$ popped
The stack is: True

True popped
Empty stack
   at LinkedListLibrary.List.RemoveFromFront() in C:UsersPaulDeitel
      Documentsexamplesch19Fig19_04LinkedListLibrary
      LinkedListLibraryLinkedListLibrary.cs:line 81
   at StackInheritanceLibrary.StackInheritance.Pop() in C:Users
      PaulDeitelDocumentsexamplesch19Fig19_13StackInheritanceLibrary
      StackInheritanceLibraryStackInheritance.cs:line 24
   at StackInheritanceTest.Main(String[] args) in C:UsersPaulDeitel
      Documentsexamplesch19Fig19_14StackInheritanceTest
      StackInheritanceTestStackInheritanceTest.cs:line 35

Stack Class That Contains a Reference to a List

Another way to implement a stack class is by reusing a list through composition. Class StackComposition (Fig. 19.15) uses a private object of class List (line 10). Composition enables us to hide the methods of class List that should not be in our stack’s public interface by providing public interface methods only to the required List methods. This class implements each stack method by delegating its work to an appropriate List method. StackComposition’s methods call List methods Insert-AtFront, RemoveFromFront, IsEmpty and Display. In this example, we do not show class StackCompositionTest, because the only differences in this example are that we change the name of the stack class from StackInheritance to StackComposition and update a using directive.

Fig. 19.15 StackComposition class encapsulates functionality of class List.

Alternate View 

  1   // Fig. 19.15: StackCompositionLibrary.cs
  2   // StackComposition class encapsulates functionality of class List.
  3   using LinkedListLibrary;
  4
  5   namespace StackCompositionLibrary
  6   {
  7      // class StackComposition encapsulates List's capabilities
  8      public class StackComposition
  9      {
 10         private List stack;
 11
 12         // construct empty stack
 13         public StackComposition()
 14         {
 15            stack = new List("stack");
 16         }
 17
 18         // add object to stack
 19         public void Push(object dataValue)
 20         {
 21            stack.InsertAtFront(dataValue);
 22         }
 23
 24         // remove object from stack
 25         public object Pop()
 26         {
 27            return stack.RemoveFromFront();
 28         }
 29
 30         // determine whether stack is empty
 31         public bool IsEmpty()
 32         {
 33            return stack.IsEmpty();
 34         }
 35
 36         // output stack contents
 37         public void Display()
 38         {
 39            stack.Display();
 40         }
 41      }
 42   }
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset