Learning data structures – Stack in depth in C#
source link: http://codereform.com/blog/post/learning-data-structures-stack-in-depth-in-c/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Learning data structures – Stack in depth in C#
What is a stack and how it works? What is an Abstract data type and how it’s related with the stack? In this post we’ll explore the stack data structure, I’ll go through the theory behind, explain why stacks are important programming tools, create a custom implementation of a stack with an array from scratch and finally, go through some interesting examples. By the end of this post I do hope that you’ll have a very good understanding of how a stack works under the hood and how you can use it to tackle day-to-day programming problems.
Source code
Code outlined in this article can be found on my GitHub repository.
Stack as a data structure
Usually data structures such as arrays, are used to store data, making it easy to insert, delete or access specific elements. But these data structures are not very useful in more complex scenarios, such as developing complex algorithms. We need something else, something that can be used to help the developer perform specific set of actions, rather a full-blown mechanism to store data.
Stack is such programming tool, it’s an abstract data structure, which allows data to be accessed one at a time in a specific order.
What is an abstract data structure though? Let’s try to give it a shot with an analogy. Some programming languages have build-in classes for several collections, like Lists, HashMaps or Dictionaries, etc. One example is the .NET Framework’s List, which is defined in the System.Collections namespace. The implementation is completely hidden from the end-developer, who is just using the List to perform some programming tasks. The internal implementation can be anything, it can be an array for instance, but as an end-user, most likely you don’t care as long it is fast enough for the job.
This is called an abstract data structure and the same applies for the Stack or Queue, they are ADT’s, meaning their internal implementation could use other data structures, like arrays or lists (yes, a stack can also be implemented by a linked list).
How it works
In order to better understand what is a stack, we can think an analogy. Let’s imagine some pancakes on a plate, like on this blog’s cover. There are, let’s say, 5 pancakes, one on top of the other. More pancakes are on the way, so they will be placed on top of the already existing ones. This is analogous to the PUSH operation of a stack. 5 additional pancakes are added, one at a time on the plate. We now have 10 pancakes, one on top of the other.
It’s time to eat! You grab the topmost pancake from the stack with your fork and you place it on your plate. So, you grabbed the item on the top of the stack, which is analogous to the POP operation. The pancake plate has 9 pancakes in total now. However, you feel hungry, so you pick another pancake from the stack, leaving in total 8 pancakes behind.
Notice that the pancakes are picked from the plate in the opposite order they were placed. The first pancake that was placed on the plate will be eaten last. This is why the stack data structure is usually called a LIFO data structure, with LIFO being the acronyms of “Last-In First-Out”, meaning the last item that was inserted into this data structure will be the first to accessed/removed.
A more technical approach
The example above might be a bit silly, however it makes easy to understand and grasp the concept of the stack. I’ll try to give a more technical explanation on the stack data structure and in the following examples we’ll see how it really works.
As we’ve already discussed, the stack provides access to the top-most stored item, which is always the last item inserted. New items will be stored on the top, above the previous top item, in the order each is inserted. This is the PUSH operation, which pushes items at the top of the stack.
When we want to consume items from the stack, we remove the topmost item, with the new top pointing to the immediate previous item. This is the POP operation which consumes items from the top of the stack.
Some implementations of the stack support operations like PEEK, which is similar to POP but it does not remove the item from the top, it just returns it without modifying the stack.
Complexity
The complexity of the stack is O(1), which means it’s very fast when accessing/inserting/removing items. Why is that though? Well, when using the stack, all we do is to PUSH or POP, operations that don’t need to perform any search or comparison or copy, they just insert or remove an item from the stack’s top. The algorithm knows where the topmost item is, usually by storing a pointer to the stack’s top, and the access time is lighting fast. Size of the stack does not matter, it can be millions of items (of course your machine should be able to handle the memory requirements for such data structure or it can be implemented with Lazy evaluation which supports infinite size data structures).
Every time your program runs, a stack is used
Did you know that most microprocessors have designs that are based on a stack? When you run your program, you usually create classes and methods, and some of your methods might also have parameters. On a method call, the return address and the parameters are stored in a stack. When that method returns, all these info are popped from that stack. Same applies for local variables. Of course this is a high overview of how the microprocessor stack is used by a programming language and it might differ from language to language, so you might need to consult your language low-level documentation for more specific detail.
Implementing a stack
In a first attempt to understand how a stack works, we’ll try to create one from scratch. The requirements are pretty much straightforward, we need to store some items and any new item is stored on top of the others. An array is perfect candidate for this kind of store. We will keep track of the topmost item with an index, it will be increased when new item is pushed and decreased when popped. When we want to pop something from that store, we take the item that lies on the top index and decrease the index to point one item below. The peek operation will be similar to pop, however it will not remove the item from the stack. Finally, we’d also need a property to indicate whether the stack is empty or not.
This is a simple UML class diagram with a single class, the Stack<T> class we are going to implement.
So, first I will create a generic class, named Stack<T>. I would like to receive the size of the stack from the constructor and initialize a generic array with that size. This will be the maximum size of the stack. Default value will be 16.
private readonly T[] _stack; private readonly int _size; private int _topMostItemIndex = -1;
public Stack(int size = 16) { _size = size; _stack = new T[size]; }
The _stack array will be the implementation of our stack, as already mentioned, I will use an array. The _size field stores the maximum size of the stack and the _topMostItemIndex field is the index of the top item in the stack. It will be increased when new item is pushed in the stack and decreased when an item is popped.
The PUSH operation is inserting an item in the stack. If the stack is full, an exception will be thrown.
public void Push(T value) { if (IsFull) { throw new Exception("Stack is full"); }
_stack[++_topMostItemIndex] = value; }
As you see in the example above, I am inserting the new value at the topmost index of the stack, which is increased by 1, to point to the new top.
The POP operation is fetching the topmost item and decreases the index to point to the previous item, which is the new top.
public T Pop() { if (IsEmpty) { throw new Exception("Stack is empty"); }
return _stack[_topMostItemIndex--]; }
As you noticed, I decrease the index by 1, only after I retrieve the top item.
The PEEK operation is similar to the POP, however it does not decrease the topmost index.
public T Peek() { if (IsEmpty) { throw new Exception("Stack is empty"); }
return _stack[_topMostItemIndex]; }
IsEmpty and IsFull
The IsEmpty (public) and IsFull (private) implementations are very trivial and they are just comparing the topmost index with the total size of the stack in order to reach to a conclusion.
public bool IsEmpty => _topMostItemIndex == -1; private bool IsFull => _size == _topMostItemIndex + 1;
That’s the bare minimum to build your own custom stack. Following is the complete implementation of the above.
public class Stack<T> { private readonly T[] _stack; private readonly int _size; private int _topMostItemIndex = -1;
public Stack(int size = 16) { _size = size; _stack = new T[size]; }
public bool IsEmpty => _topMostItemIndex == -1; private bool IsFull => _size == _topMostItemIndex + 1;
public void Push(T value) { if (IsFull) { throw new Exception("Stack is full"); }
_stack[++_topMostItemIndex] = value; }
public T Pop() { if (IsEmpty) { throw new Exception("Stack is empty"); }
return _stack[_topMostItemIndex--]; }
public T Peek() { if (IsEmpty) { throw new Exception("Stack is empty"); }
return _stack[_topMostItemIndex]; } }
In the katas coming next, I will use this implementation of the stack instead of the .NET Framework. If you’d like you can use .NET Framework’s, there will be virtually no difference if you choose either one.
.NET Framework Stack class
The .NET Framework already has an implementation of the stack, in the System.Collections namespace, but also it has a generic implementation in the System.Collections.Generic namespace. Click on the images to view maximized.
And this is the generic Stack.
As you have already noticed, our custom implementation is not very much different from .NET’s implementation. A stack is a stack anyways, it is defined by some standard operations and that’s exactly what we’ve implemented so far, a Push and a Pop method are enough for a minimum implementation.
Katas
Next, I am going to demonstrate some programming katas. A code kata is a programming exercise you can do to improve your skills. I won’t demonstrate how to write the unit tests in a TDD approach though, however the code, along with the tests, can be found on GitHub. For a good course on TDD I definitely suggest Mark Seemann’s Outside-In Test-Driven Development in Pluralsight.
Following katas demonstrate some advanced use cases and can be particularly useful in interviews. Many employers require some programming quiz or tests in order to verify the candidate’s skills. It’s like hiring a magician. You’d like to see a couple of tricks before hiring him, wouldn’t you?
Reversing a word
That’s one of the most standard katas you’d be prompted to solve. Using a stack to solve this problem seems trivial.
Given a string input, that reads from left to right, create a method that returns the same string, however with its characters reversed, like reading it from right to left. An example could be with the input “pancakes”, the result should be “sekacnap”.
Okay, from the description, we understand that we need a method that will receive a string input and return a string, though it will be the input reversed. We’ll push each of the string characters in a stack, and then, we’ll pop each one of them. Remember, when pushing an item in the stack, we are placing it at the stack’s top. If we push each character, reading from left to right in the stack, then the last character in the word will be at the top of the stack. If we start popping out the stored items, we’ll pop the last item first, then the one before last, etc., until we remove every character stored in the stack.
public static class Reverser { public static string Reverse(string word) { // Create the stack var stack = new Stack<char>(); // Insert each character from the string input in the stack foreach (var character in word) { stack.Push(character); }
// Pop characters from the stack // and store in a StringBuilder var builder = new StringBuilder(); while (!stack.IsEmpty) { builder.Append(stack.Pop()); }
return builder.ToString(); } }
A nice kata should be accompanied by some unit tests, to verify its theory. As I already mentioned, I won’t go into TDD’s specifics, however I will show some basic unit tests to verify the kata. Generally, you should try and implement a trivial test case, called the ice-breaker, and along the way you will be able to write more test cases, going from red to green. Following, I’ve implemented an XUnit theory for the Reverse method of the kata.
[Theory] [InlineData("a", "a")] [InlineData("ab", "ba")] [InlineData("george", "egroeg")] [InlineData("kata", "atak")] [InlineData("stack", "kcats")] [InlineData("eye", "eye")] // This is a palindrome! public void ShouldReverseWordSuccessfully(string input, string expected) { // Arrange | Act var result = Reverser.Reverse(input);
// Assert Equal(expected, result); }
Bracket matching
Another standard kata. Imagine that you are building a static code analysis tool, that verifies that your program compiles, by checking if opened brackets have a matching closing one.
In this kata, we’ll support 3 kinds of brackets, the {}, the [] and (); requiring every opening bracket to match a closing one, as shown in the pairs earlier. Let’s see some examples:
c[d]is correct.hiis correct.a{b(c)is not correct.a{b[c]d}eis correct.[{hi(george]})is not correct.
What we’ll need to do is to create a method that receives a string as input and returns a boolean. Then, we’ll go through the string’s characters and if we find an opening bracket, like {, [ or (, we’ll push it in the stack. If we find a closing bracket, like }, ], ), we then pop the opening bracket from the stack and compare it with the current closing character. If the pair matches we move forward else we return false. For any other character, we just ignore it and move forward.
This works beautifully with a stack, because from the requirements, the opening bracket, should be the first to close, which resembles the LIFO characteristic of the stack.
This is how it would be implemented with a stack.
public static class Analyzer { public static bool HasValidOpeningClosingBrackets(string input) { var stack = new Stack<char>(input.Length); // Test each character in string input foreach (var character in input) { switch (character) { // When opening bracket, push it in stack case '{': case '[': case '(': stack.Push(character); break;
// When closing bracket, pop it and test it case '}': case ']': case ')': var stored = stack.Pop(); // If the popped item does not match, check has failed if (stored == '{' && character != '}' || stored == '[' && character != ']' || stored == '(' && character != ')') { return false; } break; default: break; } }
// Check hasn't failed yet, input is okay return true; } }
A simple unit test is shown below, which is an XUnit theory, verifying several inputs against the HasValidOpeningClosingBrackets method.
public class HasValidOpeningClosingBrackets { [Theory] [InlineData("hi", true)] [InlineData("{}", true)] [InlineData("[}", false)] [InlineData("{hi(george)}", true)] [InlineData("{hi(george]}", false)] [InlineData("[{hi(george]})", false)] [InlineData("([{[}}])", false)] public void ReturnsExpectedOutputForStringWithBrackets(string input, bool expected) { // Arrange | Act var result = Analyzer.HasValidOpeningClosingBrackets(input);
// Assert Equal(expected, result); } }
Undoing operations using the command pattern
This is a code example involving the Command Design Pattern, which supports undo operations. A stack is a great candidate to support this scenario. I won’t include any unit tests for this, however, I’ve included a simple Windows Forms application that demonstrates the following functionality.
We want to create an application that can draw some shapes on screen, with choices among squares, rectangles and triangles. As a requirement, our application needs to perform an undo operation, in which we’ll remove the previous shape that we’ve drawn on the screen. Actually, we want to be able to perform undo operations as long as the canvas has shapes and these will be undone in the same order they had been drawn.
First, let’s start by defining the command pattern, as it is cited in the Design Patterns book.
Encapsulate a request as an object, thereby letting you parameterize clients with different requests, queue or log requests, and support undoable operations.
What the command pattern does, is that it transforms requests into objects, decoupling the object that invokes the operation from the one having the knowledge to perform it. The object that issues the request only knows how to issue it, but not how the request is carried out, and that’s the heart of this pattern. Usually, the command pattern supports one interface, ICommand, which exposes a single Execute method (of course it can be named differently if it makes sense).
One of the many uses of the command pattern, is the support for undo operations. When the Execute method is called, the state is stored internally, in the command itself. Now that it’s stored, we can easily reverse it, if we want to, by calling the Undo method, another method that we need to add to the ICommand interface to support undo. This method will reverse the effect of the Execute, using the stored state. We need one more thing though and that’s a history list. Usually the application holds a list of the executed commands in the order they were executed. This way we can support unlimited undo and redo levels, by traversing back and forth in the history list.
In our application, we’ll only support undo and a stack will be storing the executed commands, playing the role of the history list.
For this demo, I will build a Windows Forms desktop application. It will have 3 buttons which correspond to each of the 3 commands and an undo button to reverse the command effects. User will draw a shape on canvas when clicking with the mouse.
Coming up is a UML diagram of the application showing all the participants.
Commands
It’s time to get dirty. First, I have to define the ICommand interface, and I want a Draw (executes the command) and an Undo method (reverses the operation).
public interface ICommand { void Draw(); void Undo(); }
Awesome, now its time to create the commands. The application supports 3 shapes, rectangle, square and triangle, so I will create a DrawRectangleCommand, DrawSquareCommand and DrawTriangleCommand. Following is the DrawRectangleCommand implementation.
I’ve omitted most of the code, because I would like to focus on the Draw and Undo methods. In Draw, we first need to save the current state before executing the command. I am just saving each pixel color in the area where the shape is drawn. I will use these pixel colors later, in the Undo method to reverse the shape drawing.
public void Draw() { // Save state SavePreviousState();
// Carry out the command execution var brush = new SolidBrush(_color); var rectangle = new System.Drawing.Rectangle(_point.X, _point.Y, Width, Height); _graphics.FillRectangle(brush, rectangle); }
// Saving all pixels in the area we are going to draw // We are storing the color of each pixel // When we perform an undo, all pixels will be restored to initial state private void SavePreviousState() { for (int i = _point.X; i < _point.X + Width; i++) { for (int j = _point.Y; j < _point.Y + Height; j++) { _previousState.Add(_bitmap.GetPixel(i, j)); } } }
The Undo method is running through each pixel of the shape in the canvas, and resets the color back to its previous state, the one before the command executed.
// Setting each pixel that was drawn // back to its previous color public void Undo() { var points = 0; for (int i = _point.X; i < _point.X + Width; i++) { for (int j = _point.Y; j < _point.Y + Height; j++) { _bitmap.SetPixel(i, j, _previousState[points++]); } } }
Similar functionality has been applied for the DrawSquareCommand and DrawTriangleCommand, check them out on GitHub.
Client application
The client is a simple windows form application. Once again, I will show only the important bits, for more please check on GitHub.
Three are the most important things I want to show. One is the history list, a Stack of ICommand, which stores each command in the order it was executed. I am using the .NET Framework’s Stack in this example. Next thing I want to show is the mouse down handler, which instantiates a command, executes it and then stores it in the history list. Finally, is the undo click handler, which pops a command from the stack and reverses the operation by calling its Undo method.
public partial class MainForm : Form { // Code omitted for brevity // The history list private Stack<ICommand> _commands = new Stack<ICommand>(); // Code omitted for brevity // Draws the shape on canvas private void canvas_MouseDown(object sender, MouseEventArgs e) { // We get the command based on the shape selection // and we draw it in the X, Y coordinates var command = GetCommand(e.X, e.Y); command.Draw();
// We store the command in the history list _commands.Push(command); // Refresh the UI (trivial code, omitted for brevity) RefreshWindow(); } }
The GetCommand private method is only instantiating a command based on the user’s selection, which is stored in the _activeShape private field. If user had selected a Triangle, then the DrawTriangleCommand would have been instantiated.
private ICommand GetCommand(int x, int y) { // Using pattern matching to find shape and create the command switch (_activeShape) { case var square when square == typeof(Square): return new DrawSquareCommand(_bitmap, new Square(100, 100), new Point(x, y)); case var rectangle when rectangle == typeof(Rect): return new DrawRectangleCommand(_bitmap, new Rect(100, 50), new Point(x, y)); case var triangle when triangle == typeof(Triangle): return new DrawTriangleCommand(_bitmap, new Triangle(70, 35), new Point(x, y)); default: throw new ArgumentOutOfRangeException("Cannot recognize shape."); } }
When the undo button is pressed, the undoButton_Click handler will be invoked in order to reverse the command operation. It only needs to pop the command from the stack and call the Undo method of the same.
// Undo button handler private void undoButton_Click(object sender, EventArgs e) { // If history list (stack) contains any command if (_commands.Any()) { // Pop it out and undo it var command = _commands.Pop(); command.Undo(); } // Refresh UI (trivial operation, omitted for brevity) RefreshWindow(); }
Let’s see all these in action
Summary
In this post we’ve discussed about the stack as a specialized data structure, used mostly as programming tool. A stack broadly supports the PUSH and POP operations, which insert or remove an item from its top. All stack operations are very fast with constant complexity, O(1). We might not realize it, but a stack is an important data structure, broadly used in microprocessor architectures and help us run our programs by storing information about method calls, parameters, local variables, etc.
Through our examples, we implemented a stack using an array. In future posts I will show how to create a stack using a linked-list, proving its ADT nature. We also went through some interesting katas, which I included for reference and fun, however quite often they’ve been used as programming challenges in interviews, but nonetheless they are also particularly useful in sharping your coding your skills.
I plan to make another post on the same topic, going through some more advanced techniques, converting infix mathematical expressions to postfix and back again, which can be great help for interviews and generally for enriching existing knowledge as a fun exercise.
If you liked this blog post, please like, share and subscribe! For more, follow me on Twitter.
This post is part of the Learning data structures series
- Learning data structures – Arrays in C#
- Learning data structures – Search algorithms for arrays
- Learning data structures – Stack in depth in C#
- Learning data structures – Tuples in C# and F#
- Learning data structures – Queue in depth in C#
- Learning data structures – Priority queue
- Learning data structures – Simple sorting algorithms
- Learning data structures – Linked lists
- Learning data structures – Doubly linked lists
- Learning data structures – Recursive algorithms
- Learning data structures – Advanced sorting algorithms
- Learning data structures – Binary trees
- Learning data structures – Heap
- Learning data structures – Hash tables
- Learning data structures – Graphs
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK