Stack implementation using Arrays & Linked Lists


In C#, you can use a Stack object to store your data simply by using System.Collections and then making a new declaration of a generic Stack object to work with various objects like integers or strings like so: Stack s = new Stack(); and you would add items by using the .Push() method and retrieve items using the .Pop() method.

Respectively, in order effectively see what goes on “under the hood”, we make our own Stack object using Arrays. So, my version of both the Array and LinkedList implementation is shown below.

On a related note, a Stack would be most useful if you were going to implement undo/redo functionality or a Towers Of Hanoi game like this one:

  • Stacks are First in Last out, Last in First Out (LIFO)
  • Linked List representation is also another option
  • Our main functions of our Stack class will be Push(), Pop(), isEmpty(), Peek(), and Display()
  • Again, you can also borrow this code for use with Java since syntax is similar.

Array Implementation:

class Stack
 {
   private int[] arr;

   private int topOfStack;

   public Stack(int size)
   {
     arr = new int[size];
     topOfStack = 0;
   }
   public void Push(int value)//inserts an object or value onto the stack
   {
     if (topOfStack > arr.Length - 1)
     {
        Array.Resize(ref arr, topOfStack + 1);
        arr[topOfStack] = value;
     }
     else
     {
        arr[topOfStack] = value;
     }
     topOfStack++;
   }
   public int Pop()//removes the object or value at the top of the stack
   {
     int val;
     if (isEmpty())
     {
       return 0;
     }
     else
     {
       topOfStack --;
       val = arr[topOfStack];
       Array.Resize(ref arr, topOfStack);//resize the array
       return val;
     }
   }
   public bool isEmpty()//to check if the stack is empty
   {
      if (arr.Length >= 1)
      {
        return false;
      }
      else
      {
         return true;
      }
   }
   public void DisplayStack()//this is our display stack function, it prints from the top to the bottom
   {
      for (int i = topOfStack-1; i <= topOfStack-1; i--)
      {
        Console.WriteLine(arr[i]);
        if (i < 1)
        {
          break;
        }
      }
   }
   public int Peek()//Peek returns the value that is at the top of the stack
   {
       return arr[topOfStack - 1];
   }
 }
 class Program
 {
     static void Main()
     {
        Stack s = new Stack(5);
        //our stack size is going to be 5 spaces, user can also set the size to be custom as well
        s.Push(1);
        s.Push(2);
        s.Push(3);
        s.Push(4);
        s.Push(5);
        s.DisplayStack();//we write out our stack

        int poppedValue = s.Pop();//we pop a value from the stack
        int popped2 = s.Pop();
        //displaying our value that we popped from the stack
        Console.WriteLine("Values popped from the stack: {0}, {1}", poppedValue, popped2);
        s.DisplayStack();

        s.Push(32);
        s.Push(64);
        Console.WriteLine("After new pushed vales...");
        s.DisplayStack();
        Console.WriteLine("Top of the stack: {0}", s.Peek());
        Console.ReadLine();//keep the window open
    }
}

Using Linked Lists:

class Node//a class to handle the node so that it can be used to make the linked list class
{
public int item;//item represents a number/data value in a node
public Node next;
public Node(int num)
{
item = num;
}
public void displayNode()
{
Console.WriteLine("[ {0} ]", item);//display items in the stack with brackets, I will call this in the linkedlist class
}
}
class LinkedList//the linkedlist class will act as the main class to handle stack functions
{
public Node head;
private int size;//this will be used to determine how big the list gets and will be used for popping items...
public LinkedList(int size)
{
this.head = null; //null means that the link doesnt point to anything
this.size = 0;
}

public LinkedList()
{
//empty constructor, so were are able to create an instance of linkedlist in the class
}
public void Insert(int num)
{
Node newNode = new Node(num);//passing in a number to the new node
newNode.next = head;//inserts at the beginning of the linked list
head = newNode;//head or the first index is equal to the newnode (or the value inserted)
size++;//keep track of how big the stack is
}
public int takeOut()//this will represent the pop functionality
{
Node x = head;

if (size > 0)
{
head = head.next;
size--;
}
return x.item;//return a number when we are popping from the stack
}
public void Display()//this method will get called when we are displaying the entire stack
{
Node current = head;//current node (last one in) is the head, so it will display first
while (head != null)
{
current.displayNode();
current = current.next;//the get the next node and display those

if (current == null)
{
return; //so that we get no null reference exceptions, return nothing if that ever happens
}
}
}
}
class Stack//the class that will handle the stack functions
{

private LinkedList list;

public Stack()
{
list = new LinkedList(); //create a new instance of linkedlist to work with

}
public void push(int s)
{
list.Insert(s);
}
public int pop() //returning an int value when I pop from the stack
{
return list.takeOut();
}
public void DisplayStack()//this method displays the stack in its entirety
{
Console.WriteLine("Stack (from top to bottom): ");
list.Display();
}
public int Peek()
{
return list.head.item;
}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s