Java下压栈的实现

背景
  最近开始学习Robert Sedgewick的《算法》。本着“纸上得来终觉浅，绝知此事要躬行”的精神，决定把书上的所有经典算法都码一遍：一来加深印象和实际的算法动手能力；二来算是做一个云笔记，方便大家和自己在需要的时候使用。
  另外，这个是我的第一篇博客，不知道简书的规矩，此前也不知道写博客的注意事项。还希望大家多多包涵，也希望能够看到的各位多提提意见。也希望大家共同成长。
  好了，废话就不说了，下面就直接上代码。

数组实现
//代码来源于RobertSedgewick的《算法》第四版

---

import java.util.Iterator;

public class ResizeingArrayStack<Item> implements Iterable<Item>
{
    private Item[] array = (Item[]) new Object[1];
    private int itemNum = 0;

    public boolean isEmpty()
    {
        return itemNum == 0;
    }

    public int size()
    {
        return itemNum;
    }

    private void resize(int max)
    {
        Item[] arrayTmp = (Item[]) new Object[max];
        for (int i = 0; i < itemNum; i++)
        {
            arrayTmp[i] = array[i];
        }
        array = arrayTmp;
    }

    public void push(Item item)
    {
        if (itemNum == array.length)
        {
            resize(2 * itemNum);
            array[itemNum++] = item;
        }
    }

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

    @Override
    public Iterator<Item> iterator()
    {
        // TODO Auto-generated method stub
        return new ReverseArrayIterator();
    }

    private class ReverseArrayIterator implements Iterator<Item>
    {
        private int i = itemNum;

        @Override
        public boolean hasNext()
        {
            // TODO Auto-generated method stub
            return i > 0;
        }

        @Override
        public Item next()
        {
            // TODO Auto-generated method stub
            return array[--i];
        }

    }

}

---

以上便是可动态调整数组大小的下压栈的Java的数组实现。

链表实现
1、新建链表节点
在使用链表实现时，我们必须要构造一个适用于栈性质的链表节点

public class StackNode<Item>
{
    Item item;
    StackNode next;
}

2、链表栈的实现

import java.util.Iterator;

public class LinkStack<Item> implements Iterable<Item>
{
    private StackNode first;
    private int itemNum;

    public boolean isEmpty()
    {
        return first.next == null;
    }

    public int size()
    {
        return itemNum;
    }

    public void push(Item item)
    {
        StackNode oldfirst = first;
        first = new StackNode();
        first.item = item;
        first.next = oldfirst;
        itemNum++;
    }

    public Item pop()
    {
        Item item = (Item) first.item;
        first = first.next;
        itemNum--;
        return item;
    }

    @Override
    public Iterator<Item> iterator()
    {
        // TODO Auto-generated method stub
        return null;
    }

    private class LinkListIterator implements Iterator<Item>
    {
        private StackNode current = first;

        @Override
        public boolean hasNext()
        {
            // TODO Auto-generated method stub
            return current.next != null;
        }

        @Override
        public Item next()
        {
            // TODO Auto-generated method stub
            Item item = (Item) current.item;
            current = current.next;
            return item;
        }

    }

}