java - Steque 和 API 实现

Question

steque 是一种栈端队列，它是一种实现推送、弹出和入队以及您希望添加的任何其他功能的数据类型。

请注意，我正在使用基于链表的方法实现 steque。下面是我的整个 Steque 类的代码，我遇到的问题是每当我尝试从 steque 中弹出一些元素或迭代它时，我都会得到 NullPointerException。 push() 和 enqueue() 方法在我测试时似乎工作得很好，我确实彻底检查了我的 pop() 和 iterator() 但似乎找不到任何可能导致任何 NullPointerException 的错误。非常感谢对我的代码提供解决此问题的任何帮助!

public class Steque<Item> implements Iterable<Item> {
    private int N;
    private Node first;
    private Node last;

    private class Node {
        private Item item;
        private Node next;
        private Node prev;
    }

    /**
     * create an empty steque
     */
    public Steque() {
        N = 0;
        first = null;
        last = null;
    }

    /**
     * pop (return) the first item on top of stack and modify first
     * accordingly to refer to next node.
     */
    public Item pop() {
        if (isEmpty()) throw new RuntimeException("Steque underflow");
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    /**
     * push item on top of the stack and modify the first pointer
     * to refer to the newly added item.
     */
    public void push(Item item) {
        Node oldfirst = first;
        Node first = new Node();
        first.item = item;
        first.next = oldfirst;
        if (oldfirst != null)
            oldfirst.prev = first;
        ++N;
    }

    /**
     * push item on bottom of the stack and reset the last pointer
     * to refer to the newly added item.
     */
    public void enqueue(Item item) {
        Node oldlast = last;
        Node last = new Node();
        last.item = item;
        last.prev = oldlast;
        if (oldlast != null)
            oldlast.next = last;
        ++N;
    }

    public Item peek() {
        if (isEmpty()) throw new RuntimeException("Steque underflow");
        return first.item;
    }

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

    public int size() {
        return N;
    }

    /**
     *  prints the steque from top to bottom

    private void printState() {
        System.out.println("Printing steque below: top --> bottom ");
        for (Node idx = this.first; idx!= null; idx = idx.next) {
            System.out.print(idx.item + " - ");
        }
        System.out.println();
    }
    */

    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item i : this) {
            s.append(i + " ");
        }
        return s.toString().trim();
    }

    public Iterator iterator() {
        return new LIFOIterator();
    }

    /**
     * iterator that implements hasNext(), next(), and remove().
     */
    private class LIFOIterator implements Iterator<Item>
    {   // support LIFO iteration
        private Node current = first;
        public boolean hasNext() { return current.next != null; }
        public void remove() {
            Node n = first;
            while (n.next.next != null) {
                n = n.next;
            }
            n.next = null;
            --N;
        }

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

    /**
     * a simple test client
     */
    public static void main(String[] args) {
        Steque<String> steq = new Steque<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) {
                //steq.push(item);
                steq.enqueue(item);
            }
            /*
            else if (!steq.isEmpty()) {
                System.out.print(steq.pop() + " ");
            }
            */
        }
        System.out.println("(" + steq.size() + " left on steque)");
        Iterator itr = steq.iterator();
        System.out.println("printing steque of strins below: ");
        while(itr.hasNext()) {
            System.out.print(itr.next() + " ");
        }
    }
}

注意:我在这里省略了所有导入语句，但它们确实包含在我的程序中，因此可以保证此代码中没有“未定义的方法”或“未声明的标识符”错误。

Answer 1

问题是，当您只使用 enqueue 方法时，您的 first 变量不会被填充。

因此访问该字段的方法会触发 NPE。

hasNext 通过 current 使用字段。

IMO 的解决方案是在 enqueue 中捕获 N == 0 的特殊情况，并用可用元素填充第一个元素。

我试过了

if(N==0)
  first = last

在排队的最后一个初始化之后，它可以在没有 NPE 的情况下工作。