java - Steque和API实现

梯形图是堆栈末端的队列，它是一种数据类型，可实现推入，弹出和入队以及您要添加到的任何其他功能。

请注意，我正在使用基于链接列表的方法来实现此功能。下面是我整个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() + " ");
        }
    }
}

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

最佳答案

问题是，仅使用enqueue方法时，first变量不会被填充。

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

hasNext通过current使用该字段。

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

我试过了

if(N==0)
  first = last

在初始化last之后，无需NPE即可工作。

关于java - Steque和API实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34712602/