基于链表实现的Stack如何仅用int和stack类型变量完成反转？

背景说明 #

我正在开发一个基于链表实现Stack的项目，需求为「实现包含测试程序的栈，需具备push、pop、isEmpty、reverse四类方法」。目前正在开发reverse栈反转方法，该方法有明确约束：仅允许使用int、stack类型作为新变量。我之前直接调用了LinkedList项目的reverse方法实现，不符合本次要求，需要找到合规的实现方案。

现有实现代码 #

LinkedListOfInts类代码 #

import java.util.Random;

public class LinkedListOfInts {
    Node head;
    Node tail;

    private class Node {
        int value;
        Node nextNode;

        public Node(int value, Node nextNode) {
            this.value = value;
            this.nextNode = nextNode;
        }

    }

    public LinkedListOfInts(int N, int low, int high) {
        Random random = new Random();
        for (int i = 0; i < N; i++)
            this.addToFront(random.nextInt(high - low) + low);
    }

    public void addToFront(int x) {
        head = new Node(x, head);
        if (tail == null)
            tail = head;
    }

    public int deleteFromFront() {
        int headValue = -1;
        if (head == null)
            return headValue;
        else {
            if (head == tail) {
                headValue = head.value;
                head = null;
                tail = null;
            } else {
                headValue = head.value;
                head = head.nextNode;
            }
        }
        return headValue;
    }

    public LinkedListOfInts reverse() {
        Node previous = null;
        Node current = head;
        Node next;
        while (current != null) {
            next = current.nextNode;
            current.nextNode = previous;
            previous = current;
            current = next;
        }
        head = previous;
        return this;
    }

    public String toString() {
        String result = "";
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
            if (!result.isEmpty()) {
                result += ", ";
            }
            result += ptr.value;
        }
        return "[" + result + "]";
    }

    public static void main(String[] args) {
        LinkedListOfInts list = new LinkedListOfInts(5, 1, 10);
        System.out.println("Original List" + list.toString());
        list.addToFront(1);
        System.out.println("List After Adding One: " + list.toString());
        list.addToFront(2);
        System.out.println("List After Adding Two: " + list.toString());
        list.addToFront(3);
        System.out.println("List After Adding Three: " + list.toString());
        list.deleteFromFront();
        System.out.println("List After Deleting Item from the Front: " + list.toString());
        list.reverse();
        System.out.println("Reversed List: " + list.toString());

    }
}

Stack类代码 #

import java.util.Scanner;

public class Stack {
    LinkedListOfInts list = new LinkedListOfInts(5, 1, 10);

    public void push(int item) {
        list.addToFront(item);
    }

    public int pop() {
        return list.deleteFromFront();
    }

    public boolean isEmpty() {
        while (list.head != null) {
            list.head = null;
            return true;
        }
        return false;
    }

    public void reverse() {
        Stack tmpB = new Stack();
        while (!this.isEmpty()) {
            tmpB.push(this.pop());
        }
        Stack tmpC = new Stack();
        while (!tmpB.isEmpty()) {
            tmpC.push(tmpB.pop());
        }
        while (!tmpC.isEmpty()) {
            this.push(tmpC.pop());
        }
    }

    @Override
    public String toString() {
        return "Stack: " + list + "";
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        Stack stack = new Stack();
        boolean done = false;
        while (!done) {
            System.out.println("1. Push");
            System.out.println("2. Pop");
            System.out.println("3. Empty");
            System.out.println("4. Reverse");
            System.out.println("5. toString");
            switch (input.nextInt()) {
            case 1:
                System.out.println("Add an Item to the Front of the Stack");
                stack.push(input.nextInt());
                break;
            case 2:
                System.out.println("Delete an Item at the Front of the Stack");
                System.out.println(stack.pop());
                break;
            case 3:
                System.out.println("Empty a Stack");
                System.out.println(stack.isEmpty());
                break;
            case 4:
                System.out.println("Reverse the List");
                stack.reverse();
                break;
            case 5:
                System.out.println("toString");
                System.out.println(stack.toString());
                break;
            }
        }
    }
}

修复方案 #

第一步：修正错误的isEmpty方法 #

现有isEmpty方法的逻辑是判断到栈非空就直接清空链表头返回true，本质是清空栈而非判断栈是否为空，这是reverse方法无法正常运行的核心问题，修复后代码如下：

public boolean isEmpty() {
    return list.head == null;
}

第二步：优化基础构造逻辑（可选） #

当前Stack的默认构造会生成5个随机元素，会导致临时栈存在脏数据，可添加空构造方法避免该问题：

1. 给LinkedListOfInts添加无参空构造

public LinkedListOfInts() {
    head = null;
    tail = null;
}

2. 给Stack添加无参构造初始化空栈

public Stack() {
    list = new LinkedListOfInts();
}

第三步：实现合规的reverse方法 #

两种符合变量约束的实现方案可选：

方案1：双临时栈迭代实现（与你原有思路一致）

通过两次中转倒栈实现反转，逻辑简单易懂，符合变量要求：

public void reverse() {
    if (isEmpty()) return;
    Stack tmpB = new Stack();
    // 原栈全部元素倒入第一个临时栈
    while (!this.isEmpty()) {
        tmpB.push(this.pop());
    }
    Stack tmpC = new Stack();
    // 第一个临时栈元素倒入第二个临时栈，顺序与原栈一致
    while (!tmpB.isEmpty()) {
        tmpC.push(tmpB.pop());
    }
    // 第二个临时栈元素倒回原栈，完成反转
    while (!tmpC.isEmpty()) {
        this.push(tmpC.pop());
    }
}

方案2：递归实现（仅用int类型变量，无额外栈开销）

通过递归将栈顶元素逐一插入栈底完成反转，空间效率更高：

public void reverse() {
    if (isEmpty()) return;
    int top = pop();
    reverse();
    insertAtBottom(top);
}

private void insertAtBottom(int item) {
    if (isEmpty()) {
        push(item);
        return;
    }
    int top = pop();
    insertAtBottom(item);
    push(top);
}

内容的提问来源于stack exchange，提问作者Ezequiel Soler