Building Stacks with C#

Summary

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

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:

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

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.

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

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

  1. The first parenthesis is parsed ((X+Y)-1)*2 and a Push() operation is executed.
  2. The second parenthesis is parsed ((X+Y)-1)*2 and a Push() operation is executed.
  3. A closing parenthesis is parsed ((X+Y)-1)*2 and a Pop() operation is executed.
  4. A closing parenthesis is parsed ((X+Y)-1)*2 and a Pop() operation is executed.
  5. The stack is empty so the expression is valid.

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

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.