Stacks - fundamental data type to manage a collection of objects

0-stack.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Stack

####Concept

• one of the fundamental data types used to manage a collection of objects
• works like a 'stack' of plates
  • plates can only be added or removed from the top of the pile
  • new items are pushed on to the stack
  • items are popped off of the stack
  • this management method known as a Last In, First Out (LIFO)

####Implementation

• there is more than one way to accomplish this behaviour
  • both linked lists and arrays are two fundamental ways to store the data
  • the rest of the data type then determines when and how the array/linked list is accessed
    • this is what determines the stack's behaviour

####See Also

• Queues

ArrayStack.java

//! NOTE: this class does not have resizable arrays

public class ArrayStack{
		
	private String[] s;
	private int N = 0;

	public ArrayStack(int capacity)
	{
		s = new String[capacity];
	}

	public void push(String item)
	{
		s[N++] = item;
	}

	public String pop()
	{
		if (N == 0)
			throw new IndexOutOfBoundsException("No items in stack. Cannot pop.");
		return s[--N];
	}

	// client
	public static void main(String[] args)
	{
		ArrayStack stack = new ArrayStack(10);
		stack.push("Hello");
		stack.push("my");
		stack.push("name");
		System.out.println(stack.pop());
		stack.push("is");
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		stack.push("Jim.");
		System.out.println(stack.pop());
		stack.pop();
	}
}

ArrayStackResize.java

public class ArrayStackResize{
		
	private String[] s;
	private int N = 0;

	public ArrayStackResize(int capacity)
	{
		s = new String[capacity];
	}

	public void push(String item)
	{
		s[N++] = item;
		if(N == s.length)
			resize(s.length*2);
	}

	public String pop()
	{
		if (N == 0)
			throw new IndexOutOfBoundsException("No items in stack. Cannot pop.");
		if(--N == s.length/4)
			resize(s.length/2);
		return s[N];
	}

	public void resize(int capacity)
	{
		System.out.println("Resizing to " + capacity);
		String[] copy = new String[capacity];
		for (int i = 0; i < N; i++)
			copy[i] = s[i];
		s = copy;
	}

	// client
	public static void main(String[] args)
	{
		ArrayStackResize stack = new ArrayStackResize(1);
		stack.push("Hello");
		stack.push("my");
		stack.push("name");
		System.out.println(stack.pop());
		stack.push("is");
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		stack.push("Jim.");
		System.out.println(stack.pop());
		stack.pop();
	}
}

LinkedStack.java

public class LinkedStack{
	private Node first;
		
	private class Node {
		String item;
		Node next;
	}

	public String pop()
	{
		if (first == null)
			throw new IndexOutOfBoundsException("No items in stack, cannot pop.");
		String item = first.item;
		first = first.next;
		return item;
	}

	public void push(String newitem)
	{
		Node oldfirst = first;
		first = new Node();
		first.item = newitem;
		first.next = oldfirst;
	}

	// client
	public static void main(String[] args)
	{
		LinkedStack stack = new  LinkedStack();
		stack.push("Hello");
		stack.push("my");
		stack.push("name");
		System.out.println(stack.pop());
		stack.push("is");
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		stack.push("Jim.");
		System.out.println(stack.pop());
		stack.pop();
	}
}