Stacks

Table of contents:

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 2627 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. 25.4. Then we implement an identically performing stack class through composition by including a List object as a private member of a stack class.

Stack Class That Inherits from List

The program of Figs. 25.13 and 25.14 creates a stack class by inheriting from class List of Fig. 25.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. It is important to remember that all methods in the public interface of class List are also public methods of the derived class StackInheritance (Fig. 25.13).

Figure 25.13. StackInheritance extends class List.

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

Figure 25.14. Using class StackInheritance.

(This item is displayed on pages 1339 - 1340 in the print version)

 1 // Fig. 25.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( string[] args )
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.Print(); 
23 stack.Push( aCharacter ); 
24 stack.Print(); 
25 stack.Push( anInteger ); 
26 stack.Print(); 
27 stack.Push( aString ); 
28 stack.Print(); 
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.Print(); 38 } // end while 39 } // end try 40 catch ( EmptyListException emptyListException ) 41 { 42 // if exception occurs, print stack trace 43 Console.Error.WriteLine( emptyListException.StackTrace ); 44 } // end catch 45 } // end Main 46 } // end class StackInheritanceTest
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:examplesch25Fig25_14StackInheritanceTest
 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 StackInheritance inherits these methods from class List into StackInheritance's public interface. Note that class StackInheritance uses namespace LinkedListLibrary (Fig. 25.4); thus, the class library that defines StackInheritance must have a reference to the LinkedListLibrary class library.

StackInheritanceTest's Main method (Fig. 25.14) uses class StackInheritance to create a stack of objects called stack (line 12). Lines 1518 define four values that will be pushed onto the stack and popped off the stack. 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 3338) 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 programexecution stack at the time the exception occurred. The program uses method Print (inherited by StackInheritance from class List) to output the contents of the stack after each operation. Note that class StackInheritanceTest uses namespace LinkedListLibrary (Fig. 25.4) and namespace StackInheritanceLibrary (Fig. 25.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. 25.15 uses a private object of class List (line 11) 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 in this example is that we change the name of the stack class from StackInheritance to StackComposition. If you execute the application from the code on the CD that accompanies this book, you will see that the output is identical.

Figure 25.15. StackComposition class encapsulates functionality of class List.

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

Queues

Preface

Index

    Introduction to Computers, the Internet and Visual C#

    Introduction to the Visual C# 2005 Express Edition IDE

    Introduction to C# Applications

    Introduction to Classes and Objects

    Control Statements: Part 1

    Control Statements: Part 2

    Methods: A Deeper Look

    Arrays

    Classes and Objects: A Deeper Look

    Object-Oriented Programming: Inheritance

    Polymorphism, Interfaces & Operator Overloading

    Exception Handling

    Graphical User Interface Concepts: Part 1

    Graphical User Interface Concepts: Part 2

    Multithreading

    Strings, Characters and Regular Expressions

    Graphics and Multimedia

    Files and Streams

    Extensible Markup Language (XML)

    Database, SQL and ADO.NET

    ASP.NET 2.0, Web Forms and Web Controls

    Web Services

    Networking: Streams-Based Sockets and Datagrams

    Searching and Sorting

    Data Structures

    Generics

    Collections

    Appendix A. Operator Precedence Chart

    Appendix B. Number Systems

    Appendix C. Using the Visual Studio 2005 Debugger

    Appendix D. ASCII Character Set

    Appendix E. Unicode®

    Appendix F. Introduction to XHTML: Part 1

    Appendix G. Introduction to XHTML: Part 2

    Appendix H. HTML/XHTML Special Characters

    Appendix I. HTML/XHTML Colors

    Appendix J. ATM Case Study Code

    Appendix K. UML 2: Additional Diagram Types

    Appendix L. Simple Types

    Index



    Visual C# How to Program
    Visual C# 2005 How to Program (2nd Edition)
    ISBN: 0131525239
    EAN: 2147483647
    Year: 2004
    Pages: 600

    Similar book on Amazon

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