.NET TREATS & TRICKS

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.

Introduction

.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

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

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.

/// C#

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() {
        }

        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;
            }
        }
    }
}

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.

/// C#

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");
            }
        }
    }
}

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 following sample code validates expressions that use the following characters: ‘( )’, ‘{ }’, and ‘[ ]’.

/// C#

using System;

namespace DotNetTreats.DataStructures{

    public class ExpressionValidator{

        public bool Validate(string equation){
            Stack stack = new Stack();

            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()) {
                            return false;
                        }
                        char x = (char)stack.Pop();
                        if ((x == '(' && current != ')') ||
                            (x == '[' && current != ']') ||
                            (x == '{' && current != '}')) {
                            return false;
                        }
                        break;
                }
            }

            if (stack.IsEmpty()) {
                return true;
            }

            return false;
        }
    }
}

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.

Building Stacks with C#

Summary

Contents

Introduction

Definition

Common functions

Implementation

Usage Scenarios

Scenario 1: Simple consumer

Scenario 2: Expression validation

Conclusion

Reference