如何正确实现C++单链表有序栈的合并（最小元素在栈顶）

问题描述 #

需要开发一个C++函数，接收两个已排序的栈A和B（最小元素在栈顶），创建一个新的合并后有序的栈（最小元素在栈顶）。仅允许使用pop、push、size、top等标准栈操作，禁止使用数组等其他数据结构。栈需通过单链表实现，包含Stack类和Node类。

当前代码运行后输出顺序错误：

• 当前输出：10 9 8 7 6 5 4 3 2 1
• 期望输出：1 2 3 4 5 6 7 8 9 10

错误原因分析 #

问题出在mergeSortedStacks函数的逻辑上：
原函数每次将两个栈中较小的元素直接push到目标栈merged中，但由于栈后进先出的特性，最小的元素会被不断压入栈底，最终目标栈的栈顶是最大的元素，打印时自然呈现从大到小的顺序。

我们需要先把合并后的元素按从大到小的顺序存入临时栈，再将临时栈的元素反转到目标栈，这样目标栈的栈顶就是最小元素，满足要求。

修正后的完整代码 #

#include <initializer_list>
#include <iostream>

// Node class for a minimum singly linked list
struct Node {
    int data{};     // Data part 
    Node* next{};   // Link
};

// Stack, implemented as singly linked list with only minimum necessary functions
class Stack {

    Node* head{};               // Head of singly linked list
    int numberOfElements{};     // Housekeeping. Stack size
public:
    Stack() {};                 // Default constructor. Do nothing
    // Convenience function. Build stack from initailizer list
    Stack(const std::initializer_list<int>& il) { for (const int i : il) push(i); }

    // And destructor, will release memory
    ~Stack() {
        Node* temp = head;          // Start with the head
        while (temp) {              // Iterate along the list
            Node* toDelete = temp;  // Remember Node that must be deleted
            temp = temp->next;      // Goto next element
            delete toDelete;        // Delete Remebered Element
        }
    }
    void push(const int value) {    // Push a new element onto the stack. Insert at beginning
        Node* temp = new Node;      // Allocate memory for a new node
        temp->data = value;         // Assign data part to new Node
        temp->next = head;          // This will be the new head, so, next will point to previous head
        head = temp;                // Set head pointer to new Node
        ++numberOfElements;         // Bookkeeping, increment size
    }
    void pop() {                    // Simply delete the first element in the linked list
        if (head) {                 // If there is something in the list at all
            Node* temp = head;      // Remember current head Node
            head = head->next;      // New head will be the current heads next node
            delete temp;            // Delete old head
            --numberOfElements;     // Bookkeeping, decrement size
        }
    };
    int top() const { return head ? head->data : 0; }   // Simply return data from head node
    int size() const { return numberOfElements; }       // expose size to outside world 

    void print() {                          // Helper for printing debug output
        Node* temp = head;                  // We will iterate over the list beginning at the head
        while (temp) {                      // As long as we are not at the end of the list
            std::cout << temp->data << ' '; // Show data
            temp = temp->next;              // And continue with next node
        }
        std::cout << '\n';
    }
};

// 修正后的合并函数
void mergeSortedStacks(Stack& s1, Stack& s2, Stack& merged) {
    Stack tempStack;

    // 先将元素按从大到小的顺序存入临时栈
    while (s1.size() || s2.size()) {
        if (s1.size() && s2.size()) {
            // 取较大的元素压入临时栈
            if (s1.top() > s2.top()) {
                tempStack.push(s1.top());
                s1.pop();
            } else {
                tempStack.push(s2.top());
                s2.pop();
            }
        } else if (s1.size()) {
            tempStack.push(s1.top());
            s1.pop();
        } else if (s2.size()) {
            tempStack.push(s2.top());
            s2.pop();
        }
    }

    // 将临时栈的元素反转到目标栈，此时目标栈栈顶为最小元素
    while (tempStack.size()) {
        merged.push(tempStack.top());
        tempStack.pop();
    }
}

// Test
int main() {
    Stack s1{ 10, 8, 6, 4 ,2 };
    s1.print();
    Stack s2{ 9, 7, 5, 3, 1};
    s2.print();

    Stack m{};
    mergeSortedStacks(s1, s2, m);
    m.print();
}

修正说明 #

• 新增临时栈tempStack，用于暂存合并后的元素，此时临时栈的栈顶为最大元素。
• 合并逻辑改为比较两个栈的top值，将较大的元素压入临时栈，确保临时栈内元素从栈顶到栈底是从大到小排列。
• 最后将临时栈的元素逐个弹出并压入目标栈merged，完成反转，使得merged的栈顶为最小元素，符合题目要求。

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