Ashok
Ashok's Blog

Follow

Ashok's Blog

Follow

Stacks

Ashok's photo
Ashok
·Jan 6, 2020·
Play this article

Stack is an ordered list where insertion and deletion can happen at only one end. Hence, it is known as Last In, First Out (LIFO) or First In, Last Out (FILO). Insertion and deletion in stacks are called PUSH and POP respectively. PEEK returns the last added element without removing it from the stack.

Lifo_stack.png

By Vectorization: OmenBreeze - Own work based on: Lifo stack.png by Maxtremus, CC0, commons.wikimedia.org/w/index.php?curid=115..

A stack can only be accessed from one end, so random access is not possible as in an array.

Stack implementation using LinkedList

public class Stack<T> : IEnumerable<T>
{
    LinkedList<T> list = new LinkedList<T>();
    public void Push(T Value)
    {
        list.AddFirst(Value);
    }
    public T Pop(T Value)
    {
        T value = list.First.Value;
        list.RemoveFirst();
        return value;
    }
    public T Peek()
    {
        if (list.Count == 0) throw new InvalidOperationException("The Stack is empty");

        return list.First.Value;
    }

    public void Clear()
    {
        list.Clear();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return list.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Stack implementation using Array

public class Stack<T> : IEnumerable<T>
{
    private const int _defaultCapacity = 4;
    int _size;

    T[] items = new T[_defaultCapacity];


    public void Push(T value)
    {
        if (_size == items.Length)
        {
            T[] newArray = new T[2 * items.Length];
            Array.Copy(items, newArray, items.Length);
            items = newArray;
        }
        items[_size] = value;
        _size++;
    }

    public T Pop()
    {
        if (_size == 0) throw new InvalidOperationException("Stack is empty");

        _size--;
        return items[_size];
    }

    public T Peek()
    {
        if (_size == 0) throw new InvalidOperationException("Stack is empty");

        return items[_size - 1];

    }

    public void Clear() { _size = 0; }


    public IEnumerator<T> GetEnumerator()
    {
        for (int i = _size - 1; i >= 0; i--)
        {
            yield return items[i];
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator();

}

Few applications of Stacks.

  • Code editors use Stacks to match the opening tags/braces with closing tags/braces.

  • Browser back button is a Stack.

  • Compilers use stacks for converting infix expressions to Postfix expressions.

  • Compilers use stacks for storing local data and call information for multiple levels of procedure calls.

 
Share this