You want to use the Stack<T> collection in your C# program for a powerful and simple LIFO (last-in-first-out) data structure. This can help you develop parsers quickly and also replace complex recursive algorithms. Here we see ways you can use Stack and its members in methods and simple loops in your C# programs.
LIFO:
The last element added (with Push) to Stack is the first one removed (with Pop).
Push elements
Usually, the first action you need to do on Stack is Push elements into it. The word Push is a computer science term that means "add to the top." The example we see next returns a new Stack of integers from a method. Then, it writes each value of the stack to the Console is a loop.
Program that creates new Stack of integers [C#]
using System;
using System.Collections.Generic;
class Program
{
static Stack<int> GetStack()
{
Stack<int> stack = new Stack<int>();
stack.Push(100);
stack.Push(1000);
stack.Push(10000);
return stack;
}
static void Main()
{
var stack = GetStack();
Console.WriteLine("--- Stack contents ---");
foreach (int i in stack)
{
Console.WriteLine(i);
}
}
}
Output
--- Stack contents ---
10000
1000
100
Important parts. In the Main entry point, the stack local variable is assigned to a new Stack containing three integers. The ints were added with the 10000 last. Next, in Main, the values are printed out to the Console. You can see that 10000 is displayed first. This is explained by the LIFO concept—last in first out.
Pop elements
Here we see the Pop method on stack, and also the Peek method. When you call Pop, the elements from the top of the Stack is returned, and the element is removed from the collection. The example here uses the same stack as above, which means Pop returns 10000. It also uses Peek, which does the same thing as Pop but does not remove the element.
Program that uses Pop method on Stack [C#]
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Get the stack [See above definition of this method]
Stack<int> stack = GetStack();
// Pop the top element
int pop = stack.Pop();
// Write to the console
Console.WriteLine("--- Element popped from top of Stack ---");
Console.WriteLine(pop);
// Now look at the top element
int peek = stack.Peek();
Console.WriteLine("--- Element now at the top ---");
Console.WriteLine(peek);
}
}
Output
(These were the LAST elements added; see the GetStack method)
--- Element popped from top of Stack ---
10000
--- Element now at the top ---
1000
Notes. The Pop and Peek methods both act on the top of Stack, meaning the element added most recently. They also both return that top value. However, Peek does not remove the element from the Stack collection. It only gets the value—in other words, it 'peeks' at the value. Pop actually removes the reference entirely. If you call Pop, then afterwards Peek and Pop will return the next value when they are called.
Clear and count
Here we see examples of how you can use Clear and Count on your Stack. These methods won't raise exceptions unless your Stack reference is null. The Count property is used without parenthesis, while Clear() is a parameterless method. The example receives the Stack used in the above examples, then counts it, clears it, and finally counts it again.
Program that uses Clear and Count methods [C#]
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Get the stack [See method definition above]
Stack<int> stack = GetStack();
// Count the number of elements in the Stack
int count = stack.Count;
Console.WriteLine("--- Element count ---");
Console.WriteLine(count);
// Clear the Stack
stack.Clear();
Console.WriteLine("--- Stack was cleared ---");
Console.WriteLine(stack.Count);
}
}
Output
--- Element count ---
3
--- Stack was cleared ---
0
Using null stacks. First, the value null is allowed in Stacks with reference types such as string. You can also assign your Stack to null instead of calling Clear. This changes the performance characteristics slightly, because the contents are not changed; instead the reference is unrooted in the garbage collector.
Exceptions
You will probably encounter exceptions the first time you use Stack. When you call Pop or Peek on your Stack, the runtime will throw an exception if the Stack has zero elements. To work around this problem, you must check the Count property. The next example shows how you can catch the exception raised by this situation, and then shows the right way to deal with it.
Program that uses Stack incorrectly and then correctly [C#]
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Create an empty Stack.
var stack = new Stack<int>();
try
{
// This throws an exception.
int pop = stack.Pop();
}
catch (Exception ex)
{
Console.WriteLine("--- Exception raised by Pop ---");
Console.WriteLine(ex.ToString());
}
// Here we Pop the stack safely.
if (stack.Count > 0)
{
int safe = stack.Pop();
}
else
{
Console.WriteLine("--- Avoided exception by using Count method ---");
}
}
}
Output
--- Exception raised by Pop ---
System.InvalidOperationException: Stack empty.
...
...
--- Avoided exception by using Count method
Copy and search
Here we see that you can use different constructors of Stack to streamline your code. It accepts an IEnumerable parameter, which is an interface that most collections implement. Here we use that constructor. Additionally, we search the Stack with the Contains method. The Contains method on Stack returns true if the element is found.
Program that uses the Stack constructor [C#]
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// An example string array.
string[] values = { "Dot", "Net", "Perls" };
// Initialize a Stack from an array.
var stack = new Stack<string>(values);
// Display the Stack.
Console.WriteLine("--- Stack contents ---");
foreach (string value in stack)
{
Console.WriteLine(value);
}
// See if the stack contains "Perls"
Console.WriteLine("--- Stack Contains method result ---");
bool contains = stack.Contains("Perls");
Console.WriteLine(contains);
}
}
Output
--- Stack contents ---
Perls
Net
Dot
--- Stack Contains method result ---
True
Using Contains with reference types. The Stack generic collection searches the elements with Contains by using the interface defined in the collection. Therefore, the object reference is not compared in the example; instead, the string contents are. This means it does what you intuitively expect.
More details
Here we note some of the other methods on Stack in System.Collections.Generic. You can copy your Stack to a new array with ToArray(). Also, you can use TrimExcess if your Stack is using too much memory. Internally, TrimExcess will check the Stack's fill rate, and then resize the internal array.
Internal implementation of Stack. When looking inside Stack with IL Disassembler, we can see that it is implemented with an array of type T[]. This is type you specify in the declaration. Stack is very simple inside, and it is basically a wrapper around an array. No boxing or unboxing will occur.
IL Disassembler Tutorial
Parsers
I have used Stack for developing simple parsers, such as HTML parsers and validators. Many parsers push new elements they encounter, and then when they exit the element, they pop elements. This makes it easy to validate HTML and wiki markup.
Validate XHTML
Summary
We saw examples of how you can use Stack<T>. The Stack collection is in the System.Collections.Generic namespace, and provides a simple wrapper on an array. It is a useful abstraction of the classic stack data structure, and makes the development of parsers and implementation of recursive methods easier.
No comments:
Post a Comment