栈和队列之间的相互转化

7-李建涛
7-李建涛   编辑于 2018-10-01 12:57
阅读量: 116

队列实现栈

需要两个队列data,help,

因为队列是先进先出,想要模拟栈的结构,每次取栈顶的元素也就相当于取队列中队尾的元素,

要取data队列的队尾元素,需将最后一个元素前面的先取走,才能取到最后一个元素,

所以,将前面的元素逐个弹出到help队列中,顺序和在data中是一致的,只是缺少最后一个元素其他都一样,这样就可以取到data中的最后一个元素了,

此时data中已没有了元素,而help中的元素除了没有取的最后一个元素顺序和原来的data一样,所以把help作为data,data作为help进行下一次的pop操作

至于push操作 都是从一个位置进入,要不是队尾要不是栈顶,没有改变。

栈实现队列

栈实现队列的过程较队列实现栈容易一些

因为栈是先进后出的结构,想要模拟堆先进先出的结构,需要两个栈push pop 从push中压入元素,pop中弹出元素

我们还是先看从模拟的队列中取元素,想要取队头的元素,先通过一个一个取并放入pop中的方式将push中的元素逆置,这样队头的元素就暴露在pop要取得第一个位置,最先被压入栈push的元素也可以按原顺序最先被取出,

但是这里应注意两点 一是push中的元素要放入pop中便一次放完不能留下元素,二是pop如果不为空不能从push中取元素 ,否则会打乱顺序。

       代码量不小,我也没有具体实现过,网上有现成的代码我就不写了。

       这种做法我不知道有什么意义,因为直接限制线性表的操作才符合常规的做法,但也不排除面试的过程会有两个逻辑结构相互转换的过程,比如给你一个队列却偏偏让你实现一个常用栈来实现的功能,这种灵活的运用,也是拓宽思维逻辑一种方法。

       另外祝大家国庆节快乐!

 

收藏 转发 评论 2
    stack<int>st;
    queue<int>q;
    while(!st.empty()){
        q.push(st.top());
        st.pop();
    }
你们说的是这个吗(手动滑稽)

正好之前写过https://blog.csdn.net/hebtu666/article/details/82740895