20.6 Generic Classes
The concept of a data structure (e.g., a stack) that contains data elements can be understood independently of the element type it manipulates. A generic class provides a means for describing a class in a type-independent manner. We can then instantiate type-specific versions of the generic class. This capability is an opportunity for software reusability.
With a generic class, you can use a simple, concise notation to indicate the actual type(s) that should be used in place of the class’s type parameter(s). At compilation time, the compiler ensures your code’s type safety, and the runtime system replaces type parameters with type arguments to enable your client code to interact with the generic class.
One generic Stack class, for example, could be the basis for creating many Stack classes (e.g., “Stack of double,” “Stack of int,” “Stack of char,” “Stack of Employee”). Figure 20.5 presents a generic Stack class declaration. This class should not be confused with the class Stack from namespace System.Collections.Generics. A generic class declaration is similar to a nongeneric class declaration, except that the class name is followed by a type-parameter list (line 5) and, optionally, one or more constraints on its type parameter. Type parameter T represents the element type the Stack will manipulate. As with generic methods, the type-parameter list of a generic class can have one or more type parameters separated by commas. (You’ll create a generic class with two type parameters in Exercise 20.11.) Type parameter T is used throughout the Stack class declaration (Fig. 20.5) to represent the element type. Class Stack declares variable elements as an array of type T (line 8). This array (created at line 25) will store the Stack’s elements. [Note: This example implements a Stack as an array. As you’ve seen in Chapter 19, Stacks also are commonly implemented as constrained versio/ns of linked lists.]
Fig. 20.5 Generic class Stack.
Alternate View
1 // Fig. 20.5: Stack.cs
2 // Generic class Stack.
3 using System;
4
5 public class Stack<T>
6 {
7 private int top; // location of the top element
8 private T[] elements; // array that stores stack elements
9
10 // parameterless constructor creates a stack of the default size
11 public Stack()
12 : this(10) // default stack size
13 {
14 // empty constructor; calls constructor at line 18 to perform init
15 }
16
17 // constructor creates a stack of the specified number of elements
18 public Stack(int stackSize)
19 {
20 if (stackSize <= 0) // validate stackSize
21 {
22 throw new ArgumentException("Stack size must be positive.");
23 }
24
25 elements = new T[stackSize]; // create stackSize elements
26 top = -1; // stack initially empty
27 }
28
29 // push element onto the stack; if unsuccessful,
30 // throw FullStackException
31 public void Push(T pushValue)
32 {
33 if (top == elements.Length - 1) // stack is full
34 {
35 throw new FullStackException(
36 $"Stack is full, cannot push {pushValue}");
37 }
38
39 ++top; // increment top
40 elements[top] = pushValue; // place pushValue on stack
41 }
42
43 // return the top element if not empty,
44 // else throw EmptyStackException
45 public T Pop()
46 {
47 if (top == -1) // stack is empty
48 {
49 throw new EmptyStackException("Stack is empty, cannot pop");
50 }
51
52 --top; // decrement top
53 return elements[top + 1]; // return top value
54 }
55 }As with generic methods, when a generic class is compiled, the compiler performs type checking on the class’s type parameters to ensure that they can be used with the code in the generic class. For value-types, the compiler generates a custom version of the class for each unique value type used to create a new Stack object, and for reference types, the compiler generates a single additional custom Stack. The constraints determine the operations that can be performed on the type parameters. For reference types, the runtime system replaces the type parameters with the actual types. For class Stack, no type constraint is specified, so the default type constraint, object, is used. The scope of a generic class’s type parameter is the entire class.
Stack Constructors
Class Stack has two constructors. The parameterless constructor (lines 11–15) passes the default stack size (10) to the one-argument constructor, using the syntax this (line 12) to invoke another constructor in the same class. The one-argument constructor (lines 18–27) validates the stackSize argument and creates an array of the specified stackSize (if it’s greater than 0) or throws an exception, otherwise.
Stack Method Push
Method Push (lines 31–41) first determines whether an attempt is being made to push an element onto a full Stack. If so, line 35–36 throw a FullStackException (declared in Fig. 20.6). If the Stack is not full, line 39 increments the top counter to indicate the new top position, and line 40 places the argument in that location of array elements.
Stack Method Pop
Method Pop (lines 45–54) first determines whether an attempt is being made to pop an element from an empty Stack. If so, line 49 throws an EmptyStackException (declared in Fig. 20.7). Otherwise, line 52 decrements the top counter to indicate the new top position, and line 53 returns the original top element of the Stack.
Classes FullStackException and EmptyStackException
Classes FullStackException (Fig. 20.6) and EmptyStackException (Fig. 20.7) each provide a parameterless constructor, a one-argument constructor of exception classes (as discussed in Section 13.8) and a two-argument constructor for creating a new exception using an existing one. The parameterless constructor sets the default error message while the other two constructors set custom error messages.
Fig. 20.6 FullStackException indicates a stack is full.
Alternate View
1 // Fig. 20.6: FullStackException.cs
2 // FullStackException indicates a stack is full.
3 using System;
4
5 public class FullStackException : Exception
6 {
7 // parameterless constructor
8 public FullStackException() : base("Stack is full")
9 {
10 // empty constructor
11 }
12
13 // one-parameter constructor
14 public FullStackException(string exception) : base(exception)
15 {
16 // empty constructor
17 }
18
19 // two-parameter constructor
20 public FullStackException(string exception, Exception inner)
21 : base(exception, inner)
22 {
23 // empty constructor
24 }
25 }
Fig. 20.7 EmptyStackException indicates a stack is empty.
Alternate View
1 // Fig. 20.7: EmptyStackException.cs
2 // EmptyStackException indicates a stack is empty.
3 using System;
4
5 public class EmptyStackException : Exception
6 {
7 // parameterless constructor
8 public EmptyStackException() : base("Stack is empty")
9 {
10 // empty constructor
11 }
12
13 // one-parameter constructor
14 public EmptyStackException(string exception) : base(exception)
15 {
16 // empty constructor
17 }
18
19 // two-parameter constructor
20 public EmptyStackException(string exception, Exception inner)
21 : base(exception, inner)
22 {
23 // empty constructor
24 }
25 }Demonstrating Class Stack
Now, let’s consider an app (Fig. 20.8) that uses our generic Stack class. Lines 13–14 declare variables of type Stack<double> (pronounced “Stack of double”) and Stack<int> (pronounced “Stack of int”). The types double and int are the Stack’s type arguments. The compiler replaces the type parameters in the generic class and performs type checking. Method Main instantiates objects doubleStack of size 5 (line 18) and intStack of size 10 (line 19), then calls methods TestPushDouble (declared in lines 28–47), TestPopDouble (declared in lines 50–71), TestPushInt (declared in lines 74–93) and TestPopInt (declared in lines 96–117) to manipulate the two Stacks in this example.
Fig. 20.8 Testing generic class Stack.
Alternate View
1 // Fig. 20.8: StackTest.cs
2 // Testing generic class Stack.
3 using System;
4
5 class StackTest
6 {
7 // create arrays of doubles and ints
8 private static double[] doubleElements =
9 {1.1, 2.2, 3.3, 4.4, 5.5, 6.6};
10 private static int[] intElements =
11 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
12
13 private static Stack<double> doubleStack; // stack stores doubles
14 private static Stack<int> intStack; // stack stores ints
15
16 static void Main()
17 {
18 doubleStack = new Stack<double>(5); // stack of doubles
19 intStack = new Stack<int>(10); // stack of ints
20
21 TestPushDouble(); // push doubles onto doubleStack
22 TestPopDouble(); // pop doubles from doubleStack
23 TestPushInt(); // push ints onto intStack
24 TestPopInt(); // pop ints from intStack
25 }
26
27 // test Push method with doubleStack
28 private static void TestPushDouble()
29 {
30 // push elements onto stack
31 try
32 {
33 Console.WriteLine("
Pushing elements onto doubleStack");
34
35 // push elements onto stack
36 foreach (var element in doubleElements)
37 {
38 Console.Write($"{element:F1} ");
39 doubleStack.Push(element); // push onto doubleStack
40 }
41 }
42 catch (FullStackException exception)
43 {
44 Console.Error.WriteLine($"
Message: {exception.Message}");
45 Console.Error.WriteLine(exception.StackTrace);
46 }
47 }
48
49 // test Pop method with doubleStack
50 private static void TestPopDouble()
51 {
52 // pop elements from stack
53 try
54 {
55 Console.WriteLine("
Popping elements from doubleStack");
56
57 double popValue; // store element removed from stack
58
59 // remove all elements from stack
60 while (true)
61 {
62 popValue = doubleStack.Pop(); // pop from doubleStack
63 Console.Write($"{popValue:F1} ");
64 }
65 }
66 catch (EmptyStackException exception)
67 {
68 Console.Error.WriteLine($"
Message: {exception.Message}");
69 Console.Error.WriteLine(exception.StackTrace);
70 }
71 }
72
73 // test Push method with intStack
74 private static void TestPushInt()
75 {
76 // push elements onto stack
77 try
78 {
79 Console.WriteLine("
Pushing elements onto intStack");
80
81 // push elements onto stack
82 foreach (var element in intElements)
83 {
84 Console.Write($"{element} ");
85 intStack.Push(element); // push onto intStack
86 }
87 }
88 catch (FullStackException exception)
89 {
90 Console.Error.WriteLine($"
Message: {exception.Message}");
91 Console.Error.WriteLine(exception.StackTrace);
92 }
93 }
94
95 // test Pop method with intStack
96 private static void TestPopInt()
97 {
98 // pop elements from stack
99 try
100 {
101 Console.WriteLine("
Popping elements from intStack");
102
103 int popValue; // store element removed from stack
104
105 // remove all elements from stack
106 while (true)
107 {
108 popValue = intStack.Pop(); // pop from intStack
109 Console.Write($"{popValue:F1} ");
110 }
111 }
112 catch (EmptyStackException exception)
113 {
114 Console.Error.WriteLine($"
Message: {exception.Message}");
115 Console.Error.WriteLine(exception.StackTrace);
116 }
117 }
118 }Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5 6.6
Message: Stack is full, cannot push 6.6
at Stack`1.Push(T pushValue) in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStack.cs:line 35
at StackTest.TestPushDouble() in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStackTest.cs:line 39
Popping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
Message: Stack is empty, cannot pop
at Stack`1.Pop() in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStack.cs:line 49
at StackTest.TestPopDouble() in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStackTest.cs:line 62
Pushing elements onto intStack
1 2 3 4 5 6 7 8 9 10 11
Message: Stack is full, cannot push 11
at Stack`1.Push(T pushValue) in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStack.cs:line 35
at StackTest.TestPushInt() in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStackTest.cs:line 85
Popping elements from intStack
10 9 8 7 6 5 4 3 2 1
Message: Stack is empty, cannot pop
at Stack`1.Pop() in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStack.cs:line 49
at StackTest.TestPopInt() in C:UsersPaulDeitelDocuments
examplesch20Fig20_05_08StackStackStackTest.cs:line 109
Method TestPushDouble
Method TestPushDouble (lines 28–47) invokes method Push to place the double values 1.1, 2.2, 3.3, 4.4 and 5.5 stored in array doubleElements onto doubleStack. The foreach statement terminates when the test program attempts to Push a sixth value onto doubleStack (which is full, because doubleStack can store only five elements). In this case, the method throws a FullStackException (Fig. 20.6) to indicate that the Stack is full. Lines 42–46 of Fig. 20.8 catch this exception and display the message and stack-trace information. The stack trace indicates the exception that occurred and shows that Stack method Push generated the exception at line 35 of the file Stack.cs (Fig. 20.5). The trace also shows that method Push was called by StackTest method TestPushDouble at line 39 of StackTest.cs. This information enables you to determine the methods that were on the method-call stack at the time that the exception occurred. Because the program catches the exception, the C# runtime environment considers the exception to have been handled, and the program can continue executing.
Method TestPopDouble
Method TestPopDouble (Fig. 20.8, lines 50–71) invokes Stack method Pop in an infinite while loop to remove all the values from the stack. Note in the output that the values are popped off in last-in, first-out order—this, of course, is the defining characteristic of stacks. The while loop (lines 60–64) continues until the stack is empty. An EmptyStack-Exception occurs when an attempt is made to pop from the empty stack. This causes the program to proceed to the catch block (lines 66–70) and handle the exception, so the program can continue executing. When the test program attempts to Pop a sixth value, the doubleStack is empty, so method Pop throws an EmptyStackException.
Methods TestPushInt and TestPopInt
Method TestPushInt (lines 74–93) invokes Stack method Push to place values onto int-Stack until it’s full. Method TestPopInt (lines 96–117) invokes Stack method Pop to remove values from intStack until it’s empty. Again, values pop in last-in, first-out order.
Creating Generic Methods to Test Class Stack<T>
Note that the code in methods TestPushDouble and TestPushInt is virtually identical for pushing values onto Stacks. Similarly the code in methods TestPopDouble and TestPopInt is virtually identical for popping values from Stacks. This presents another opportunity to use generic methods. Figure 20.9 declares generic method TestPush (lines 33–53) to perform the same tasks as TestPushDouble and TestPushInt in Fig. 20.8—that is, Push values onto a Stack<T>. Similarly, generic method TestPop (lines 56–77) performs the same tasks as TestPopDouble and TestPopInt in Fig. 20.8—that is, Pop values off a Stack<T>.
Fig. 20.9 Testing generic class Stack.
Alternate View
1 // Fig. 20.9: StackTest.cs
2 // Testing generic class Stack.
3 using System;
4 using System.Collections.Generic;
5
6 class StackTest
7 {
8 // create arrays of doubles and ints
9 private static double[] doubleElements =
10 {1.1, 2.2, 3.3, 4.4, 5.5, 6.6};
11 private static int[] intElements =
12 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
13
14 private static Stack<double> doubleStack; // stack stores doubles
15 private static Stack<int> intStack; // stack stores int objects
16
17 static void Main()
18 {
19 doubleStack = new Stack<double>(5); // stack of doubles
20 intStack = new Stack<int>(10); // stack of ints
21
22 // push doubles onto doubleStack
23 TestPush(nameof(doubleStack), doubleStack, doubleElements);
24 // pop doubles from doubleStack
25 TestPop(nameof(doubleStack), doubleStack);
26 // push ints onto intStack
27 TestPush(nameof(doubleStack), intStack, intElements);
28 // pop ints from intStack
29 TestPop(nameof(doubleStack), intStack);
30 }
31
32 // test Push method
33 private static void TestPush<T>(string name, Stack<T> stack,
34 IEnumerable<T> elements)
35 {
36 // push elements onto stack
37 try
38 {
39 Console.WriteLine($"
Pushing elements onto {name}");
40
41 // push elements onto stack
42 foreach (var element in elements)
43 {
44 Console.Write($"{element} ");
45 stack.Push(element); // push onto stack
46 }
47 }
48 catch (FullStackException exception)
49 {
50 Console.Error.WriteLine($"
Message: {exception.Message}");
51 Console.Error.WriteLine(exception.StackTrace);
52 }
53 }
54
55 // test Pop method
56 private static void TestPop<T>(string name, Stack<T> stack)
57 {
58 // pop elements from stack
59 try
60 {
61 Console.WriteLine($"
Popping elements from {name}");
62
63 T popValue; // store element removed from stack
64
65 // remove all elements from stack
66 while (true)
67 {
68 popValue = stack.Pop(); // pop from stack
69 Console.Write($"{popValue} ");
70 }
71 }
72 catch (EmptyStackException exception)
73 {
74 Console.Error.WriteLine($"
Message: {exception.Message}");
75 Console.Error.WriteLine(exception.StackTrace);
76 }
77 }
78 }Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5 6.6
Message: Stack is full, cannot push 6.6
at Stack`1.Push(T pushValue) in C:UsersPaulDeitelDocuments
examplesch20Fig20_09StackStackStack.cs:line 35
at StackTest.TestPush[T](String name, Stack`1 stack, IEnumerable`1
elements) in C:UsersPaulDeitelDocumentsexamplesch20Fig20_09
StackStackStackTest.cs:line 45
Popping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
Message: Stack is empty, cannot pop
at Stack`1.Pop() in C:UsersPaulDeitelDocuments
examplesch20Fig20_09StackStackStack.cs:line 49
at StackTest.TestPop[T](String name, Stack`1 stack) in
C:UsersPaulDeitelDocumentsexamplesch20Fig20_09Stack
StackStackTest.cs:line 68
Pushing elements onto intStack
1 2 3 4 5 6 7 8 9 10 11
Message: Stack is full, cannot push 11
at Stack`1.Push(T pushValue) in C:UsersPaulDeitelDocuments
examplesch20Fig20_09StackStackStack.cs:line 35
at StackTest.TestPush[T](String name, Stack`1 stack, IEnumerable`1
elements) in C:UsersPaulDeitelDocumentsexamplesch20Fig20_09
StackStackStackTest.cs:line 45
Popping elements from intStack
10 9 8 7 6 5 4 3 2 1
Message: Stack is empty, cannot pop
at Stack`1.Pop() in C:UsersPaulDeitelDocuments
examplesch20Fig20_09StackStackStack.cs:line 49
at StackTest.TestPop[T](String name, Stack`1 stack) in
C:UsersPaulDeitelDocumentsexamplesch20Fig20_09Stack
StackStackTest.cs:line 68
Method Main (Fig. 20.9, lines 17–30) creates the Stack<double> (line 19) and Stack<int> (line 20) objects. Lines 23–29 invoke generic methods TestPush and TestPop to test the Stack objects.
Generic method TestPush (lines 33–53) uses type parameter T (specified at line 33) to represent the data type stored in the Stack. The generic method takes three arguments—a string that represents the name of the Stack object for output purposes, an object of type Stack<T> and an IEnumerable<T> that contains the elements that will be Pushed onto Stack<T>. The compiler enforces consistency between the type of the Stack and the elements that will be pushed onto the Stack when Push is invoked, which is the type argument of the generic method call. Generic method TestPop (lines 56–77) takes two arguments—a string that represents the name of the Stack object for output purposes and an object of type Stack<T>.