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
- 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 '[ ]'.
/// 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.