Introduction

栈的实现需要先了解几个背景：内存管理，接口继承，对象游离。

tip：
引用：相当于存储对象的变量

Detail

内存管理

java使得引用不可修改，而相对于其它语言来说增加了一条特性：自动内存管理

当引用a被覆盖时，那么引用a原来指向的对象就成了孤儿，就会被回收。
当对象离开作用域后也会被回收。

例如：

动态数组

private void resize(int max)
{
    Item[] temp = (Item[]) new Object[max];
    for(int i = 0; i < N; i++)
        temp[i] = a[i];
    a = temp; //让a指向了新数组，原来的a指向数组就成了孤儿。temp引用也会被回收。
}

对象游离

实现栈，主要的情景是：栈是占用使用数组的空间的。
当我们应用pop()的实现中，弹出的元素仍然在数组中。而java的自动内存管理是针对那些再也无法被引用的对象的内存，所有回收不到这些pop出去的元素。所以，就要采取一种方法：将元素的引用设置为null，这将覆盖该引用，并使系统在用例用完后回收元素的内存。

public Item pop()
{
    Item item = a[--N];
    a[N] = null;
    if(N > 0 && N == a.length / 4)
        resize(a.length / 2);
    return item;
}

接口继承

一个类通过继承接口的方式，从而来继承接口的抽象方法。
接口并不是类，编写接口的方式和类很相似，但是它们属于不同的概念。类描述对象的属性和方法。接口则包含类要实现的方法。

接口的声明

关键字：interface
public[可见度] interface /*name*/ ([extends other name]){}
编写方法

接口(迭代)

public interface Iterable<Item>
{
    Iterator<Item> iterator();
}

接口实现

关键字：implements

...implements /*name*/[, 其他接口名称, 其他接口名称..., ...] ..

在其它类中实现接口

1
2
3

import java.util.Iterator;

public class ResizingArrayStack<Item> implements Iterable<Item>{

在该类中即可应用方法

public Iterator<Item> iterator()
{
    return new ReverseArrayIterator();
}
private class ReverseArrayIterator implements Iterator<Item>
{
    private int i = N;
    public boolean hasNext()
    {
        return i > 0;
    }
    public Item next()
    {
        return a[--i];
    }
    public void remove() {}
}

Test

LIFO栈（动态数组）

import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<Item>{
	
	private Item[] a = (Item[])new Object[1];//栈元素
	private int N = 0; //元素数量
	public boolean isEmpty()
	{
		return N == 0;
	}
	public int size()
	{
		return N;
	}
	
	private void resize(int max)
	{
		Item[] temp = (Item[]) new Object[max];
		for(int i = 0; i < N; i++)
			temp[i] = a[i];
		a = temp;
	}
	
	public void push(Item item)
	{
		if(N == a.length)
			resize(2 * a.length);
		a[N++] = item;
	}
	public Item pop()
	{
		Item item = a[--N];
		a[N] = null;
		if(N > 0 && N == a.length / 4)
			resize(a.length / 2);
		return item;
	}
	
	public Iterator<Item> iterator()
	{
		return new ReverseArrayIterator();
	}
	private class ReverseArrayIterator implements Iterator<Item>
	{
		private int i = N;
		public boolean hasNext()
		{
			return i > 0;
		}
		public Item next()
		{
			return a[--i];
		}
		public void remove() {}
	}
}

用例

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ResizingArrayStack<String> s = new ResizingArrayStack<String>();
		while(!StdIn.isEmpty())
		{
			String item = StdIn.readString();
			if(!item.equals("-"))
				s.push(item);
			else if(!s.isEmpty())
				StdOut.print(s.pop() + " ");
		}
		StdOut.println("(" + s.size() + " left on stack)");
	}

}

下压栈