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.
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).
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 object
s 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.
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.