Building Stacks with C#

Introduction to Stack In C#

The following article presents a general definition of the stack data structure and its most common functions.This article explores a sample stack implementation as a .NET class in C#, as well as some interesting usage scenarios.

.NET includes a Stack class inside the System.Collections namespace. It is efficient because it is implemented using a System.Collections.ArrayList, so if you need to consume a stack, it is a better idea to use the built in .NET stack class. Just for fun and for educational purposes, the following article presents a simple way to implement a stack and sample stack consumers.

Definition of Stack

A stack is a data structure that allows to add and remove objects at the same position. The last object placed on the stack is the first one to be removed following a Last In First Out (LIFO) data storing method.

Common Functions

The most common functions to manipulate a stack are

• Push(element): Adds a new object to the last position of the stack.
• Pop(): Returns and removes the last object of the stack.
• Peek(): Returns the last object without removing it.
• IsEmpty(): Validates if the stack is empty.

Implementation

There are many ways to implement a stack. I will use an array to keep the demonstration simple, even though you might consider using a linked list to allow dynamic resizing. I will define the maximum size of the stack at compilation time, but you might also define it at runtime. I will use an index to store the last object position (bottom of the stack) at any time.

Each time a Push() operation is done, I validate if the stack has enough space, I increment the index, and add the new object. Each time a Pop() operation is done, I validate if the stack IsEmpty(), I decrease the index, and return the last object. Each time a Peek() operation is done, I validate if the stack IsEmpty(), and I return the last object.

The following sample code illustrates a sample C# stack implementation

using System;

namespace DotNetTreats.DataStructures
{
    public class Stack
    {
        private const int MaxSize = 100;
        private object[] _items = new object[MaxSize];
        private int _currentIndex = -1;

        public Stack()
        {
            // Constructor
        }

        public void Push(object element)
        {
            if (_currentIndex >= MaxSize - 1)
            {
                throw new InvalidOperationException("Stack is full");
            }

            _currentIndex++;
            _items[_currentIndex] = element;
        }

        public object Pop()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException("No elements in stack");
            }

            object element = _items[_currentIndex];
            _items[_currentIndex] = null;
            _currentIndex--;
            return element;
        }

        public object Peek()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException("No elements in stack");
            }
            return _items[_currentIndex];
        }

        public bool IsEmpty()
        {
            if (_currentIndex < 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}

C#

Copy

Listing 1. C# Stack implementation

Usage Scenarios

Scenario 1 : Simple consumer

Once the stack is implemented, a program can consume it. The following console application represents a simple way to consume the stack.

using System;

namespace DotNetTreats.DataStructures
{
    internal class StackConsumer
    {
        public StackConsumer() { }

        [STAThread]
        static void Main(string[] args)
        {
            // Simple stack consumer
            Stack stack = new Stack();
            int x = 9;
            string y = "foo";

            Console.WriteLine("Push 9");
            stack.Push(x);
            Console.WriteLine(stack.Peek().ToString());

            Console.WriteLine("Push foo");
            stack.Push(y);
            Console.WriteLine(stack.Peek().ToString());

            Console.WriteLine("Pop -> foo, 9 is at the top now.");
            stack.Pop();
            Console.WriteLine(stack.Peek().ToString());

            // Expression validator
            ExpressionValidator eval = new ExpressionValidator();
            Console.WriteLine("Write an equation.");
            bool result = eval.Validate(Console.ReadLine());

            if (result)
            {
                Console.WriteLine("Valid");
            }
            else
            {
                Console.WriteLine("Invalid");
            }
        }
    }
}

C#

Copy

Listing 2. C# Stack consumer

Scenario 2 : Expression validation

Equations as well as some string expressions use parenthesis, braces and brackets to open and close parts of the expression. Many programs require validating if in a given string expression, all the opening parenthesis have a matching closing parenthesis (balanced expressions). Some compilers check if functions have balanced opening and closing brackets. Some XML and HTML editors check if all the tags have a corresponding closing tag.

To solve this kind of problems it is recommended to use a stack. The general idea is to parse a string character by character. Each time an opening parenthesis or tag is found, a Push() operation is executed, and each time a corresponding closing parenthesis or tag is found a Pop() operation is executed. If the program finishes parsing the document and the stack IsEmpty() , the equation or expression is valid; otherwise, if the stack has elements, then some matching parenthesis are missing and the expression is invalid.

The following sample represents an expression validation with a stack.

Initial expression: ((X+Y)-1)*2

• The first parenthesis is parsed ((X+Y)-1)*2 and a Push() operation is executed.
• The second parenthesis is parsed ((X+Y)-1)*2 and a Push() operation is executed.
• A closing parenthesis is parsed ((X+Y)-1)*2 and a Pop() operation is executed.
• A closing parenthesis is parsed ((X+Y)-1)*2 and a Pop() operation is executed.

The stack is empty so the expression is valid.

The following sample code validates expressions that use the following characters '( )', '{ }', and '[ ]'.

using System;

namespace DotNetTreats.DataStructures
{
    public class ExpressionValidator
    {
        public bool Validate(string equation)
        {
            Stack stack = new Stack();

            // Iterate through each character in the equation
            for (int i = 0; i < equation.Length; i++)
            {
                char current = equation[i];

                switch (current)
                {
                    case '(': case '[': case '{':
                        stack.Push(current);
                        break;

                    case ')': case ']': case '}':
                        if (stack.IsEmpty())
                        {
                            // If there's nothing to match, it's invalid
                            return false;
                        }

                        char x = (char)stack.Pop();

                        // Check if the opening and closing characters match
                        if ((x == '(' && current != ')') ||
                            (x == '[' && current != ']') ||
                            (x == '{' && current != '}'))
                        {
                            return false;
                        }
                        break;
                }
            }

            // If there are any unmatched opening characters, it's invalid
            if (stack.IsEmpty())
            {
                return true; // The equation is valid
            }

            return false; // There are unmatched opening characters
        }
    }
}

C#

Copy

Listing 3. Expression validation using a C# stack

Conclusion

In this article, I examined and defined the stack data structure. I explained its principal functions, presented a sample .NET stack implementation, and shared two common usage scenarios.

Reference

• Andrew Binstock, John Rex, Practical Algorithms for Programmers, Addison Wesley, 1995.