背包、栈和队列

介绍

背包是一种不支持从中删除元素的集合类型，它的目的是帮助用例收集元素并迭代遍历所有收集到的元素，迭代的顺序不确定且与用例无关。

下压栈是一种基于后进先出（LIFO）策略的集合类型。当遍历下压栈中的元素时，从最后压入的元素依次遍历到最先压入的元素。

先进先出队列是一种基于先进先出（FIFO）策略的集合类型。当遍历队列中的元素时，从最后加入队列的元素依次遍历到最先加入队列的元素。

API设计

下面是背包、下压栈和先进先出队列的API设计：

public class Bag<Item> implements Iterable<Item>
            Bag()           创建一个空背包
void        add(Item item)  添加一个新元素
boolean     isEmpty()       检查背包是否为空
int         size()          背包中元素的数量

public class Stack<Item> implements Iterable<Item>
            Stack()         创建一个空栈
void        push(Item item) 压入一个新元素
Item        pop()           弹出最后加入的元素
boolean     isEmpty()       检查栈是否为空
int         size()          栈中的元素数量

public class Queue<Item> implements Iterable<Item>
            Queue()             创建一个空队列
void        enqueue(Item item)  添加一个新元素
Item        dequeue()           删除最先被加入的元素
boolean     isEmpty()           检查队列是否为空
int         size()              队列中的元素数量

代码实现

背包的代码实现：

import java.util.Iterator;
import java.util.NoSuchElementException;

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

    private Node<Item> mFirst;
    private int mN;

    public Bag () {
        mFirst = null;
        mN = 0;
    }

    public boolean isEmpty() {return mFirst == null;}

    public int size() {return mN;}

    public void add(Item item) {
        Node<Item> oldFirst = mFirst;
        mFirst = new Node<Item> (item, oldFirst);
        mN++;
    }

    public ListIterator<Item> iterator () {
        return new ListIterator<Item> (mFirst);
    }

    private class ListIterator<Item> implements Iterator<Item> {
        private Node<Item> mCurrent;

        public ListIterator (Node<Item> first) {
            mCurrent = first;
        }

        public boolean hasNext() {return mCurrent != null;}

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = mCurrent.getItem();
            mCurrent = mCurrent.getNext();
            return item;
        }

        public void remove() {throw new UnsupportedOperationException(); }
    }

    public static class Node<Item> {
        private Item mItem;
        private Node<Item> mNext;

        public Node (Item item, Node<Item> next) {
            mItem = item;
            mNext = next;
        }

        public Item getItem() {
            return mItem;
        }

        public Node<Item> getNext() {
            return mNext;
        }
    }
}

下压栈的代码实现：

import java.util.Iterator;
import java.util.NoSuchElementException;

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

    private Node<Item> mFirst;
    private int mN;

    public Stack () {
        mFirst = null;
        mN = 0;
    }

    public boolean isEmpty() {return mFirst == null;}

    public int size() {return mN;}

    public void push(Item item) {
        Node<Item> oldFirst = mFirst;
        mFirst = new Node<Item> (item, oldFirst);
        mN++;
    }

    public Item pop () {
        if (isEmpty()) throw new NoSuchElementException("Stack Overflow");
        Node<Item> item = mFirst;
        mFirst = mFirst.getNext();
        return item.getItem();
    }

    public Item peek () {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return mFirst.getItem();
    }

    public Iterator<Item> iterator () {
        return new ListIterator<Item>(mFirst);
    }

    private class ListIterator<Item> implements Iterator<Item> {
        Node<Item> mCurrent;

        public ListIterator(Node<Item> first) {
            mCurrent = first;
        }

        public boolean hasNext () {
            return mCurrent != null;
        }

        public Item next () {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = mCurrent.getItem();
            mCurrent = mCurrent.getNext();
            return item;
        }

        public void remove () {
            throw new UnsupportedOperationException();
        }
    }

    private static class Node<Item> {
        private Item mItem;
        private Node<Item> mNext;

        public Node(Item item, Node<Item> next) {
            mItem = item;
            mNext = next;
        }

        public Item getItem() {
            return mItem;
        }

        public Node<Item> getNext() {
            return mNext;
        }
    }
}

先进先出队列的代码实现：

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Queue<Item> implements Iterable<Item> {
    private Node<Item> mFirst;
    private Node<Item> mLast;
    private int mN;

    public Queue () {
        mFirst = null;
        mLast = null;
        mN = 0;
    }

    public boolean isEmpty () {return mFirst == null;}

    public int size() {return mN;}

    public void enqueue(Item item) {
        Node<Item> oldLast = mLast;
        mLast = new Node<Item> (item, null);
        if (isEmpty())  mFirst = mLast;
        else            oldLast.setNext(mLast);
        mN++;
    }

    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = mFirst.getItem();
        mFirst = mFirst.getNext();
        mN--;
        if (isEmpty()) mLast = null;   // to avoid loitering
        return item;
    }

    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return mFirst.getItem();
    }

    public Iterator<Item> iterator () {
        return new ListIterator<Item> (mFirst);
    }

    private class ListIterator<Item> implements Iterator<Item> {
        private Node<Item> current;

        public ListIterator (Node<Item> first) {
            current = first;
        }

        public boolean hasNext () {
            return current != null;
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.getItem();
            current = current.getNext();
            return item;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    private static class Node<Item> {
        private Item mItem;
        private Node<Item> mNext;

        public Node (Item item, Node<Item> next) {
            mItem = item;
            mNext = next;
        }

        public Item getItem() {
            return mItem;
        }

        public Node<Item> getNext() {
            return mNext;
        }

        public void setNext(Node<Item> next) {
            mNext = next;
        }
    }
}