Home

C# Collections: Introduction to Stacks

   

Stacks Fundamentals

 

Introduction

A stack is a technique of creating a list so that the last item added to the list is also the first one that would be removed. It can be illustrated as placing a few cups in a box that can receive only one on top of another (no adjacent cup). When it comes time to get one of those cups, you must first access the top one; that is, the last one that was added. In other words, at one time, the items in the list appear in the reverse order they were added. This technique of building a list is referred to as first-in last-out (FILO).

To create a collection class that supports stack functionality, you have various options between arrays and linked lists.

Introduction to Creating a Stack Using an Array

To perform stack operations using a collection, you can create a class whose main member is an array. Here is an example of starting such a class:

interface IStack<T>
{
}

public class Stack<T> : IStack<T>
{
    private T[] items;
}

 (We are starting from an interface but you can omit it if you want.) Here is an example:

Stack
public class Stack<T>
{
    private T[] items;
}

We are also creating the class as a generic one but you can remove <T> then use a data type of your choice wherever T is used as a type. Here is an example:

public class Stack
{
    double[] items;
}

)

Of course, whenever you use an array, you should (must) make sure you initialize it prior to its being used. You can initialize the array in the body of the class or you can use a constructor. Here is an example:

public class Stack<T> : IStack<T>
{
    private T[] items;

    public Stack()
    {
        items = new T[10];
    }
}

As always, as a courtesy, you should make sure you keep a count of the items in a collection class. This is usually done by using a read-only property that returns the size of the array. This can be done as follows:

interface IStack<T>
{
    int Count { get; }
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }
}

Using this mechanism, you can create a property that holds the information about the stack being empty or not. When implementing this method, you can check the value of the size. If it is 0, the list is empty. If the size is greater than 0, the list is not empty. Here is an example of defining this method:

interface IStack<T>
{
    int Count { get; }
    bool IsEmpty { get; }
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            else
                return false;
        }
    }
}

Pushing an Item to a Stack

To add an item to a stack, if the list is empty, which means its size is 0, you simply position the first item. If the stack already contains at leas one item, you must push the existing item down (or in the moving direction) to create an empty space for the new item, then position the new item in the new empty position. For this reason, this operation is referred to as pushing.

If you are using an array, to push the new item, from the end of the list, first move each item one position down to make the 0 index available. Then, assign the new item to that index. If your class is keeping a count of the items in its list, after adding the new item, you should increase the number of items. Here is an example of performing this operation:

using System;

interface IStack<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Push(T item);
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            else
                return false;
        }
    }

    public void Push(T item)
    {
        items[size] = item;
        size++;
    }
}

public class Exercise
{
    public static int Main()
    {
        Stack<double> stk = new Stack<double>();

        stk.Push(424.06);
        stk.Push(12500.58);
        stk.Push(28.0746);
        stk.Push(1046.88);

        return 0;
    }
}

Peeking an Item of a Stack

The process of getting an item of a stack is referred to as peeking. Remember that, in a stack, you have access to only one item, the last one to be added. Therefore, to peek an item, create a method that simply returns the item in the last index. This would be the item at the size - 1. Here is an example of creating and using a peeking method:

using System;

interface IStack<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Push(T item);
    T Peek();
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            else
                return false;
        }
    }

    public void Push(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[size - 1];
    }
}

public class Exercise
{
    public static int Main()
    {
        Stack<double> stk = new Stack<double>();

        stk.Push(424.06);
        Console.WriteLine("Number: {0}", stk.Peek());
        stk.Push(12500.58);
        Console.WriteLine("Number: {0}", stk.Peek());
        stk.Push(28.0746);
        Console.WriteLine("Number: {0}", stk.Peek());
        stk.Push(1046.88);
        Console.WriteLine("Number: {0}", stk.Peek());

        return 0;
    }
}

This would produce:

Number: 424.06
Number: 12500.58
Number: 28.0746
Number: 1046.88
Press any key to continue . . .

Popping an Item From a Stack

The processing of removing an item from a stack is referred to as poping it. Once again, remember that you only have access to the top item, which is the last item that was added. If you are using an array, to pop an item, in your method:

  1. Get a reference to the top item, which is the item at index - 1
  2. Decrease the number of items. This would remove the last item
  3. Return the reference you got in the first step

Here is an example of creating and using a peeking method:

using System;

interface IStack<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Push(T item);
    T Peek();
    T Pop();
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            else
                return false;
        }
    }

    public void Push(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[size - 1];
    }

    public T Pop()
    {
        T Last = items[size - 1];

        size--;
        return Last;
    }
}

public class Exercise
{
    public static int Main()
    {
        Stack<double> stk = new Stack<double>();

        stk.Push(424.06);
        stk.Push(12500.58);
        stk.Push(28.0746);
        stk.Push(1046.88);

        Console.WriteLine("Total: {0}", stk.Count);
        Console.WriteLine("Number: {0}", stk.Pop());
        Console.WriteLine("Number: {0}", stk.Pop());
        Console.WriteLine("Number: {0}", stk.Pop());
        Console.WriteLine("Number: {0}", stk.Pop());

        return 0;
    }
}

This would produce:

Total: 4
Number: 1046.88
Number: 28.0746
Number: 12500.58
Number: 424.06
Press any key to continue . . .

Clearing a Stack

Clearing a stack consists of deleting all of its items. To support this operation, create a method that resets the number of items of the list. Here is an example:

interface IStack<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Push(T item);
    T Peek();
    T Pop();
    void Clear();
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            else
                return false;
        }
    }

    public void Push(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[size - 1];
    }

    public T Pop()
    {
        T Last = items[size - 1];

        size--;
        return Last;
    }

    public void Clear()
    {
        size = 0;
    }
}

Enumerating Each Item of the Stack

If you want, you can provide support foreach item of the collection. To do this, you would create a method named GetEnumerator that returns an IEnumerator object. When implementing this method, start from the end of the list, use a while loop to yield return the current item and decrement the count each time. Here is an example:

using System;
using System.Collections.Generic;

interface IStack<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Push(T item);
    T Peek();
    T Pop();
    void Clear();
    IEnumerator<T> GetEnumerator();
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            else
                return false;
        }
    }

    public void Push(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[size - 1];
    }

    public T Pop()
    {
        T Last = items[size - 1];

        size--;
        return Last;
    }

    public void Clear()
    {
        size = 0;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = size - 1;

        while (counter >= 0)
        {
            yield return items[counter];
            counter--;
        }
    }
}

public class Exercise
{
    public static int Main()
    {
        Stack<double> stk = new Stack<double>();

        stk.Push(424.06);
        stk.Push(12500.58);
        stk.Push(28.0746);
        stk.Push(1046.88);

        foreach(double d in stk)
            Console.WriteLine("Number: {0}", d);

        return 0;
    }
}

This would produce:

Number: 1046.88
Number: 28.0746
Number: 12500.58
Number: 424.06
Press any key to continue . . .

Looking for an Item in a Stack

The operations we have implemented so far are typical of a stack. One of the routine operations you can perform consists of checking the availability of an item. To perform this operation, create a method (you can call it Contains) that is passed the item to look for. When implementing the method, you can use a loop to visit each item. If you find an item that matches the argument, return true. If you get to the end of the list and there was no item that matched the argument, let the method return false. Here is an example of how this can be done:

using System;
using System.Collections.Generic;

interface IStack<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Push(T item);
    T Peek();
    bool Contains(T item);
    T Pop();
    void Clear();
    IEnumerator<T> GetEnumerator();
}

public class Stack<T> : IStack<T>
{
    private int size;
    private T[] items;

    public Stack()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            else
                return false;
        }
    }

    public void Push(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[size - 1];
    }

    public bool Contains(T item){
        foreach (T value in items)
            if (value.Equals(item))
                return true;

        return false;
    }

    public T Pop()
    {
        T Last = items[size - 1];

        size--;
        return Last;
    }

    public void Clear()
    {
        size = 0;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = size - 1;

        while (counter >= 0)
        {
            yield return items[counter];
            counter--;
        }
    }
}

 

 
 

Home Copyright © 2010-2011 FunctionX