Stack

Posted by Abhishek on December 21, 2019

Fundamentals

Stacks are powerful data structures that can help us solve many complex programming problems. Stacks can be used in some use-cases like:

  1. Develop UNDO functionality
  2. Build Compilers
  3. Evaluate Arithmetic Expressions
  4. Develop navigation features in our application (moving forward and backward)

Structure of a Stack

Stacks can be visualized as a stack of books. The peculiarity of a Stack is that items can be added to the stack only on the top & removed only from the top. If you want to access the bottom-most item in the stack, you have to remove the books from the top until you reach the bottom-most item. This principle is called LIFO (Last In First Out).

Stack

Operations that can be performed on a Stack

  1. PUSH – Adds an item to the top of the stack
  2. POP – Removes an item from the top of the stack
  3. PEEK – Returns the item from the top of the stack without removing
  4. ISEMPTY – Returns true if the stack is empty. Otherwise, false.

All the operations can be done in O(1) complexity because these operations are done on the top of the stack. There is no need to iterate.

Coding Exercise: Reverse a String using Stacks

String str = "abcd";
Stack stack = new Stack();
foreach (char ch in str)
{
    stack.Push(ch);
}
StringBuilder builder = new StringBuilder();
while (stack.Count != 0)
{
    builder.Append(stack.Pop());
}
Console.WriteLine(builder.ToString());

Coding Exercise: Check if an expression is balanced

An expression is balanced if the sequence of opening brackets matches with sequence of closing brackets. For example: ((1+2)) is balanced ((1+2>) is not balanced

Solution

public class Expression
{
    private ArrayList leftBrackets = new ArrayList() { ')', ']', '>', '}' };
    private ArrayList rightBrackets = new ArrayList() { '(', '[', '<', '{' };
    public Boolean IsBalanced(string str)
    {
        Stack stack = new Stack();
        foreach (char ch in str)
        {
            if (isLeftBracket(ch))
            {
                stack.Push(ch);
            }

            if (isRightBracket(ch))
            {
                if (stack.Count == 0) return false;

                var poppedBracket = Convert.ToChar(stack.Pop());
                if (!doesBracketsMatch(poppedBracket, ch)) return false;
            }
        }
        return (stack.Count == 0 ? true : false);
    }

    private bool doesBracketsMatch(char left, char right)
    {
        return (rightBrackets.IndexOf(right) == leftBrackets.IndexOf(left));
    }

    private bool isRightBracket(char ch)
    {
        return rightBrackets.Contains(ch);
    }

    private bool isLeftBracket(char ch)
    {
        return leftBrackets.Contains(ch);
    }
}
Block of code in the Main program
Expression exp = new Expression();
System.Console.WriteLine(exp.IsBalanced("((1+2>)"));

Implementation of Stack

Stack using Arrays

public class Stack
{
    private int[] items;
    private int count;
    public Stack()
    {
        items = new int[2];
    }

    public void push(int number)
    {
        if (items.Length == count)
        {
            int[] newItems = new int[count * 2];
            for (int i = 0; i < count; i++)
            {
                newItems[i] = items[i];
            }
            items = newItems;
        }
        items[count++] = number;
    }

    public int peek()
    {
        if (count == 0)
            throw new System.Exception("Nothing to Peek");
        return items[count - 1];
    }

    public int pop()
    {
        if (count == 0)
            throw new System.Exception("Cannot Pop");
        return items[--count];
    }

    public bool isEmpty()
    {
        return count == 0;
    }
}
Block of code in the Main program
Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
System.Console.WriteLine(stack.peek());
stack.pop();
System.Console.WriteLine(stack.peek());
System.Console.WriteLine(stack.isEmpty());

Stack using Linked List

public class Stack2
{
    private Node First;
    private Node Last;
    private int size;

    public int Count
    {
        get { return size; }
    }
    public class Node
    {
        public int Value;
        public Node Next;

        public Node(int value)
        {
            Value = value;
        }
    }

    public bool isEmpty()
    {
        return First == null;
    }

    public void push(int number)
    {
        var newNode = new Node(number);
        if (isEmpty())
        {
            First = Last = newNode;
        }
        else
        {
            Last.Next = newNode;
            Last = Last.Next;
        }
        size++;
    }

    public int peek()
    {
        if (isEmpty())
            throw new System.Exception("Nothing to Peek");
        return Last.Value;
    }

    public int pop()
    {
        if (First == Last)
        {
            First = Last = null;
        }
        else
        {
            var previous = GetPrevious(Last);
            Last = previous;
            Last.Next = null;
        }
        if (isEmpty())
            throw new System.Exception("Cannot Pop");
        size--;
        return Last.Value;
    }

    private Node GetPrevious(Node node)
    {
        var currentNode = First;
        while (currentNode != null)
        {
            if (currentNode.Next == node)
                return currentNode;
            else
                currentNode = currentNode.Next;
        }
        return null;
    }
}
Block of code in the Main program
Stack2 stack = new Stack2();
stack.push(10);
stack.push(20);
stack.push(30);
System.Console.WriteLine(stack.peek());
stack.pop();
System.Console.WriteLine(stack.peek());
System.Console.WriteLine(stack.isEmpty());

Thanks for reading this post. Enjoy !!
Share on: