Java堆栈方法:大小、重复、反向

Question

任务中给出了堆栈，我应该实现3种方法：

1. 一种告诉堆栈中元素大小的方法

2. 一种复制堆栈最高值的方法

3. 反转堆栈/更改其顺序的方法

我已经成功地实施了前两种方法，它们运行良好。

public int size() {
        int count = 0;
        for (Element element = top; element != null; element = element.next)
        {
            count++;
        }
        return count;
    }
public void dupe() {
        if (top == null)
        {
            throw new EmptyStackException();
        }
        push(top());
    }

对于我遇到的反向方法，是否可以仅通过使用堆栈来反向堆栈？这里不需要两堆吗？

完整的代码在这里：

import java.util.EmptyStackException;

public class IntStack {
    private Element top;

    public IntStack() {
        top = null;
    }

    public int pop() {
        if (top == null)
            throw new EmptyStackException();
        int value = top.getValue();
        top = top.getNext();
        return value;
    }

    public int top() {
        if (top == null)
            throw new EmptyStackException();
        return top.getValue();
    }

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

    public void push(int value) {
        Element newTop = new Element(value);
        newTop.setNext(top);
        top = newTop;
    }

    public String toString() {
        Element runingElement = top;
        StringBuilder sb = new StringBuilder();
        while (runingElement != null) {
            sb.append(runingElement.getValue()).append("n");
            runingElement = runingElement.getNext();
        }
        return sb.toString();
    }

    public void dupe() {
        if (top == null)
        {
            throw new EmptyStackException();
        }
        push(top());
    }

    public int size() {
        int count = 0;
        for (Element element = top; element != null; element = element.next)
        {
            count++;
        }
        return count;
    }

    public void reverse() {

    }

Answer 1

这里有一种方法可以在不使用数组或其他堆栈的情况下反转堆栈。当然，可能有更优化的方法来实现这个结果。本质上，堆栈的顶部将其下一个设置为null，并遍历每个元素，将元素的next设置为上一个节点。最后，它将内部顶部设置为最后一个元素。这种方法不是线程安全的。

    public void reverse() {
        if (isEmpty() || top.getNext() == null) {
            return;
        }
        Element prev = top;            
        Element cur = top.getNext();
        Element end = null;
        // set the top of the stack to have it's next point to nothing
        prev.setNext(null);
        // while we have something to process, loop
        while (cur != null) {
            // keep the next from the current
            Element tmp = cur.getNext();
            // update the next to point to the previous
            cur.setNext(prev);
            // set the previous to where we are now
            prev = cur;
            // need to find the end; update to where we are now
            end = cur;
            // update our current to the temp; could be null
            cur = tmp;
        }
        top = end;
    }

将加载10个元素（0-9）的示例测试驱动程序：

public static void main(String[] args) {
    IntStack stack = new IntStack();
    // ensure reverse does nothing on empty stack
    System.out.println("empty stack");
    System.out.println(stack.toString());
    System.out.println("Reversing.");
    stack.reverse();
    System.out.println(stack.toString());
    // make sure does nothing on single entry
    System.out.println("pushing 0");
    stack.push(0);
    System.out.println(stack.toString());
    System.out.println("Reversing.");
    stack.reverse();
    System.out.println(stack.toString());

    for (int i = 1; i < 10; ++i) {
        System.out.println("Pushing " + i);
        stack.push(i);
    }
    System.out.println("Stack after test load:");
    System.out.println(stack.toString());

    System.out.println("Printing size.");
    System.out.println(stack.size() + "n");
    System.out.println("Reversing.");
    stack.reverse();
    System.out.println(stack.toString());

}

样本输出：

空堆栈

反转。

正在推送0
0

反转
0

推1
推2
推3
推4
推5
推6
推7
推8
推动9

测试加载后的堆栈：
9
8
7
6
5
4
3
2
1
0

打印尺寸
10

反转
0
1
2
3
4
5
6
7
8
9

Answer 2

这里有另一个反转堆栈的方法。

public void reverse() {
    if( top == null || top.next == null) {
        return; //do nothing
    } if (top.next.next == null) {
        Element last = top.next;
        last.next = top;
        last.next.next = null;
        top = last;
    } else {
        Element secondLast = top;
        Element last = top.next;
        Element current = top.next.next;
        secondLast.next = null;
        while(true) {
            last.next = secondLast;
            if(current == null) {
                top = last;
                break;
            }
            secondLast = last;
            last = current;
            current = current.next;
        }
    }
}

注意：如果我们创建一个双链接列表，这几乎太容易了。