Stack is a linear data structure in which there are 3 operations defined: adding an element at the top of the stack (push), removing an element from the top of the stack (pop) and inspect the element from the top without removing it (peek). All these operations are very fast – it takes a constant time to execute them. The stack does not support the operations search and
access through index. The stack is a data structure which has a LIFO behavior (last in, first out). It is used when we have to model such a behavior – for example, if we have to keep the path to the current position in a recursive search. Use a stack when you have to implement the behavior “last in, first out” (LIFO).
Like an List, a stack has an add and get method, with a slight difference in behavior.
To add to a stack data structure, you need to use the Push() call, which is the Add() equivalent of an List. Retrieving a value is slightly different. The stack has a Pop() call, which returns and removes the last object added. If you want to check the top value in a Stack, use the Peek() call.
There are two formats to define a Stack in C#:
|
1 2 |
Stack stack = new Stack(); Stack<string> stack = new Stack<string>(); |
The difference between them is that the simple Stack structure will work with Objects, while the Stack<T> one will accept only a specified type.
Here is the C# code to add and traverse through a Stack data structure:
|
1 2 3 4 5 6 7 |
Stack<string> stack = new Stack<string>(); stack.Push("one"); stack.Push("two"); stack.Push("three"); while (stack.Count > 0) Console.WriteLine(stack.Pop()); |
If you run the above C# code, you see that the list is returned in the order: “three”, “two”, “one”.
These are the main methods of a Stack:
Push() – 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.”
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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); } } |
Pop(), Peek() – Here we Pop and Peek. When you call Pop(), the elements from the top of the Stack is returned, and the element is removed from the collection.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
using System; using System.Collections.Generic; class Program { static void Main() { // Get the stack. 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); } static Stack<int> GetStack() { Stack<int> stack = new Stack<int>(); stack.Push(100); stack.Push(1000); stack.Push(10000); return stack; } } |
Clear() – is a parameterless method. It erases the Stack’s contents.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
using System; using System.Collections.Generic; class Program { static void Main() { // Get the stack 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); } static Stack<int> GetStack() { Stack<int> stack = new Stack<int>(); stack.Push(100); stack.Push(1000); stack.Push(10000); return stack; } } |
Contains() – We search the Stack with the Contains() method. The Contains method on Stack returns true if the element is found.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
using System; using System.Collections.Generic; class Program { static void Main() { // An example string array. string[] values = { "one", "two", "three" }; // Copy an array into a Stack. 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 "three" Console.WriteLine("--- Stack Contains method result ---"); bool contains = stack.Contains("three"); Console.WriteLine(contains); } } |
The most important property of a Stack is:
Count – gives the number of elements in a Stack.
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(). When assigning to null, the contents are not changed. Instead the reference is unrooted in the garbage collector. 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. Here we catch the exception raised by this situation (we haven’t learn about exceptions yet, but just consider them a special kind of errors):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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 safely Pop the stack. if (stack.Count > 0) int safe = stack.Pop(); else Console.WriteLine("--- Avoid exceptions by using Count method! ---"); } } |
Tags: data structures, stack
