Data Structures — Stack

A Stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last item added to the stack will be the first item to leave the stack. In this article, I present how to use this data structure in .NET.

For demonstration purposes, I created a console application using .NET. The complete code can be found on my GitHub.

The Stack data structure provides a series of methods that you can use to work with it. These are the main methods:

• Push: this method inserts elements to the top of the stack.
• Pop: this method removes and returns the element at the top of the stack.
• Peek: this method returns the top element at the top of the stack (without removing it).
• Count: this method gets the number of elements contained in the stack.
• Contains: this method returns whether an element is in the stack.

In the image below you can see what happens when the Pushand Pop operations are executed:

• The Push operation added the element 3 at the top of the stack.
• The Peek operation returned the top element of the stack (element 3).
• The Pop operation removed the top element of the stack (element 3).

Creating a Stack

To create a Stack in C#, you can declare it by using the generic class Stack<T>, where T is the type of elements that will be stored in the stack. For example, below I’m creating a Stack of string elements:

Stack<string> stackDemo = new Stack<string>();

// or

var stackDemo = new Stack<int>();

Adding elements to the Stack

In the code below I’m adding three elements to the stackDemo:

stackDemo.Push("Melon");
stackDemo.Push("Banana");
stackDemo.Push("Kiwi");

For each Push operation, the element will be added to the top of the stack:

So after adding these three elements, the “1- Melon” (the first element to be added) is at the bottom of the stack, and the “3- Kiwi” (the last element to be added) is at the top of the stack

When printing the values of this stack, this is the output:

Kiwi
Banana
Melon

Removing the top element from the Stack

The Pop operation can be used to remove the top element from the stack. For example:

stackDemo.Pop();

When executing the Pop operation, the last element that was added to the stack (“Kiwi) will be removed:

When printing the elements of the stack after executing the Pop method, this is the output:

Banana
Melon

Getting the top element from the Stack

To retrieve the top element from the Stack, you can use the Peek method:

string topItem = stackDemo.Peek();

Now when printing the topItem, this is the output:

Banana

Contains operation

To check if an element exists in the Stack, you can use the Contains method, and pass as a parameter the value that you want to search:

var containsBanana = stackDemo.Contains("Banana");
var containsApple = stackDemo.Contains("Apple");

When printing containsBanana and containsApple, this is the output:

containsBanana: True
containsApple: False

Retrieving the number of elements in a Stack

To get the amount of elements that exist in a Stack, or to check if the Stack is empty or not, you can use the Count method:

var numberOfElements = stackDemo.Count;

When printing the numberOfElements, the output is:

numberOfElements: 2

Useful cases for using a Stack

The Stack data structure is useful for scenarios such as:

• Undo/redo operations: think of a text editor where you can undo and redo actions. Using a stack is an efficient way to manage the history of operations, allowing users to revert changes or reapply them.
• Browser History Navigation: Browsing through web pages involves moving backwards and forward. Stacks can facilitate this navigation by maintaining a history of visited pages.
• Recursion: Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Each recursive call creates a new activation record on the call stack. The stack’s Last-In-First-Out (LIFO) property manages the recursive function calls, ensuring proper memory management.
• Calling Functions (Call Stack): Function calls use the call stack. When a function is called, its context, including parameters and variables, is pushed onto the stack. As functions finish, they are popped off, allowing the program to resume execution from the caller. This LIFO process mirrors the behaviour of a stack.
• Expression Evaluation and Parsing: Stack helps convert infix expressions to postfix or prefix notation (Reverse Polish Notation or Polish Notation), ensuring proper evaluation by following operator precedence rules.
• Depth-First Search (DFS): DFS is a graph traversal algorithm that explores each branch as far as possible before backtracking. Stacks are commonly used for iterative DFS implementation, systematically managing nodes to ensure traversal of the graph’s vertices and edges.
• Backtracking Algorithms: Applications involving backtracking, such as file directory traversal or maze-solving algorithms, rely on stacks to track and manage potential solutions.

Conclusion

The Stack data structure offers a simple but powerful mechanism for managing data in a LIFO manner. Stacks can be useful in a range of scenarios, including managing undo/redo operations, navigating browser history, handling recursion, managing function calls (call stack), implementing graph traversal algorithms, and converting infix expressions to postfix or prefix notation.

This is the link for the project in GitHub: https://github.com/henriquesd/stackdemo

If you like this demo, I kindly ask you to give a ⭐️ in the repository.

Thanks for reading!

References

Stack<T> Class — Microsoft Docs