BFS裸题，在搜索中模拟栈的弹出和压入即可

注意，代码全篇使用STL，不适用C语言题解

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

vector<char> ans;

void dfs(stack<char>& search_stack, deque<char>& search_queue)
{
    // 1. 模拟栈和搜索队列都为空，则输出答案
    if(search_stack.empty() && search_queue.empty())
    {
        for(const auto& c : ans)
        {
            cout << c;
        }
        cout << endl;
        return;
    }
    // 2. 模拟栈弹出
    if(!search_stack.empty())
    {
        // 状态储存
        char pop_char = search_stack.top();
        ans.push_back(pop_char);
        //cout << "pop: " << pop_char << endl;
        search_stack.pop();

        dfs(search_stack, search_queue);
        // 状态回溯
        ans.pop_back();
        search_stack.push(pop_char);
    }
    // 3. 模拟栈压入
    if(!search_queue.empty())
    {
        // 状态储存
        char front_char = search_queue.front();
        search_stack.push(front_char);
        //cout << "push: " << front_char << endl;
        search_queue.pop_front();
        
        dfs(search_stack, search_queue);
        // 状态回溯
        search_queue.push_front(front_char);
        search_stack.pop();
    }
}

int main() 
{
    string words;
    deque<char> search_queue;
    stack<char> search_stack;

    cin >> words;
    for(const auto& c : words)
    {
        search_queue.push_back(c);
    }
    dfs(search_stack, search_queue);
    return 0;
}