Stack (Python)

Beyond Python Stack

First of all, there is no stack class in Python library, therefore there is no way you can import stack from the library, you have to implement your own stack class. This piece of information cost my friend an hour of searching in google how to import stack from the library. But after you implemented the stack class onto your library, it will be very handy to have it around. Lets quickly define what is a stack.

A stack is a collection of objects that represents a simple last in - first out order. The collection mostly visualizes it vertically. Imagine a pile of cards, the rules are: you can only pick a card from the top of the pile and you can only put a card on top of the pile.

The functions of stack class are is_empty, pop, push, top. 

is_empty: return true if the collection is empty

pop: remove the object from the collection and then return the object

push: add the object on top of the collection

top: return the last added object of the collection

In Python, we can use a list as the collection. For push, append the new object to the list, for pop, remove last object from the list, and for top, remove the last object from the list. This is just how we learned how to implement a stack with a list. It might seems a small concept for this course and you might think why I am making stack such a big deal. It is because when we learned stack with java, we still didn't know about link. So, we have to implement stack with array. It is important to note that java has to initialize an array, so every array occupy limited amount of memory. Therefore if the array is full, we need to create another array that duplicate the data into it. Here are the code:

________________________________________________________________________________

/** http://userpages.umbc.edu/~dcarter2/workspace/Trees/src/javafoundations/ArraySta/ck.java

**/

//********************************************************************
//  ArrayStack.java       Java Foundations
//
//  Represents an array implementation of a stack. The bottom of
//  the stack is kept at array index 0.

//

//

//********************************************************************

package javafoundations;

import javafoundations.exceptions.*;

public class ArrayStack<T> implements Stack<T>
{
   private final int DEFAULT_CAPACITY = 10;
   private int count;
   private T[] stack;

   //-----------------------------------------------------------------
   //  Creates an empty stack using the default capacity.
   //-----------------------------------------------------------------
   public ArrayStack()
   {
      count = 0;
      stack = (T[]) (new Object[DEFAULT_CAPACITY]);
   }

   //-----------------------------------------------------------------
   //  Adds the specified element to the top of this stack, expanding
   //  the capacity of the stack array if necessary.
   //-----------------------------------------------------------------
   public void push (T element)
   {
      if (count == stack.length)
         expandCapacity();

      stack[count] = element;
      count++;
   }

   //-----------------------------------------------------------------
   //  Returns a string representation of this stack.
   //-----------------------------------------------------------------
   public String toString()
   {
      String result = "<top of stack>\n";

      for (int index=count-1; index >= 0; index--)
         result += stack[index] + "\n";

      return result + "<bottom of stack>";
   }

   //-----------------------------------------------------------------
   //  Creates a new array to store the contents of this stack with
   //  twice the capacity of the old one.
   //-----------------------------------------------------------------
   private void expandCapacity()
   {
      T[] larger = (T[])(new Object[stack.length*2]);

      for (int index=0; index < stack.length; index++)
         larger[index] = stack[index];

      stack = larger;
   }

   //-----------------------------------------------------------------
   //  The following methods are left as Programming Projects.
   //-----------------------------------------------------------------
   public T pop () throws EmptyCollectionException 
 {
  if(count == 0)
   throw new EmptyCollectionException("Pop operation failed. Stack is empty.");
   
  T temp = stack[count - 1];
  count--;
  return temp;
 }
   public T peek () throws EmptyCollectionException 
 {
  if(count == 0)
   throw new EmptyCollectionException("Peek operation failed. Stack is empty.");
   
  return stack[count - 1];
 }
   public boolean isEmpty() 
 {
  return count == 0;
 }
   public int size() 
 {
  return count;
 }
}

________________________________________________________________________________

You might think that this concept seems pretty lame. However, the concept of stack goes beyond every code. Almost every complex code uses stack. Everything you do on the computer uses stack, even your calculator uses stack. This is because how the assembly language create functions so that cpu knows where to go back to run the code. So that your code will be run from the top to the bottom, unless you tell is to jump to other section of the code.