Section 24.5. Stacks

24.5. Stacks

A stack is a constrained version of a linked lista stack 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 non-recursive method calls.

The System.Collections namespace contains class Stack for implementing and manipulating stacks that can grow and shrink during program execution. Chapters 25 and 26 both discuss class Stack.

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. 24.4. Then we implement an identically performing stack class through composition by including a reference to a List object as a Private member of a stack class.

Stack Class That Inherits from List

The program of Fig. 24.13. and 24.14. creates a stack class by inheriting from class List of Fig. 24.4 (line 9). We want the stack to have methods Push, Pop, IsEmpty and Print. Essentially, these are the methods InsertAtFront, RemoveFromFront, IsEmpty and Print 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. Remember that all methods in the Public interface of class List are inherited as Public methods of the derived class StackInheritance (Fig. Fig.24.13).

Figure 24.13. StackInheritance extends class List.

  1  ' Fig. 24.13: StackInheritanceLibrary.vb  2  ' Implementing a stack by inheriting  from class List.  3  Imports LinkedListLibrary  4  5  ' class StackInheritance inherits class List's capabilities  6  Public Class StackInheritance : Inherits List  7     ' pass name "stack" to List constructor  8     Public Sub New()  9        MyBase.New("stack") 10     End Sub ' New 11 12     ' place dataValue at top of stack  by inserting 13     ' dataValue at front of linked list 14     Public Sub Push(ByVal dataValue As Object$) 15        InsertAtFront(dataValue) 16     End Sub ' Push 17 18     ' remove item from top of stack by removing 19     ' item at front of linked list 20     Public Function Pop() As Object 21        Return RemoveFromFront() 22     End Function ' Pop 23  End Class' StackInheritance 

Figure 24.14. Using class StackInheritance.

  1  ' Fig. 24.14: StackInheritanceTest.vb  2  ' Testing class StackInheritance.  3  Imports StackInheritanceLibrary  4  Imports LinkedListLibrary  5  6  Module StackInheritanceTest  7     Sub Main()  8        Dim stack As New StackInheritance()  9 10        ' create objects to store in the stack 11        Dim aBoolean As Boolean = True 12        Dim aCharacter As Char = "$"c 13        Dim anInteger As Integer = 34567 14        Dim aString As String = "hello" 15 16        ' use method Push to add  items to stack 17        stack.Push(aBoolean)                     18        stack.Print()                            19        stack.Push(aCharacter)                   20        stack.Print()                            21        stack.Push(anInteger)                    22        stack.Print()                            23        stack.Push(aString)                      24        stack.Print()                            25 26        ' remove items from stack 27        Try 28           While True 29              Dim removedObject As Object = stack.Pop() 30              Console.WriteLine(removedObject & " popped") 31              stack.Print() 32           End While 33        Catch exception As EmptyListException 34           ' if exception occurs, print stack trace 35           Console.Error.WriteLine(exception.StackTrace) 36        End Try 37     End Sub ' Main 38  End Module ' StackInheritanceTest 

[View full width]
 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()    at StackInheritanceLibrary.StackInheritance.Pop()    at StackInheritanceTest.StackInheritanceTest .Main(String[] args)       in C:\examples\ch25\Fig25_14 \StackInheritanceTest\       StackInheritanceTest.cs:line 35 

The implementation of each StackInheritance method calls the appropriate List methodmethod Push calls InsertAtFront, method Pop calls RemoveFromFront. Class StackInheritance does not define methods IsEmpty and Print, because it inherits them from class List into StackInheritance's Public interface. Note that class StackInheritance uses namespace LinkedListLibrary (which is the name of the project you created in Fig. 24.4); thus, the class library that defines StackInheritance must have a reference to the LinkedListLibrary class library.

StackInheritanceTest's Main method (Fig. 24.14) uses class StackInheritance to create a stack of Objects called stack (line 8). Lines 11-14 define four values of various types to push onto and pop off the stack. The program pushes onto the stack (lines 17, 19, 21 and 23) a Boolean (true), a Char ('$'), an Integer (34567) and a String ("hello"). An infinite loop (lines 28-32) pops the elements from the stack. When the stack is empty, 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 Print (inherited by StackInheritance from class List) to output the stack contents after each operation. Class StackInheritanceTest uses namespace LinkedListLibrary (Fig. 24.4) and namespace StackInheritanceLibrary (Fig. 24.13); thus, the solution for class StackInheritanceTest must have references to both class libraries.

Stack Class That Contains a Reference to a List

Another way to implement a stack class is by reusing a list class through composition. The class in Fig. 24.15 uses a Private object of class List (line 6) in the declaration of class StackComposition. 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 InsertAtFront, RemoveFromFront, IsEmpty and Print. In this example, we do not show class StackCompositionTest, because the only difference (from StackInheritanceTest) in this example is that we change the name of the stack class from StackInheritance to StackComposition. If you download and execute the application, you will see that the output is identical.

Figure 24.15. StackComposition class encapsulates functionality of class List.

  1  ' Fig. 24.15: StackCompositionLibrary.vb  2  ' StackComposition declaration with composed List object.  3  Imports LinkedListLibrary  4  5  Public Class StackComposition  6     Private stack As List  7  8     ' construct empty stack  9     Public Sub New() 10        stack = New List("stack") 11     End Sub ' New 12 13     ' add object to stack 14     Public Sub Push(ByVal dataValue As Object) 15        stack.InsertAtFront(dataValue) 16     End Sub ' Push 17 18     ' remove object from stack 19     Public Function Pop() As Object 20        Return stack.RemoveFromFront() 21     End Function ' Pop 22 23     ' determine whether stack is empty 24     Public Function IsEmpty() As Boolean 25        Return stack.IsEmpty() 26     End Function ' IsEmpty 27 28     ' output stack  contents 29     Public Sub Print() 30        stack.Print() 31     End Sub ' Print 32  End Class ' StackComposition