C++中栈的递归反转实现及指定元素递归弹出逆序打印问题咨询

Hey there! Let's break down your two technical requirements step by step, focusing on the recursive logic you're finding tricky. I'll include working C++ code examples and clear explanations for each problem.

The core idea for recursive stack reversal is to "peel off" elements one by one, recursively reverse the remaining stack, then place each peeled element at the bottom of the reversed stack. We'll need two recursive functions: one for the main reversal, and a helper to insert an element at the stack's bottom.

#include <iostream>
#include <vector>
using namespace std;

// Global stack setup (matches your scenario: elements [1,2,3,4,5] from bottom to top, Top points to 5 (index 4))
vector<int> stack = {1, 2, 3, 4, 5};
int Top = 4;

// Helper function to insert a value at the bottom of the stack
void insertAtBottom(int val) {
    if (Top == -1) {
        stack.push_back(val);
        Top++;
    } else {
        // Temporarily pop the top element
        int temp = stack[Top];
        stack.pop_back();
        Top--;
        // Recursively insert target value at the bottom
        insertAtBottom(val);
        // Push the temporarily popped element back
        stack.push_back(temp);
        Top++;
    }
}

// Main recursive function to reverse the stack
void reverseStack() {
    if (Top == -1) {
        return;
    }
    // Pop the current top element
    int temp = stack[Top];
    stack.pop_back();
    Top--;
    // Recursively reverse the remaining stack
    reverseStack();
    // Insert the popped element at the bottom of the reversed stack
    insertAtBottom(temp);
}

How it works: #

• reverseStack keeps popping elements until the stack is empty. As the recursion unwinds, each popped element is inserted at the bottom of the stack via insertAtBottom.
• The helper insertAtBottom uses the same recursive pattern: it clears the stack temporarily, adds the target value, then pushes all the temporarily popped elements back on top.

Your scenario has a stack with elements [1,2,3,4,5] (bottom to top), Top pointing to 5 (index 4). You need to pop the top three elements (5,4,3) and print them in the order 5 4 3. Your original trav() function doesn't use recursion and doesn't target the correct elements—here's a recursive solution tailored to your needs:

// Reusing the same global stack and Top variable from above
void printAndPopLastThree(int count = 0) {
    // Base case: stop if we've popped 3 elements, or the stack has fewer than 3 elements left
    if (count == 3 || Top < 2) {
        return;
    }
    // Pop the current top element
    int current = stack[Top];
    stack.pop_back();
    Top--;
    // Print immediately to get the expected order: 5 4 3
    cout << current << " ";
    // Recurse to process the next element
    printAndPopLastThree(count + 1);
}

// If you ever needed to print them in reverse order (3 4 5), you'd print during recursion unwinding:
void printReverseLastThree(int count = 0) {
    if (count == 3 || Top < 2) {
        return;
    }
    int current = stack[Top];
    stack.pop_back();
    Top--;
    // Recurse first, then print
    printReverseLastThree(count + 1);
    cout << current << " ";
}

Key Notes for Your Original Code: #

Your trav() function uses hardcoded pop() calls and a loop, which lacks flexibility and doesn't leverage recursion. The recursive approach above uses a count parameter to track how many elements we've processed, ensuring we only pop and print exactly three elements while respecting the Top ≥ 2 precondition (we check Top < 2 as a safety base case to avoid errors).

To test this, simply call printAndPopLastThree()—it will output 5 4 3 as expected, and leave the stack with elements [1,2] (Top = 1).

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