C语言-- 用队列实现栈的功能

• 思想：

        队列：先进先出

        栈：先进后出

        入栈：

        （1）定义两个队列：temp、data

        （2）数据先进入到temp队内

        （3）如果data队不为空，将data队内的数据依次出队进入到temp队内

        （4）将temp队内数据依次出队，进入到data队内

        思路演绎：

        拿1234举例，进行入栈，1234入栈结果应为栈顶元素为4：

        （注：下面的(2)(3)(4)对应着上面思路中的(2)(3)(4)步骤）

        第一次：

        （2）temp队内：1

        （3）data队内：NULL

        （4）temp队内：NULL； data队内：1

        第二次：

        （2）temp队内：2

        （3）data队内：NULL；temp队内：2  1

        （4）temp队内：NULL； data队内：2  1

        第三次：

        （2）temp队内：3

        （3）data队内：NULL；temp队内：3  2  1

        （4）temp队内：NULL； data队内：3  2  1

        第四次：

        （2）temp队内：4

        （3）data队内：NULL；temp队内：4  3  2  1

        （4）temp队内：NULL； data队内：4  3  2  1

         此时data队内的数据4321就是将1234进行入栈的结果，因为将1234入栈后，输出栈顶元素为4，而在data队列内出队的队头元素为4，符合入栈的结果。

• 用栈实现队列代码：

typedef struct Stack
{
    queue<int> data;//栈内只定义了一个最终的data队列
}MyStack;
 
//入栈
void Push(MyStack* ms, int value)
{
    queue<int>temp;//定义temp临时队列
    //1.将第一个数值入Temp队
    temp.push(value);
    //2.依次将data队列中所有的数据放到temp中
    while (!ms->data.empty())
    {
        temp.push(ms->data.front());
        ms->data.pop();
    }
    //3.将temp中的所有的数据再放到data队列中
    while (!temp.empty())
    {
        ms->data.push(temp.front());
        temp.pop();
    }
}
//出栈：将data元素出队即可
void Pop(MyStack* ms)
{
    ms->data.pop();
}
//获取栈顶元素：即为data队内的队头元素
int Top(MyStack* ms)
{
    return ms->data.front();
}
 
void main()
{
    MyStack ms;
    Push(&ms, 1);//栈顶元素1
    Push(&ms, 2);//栈顶元素1
    printf("top=%d\n", Top(&ms));//输出栈顶元素2验证入栈是否正确
    Pop(&ms);//出栈
    printf("top=%d\n", Top(&ms));//输出栈顶元素1验证出栈是否正确
}

•  用队列实现栈代码：

 
//作业：用两个栈实现队列的功能
typedef struct Queue
{
    stack <int>data;
}MyQueue;
void Push(MyQueue* ms, int value)
{
    stack<int>temp;//定义temp临时栈
    //1.将第一个数值入Temp栈
    temp.push(value);
    //2.依次将data队列中所有的数据放到temp中
    while (!ms->data.empty())
    {
        temp.push(ms->data.top());
        ms->data.pop();
    }
    //3.将temp中的所有的数据再放到data栈中
    while (!temp.empty())
    {
        ms->data.push(temp.top());
        temp.pop();
    }
}
void Pop(MyQueue* ms)
{
    ms->data.pop();
}
 
int Top(MyQueue* ms)
{
    return ms->data.top();
}
 
void main()
{
    MyQueue ms;
    Push(&ms, 1);//输出队头元素
    Push(&ms, 2);//队头元素1
    printf("top=%d\n", Top(&ms));//输出队头元素2验证入栈是否正确
    Pop(&ms);//出队
    printf("top=%d\n", Top(&ms));//输出队头元素1验证出栈是否正确
}

•  运行结果：