Stack<==>Queue。使用栈实现队列的功能以及使用队列实现栈的功能
首先栈的原理是先入的后出,也就是First In Last Out(FILO)。队列的原理是先入先出 First In First Out(FIFO)
1.栈实现队列
原理:使用两个栈,一个用来进一个用来出。
push操作时候,往输入的栈push元素
pop操作的时候,先判断输出的栈有没有元素,如果没有就把输入栈里面元素依次后入先出的顺序给到输出栈,最后取出输出栈的元素。
2.队列实现栈
方法1:用一个辅助队列,每当有元素push进“栈”,则需要把队列的front位置给它空出来,方便后面直接pop()和top(),因此我们可以做两次搬家操作,来获得一个新的队列:
方法2:在每次push()操作时,我们直接从队列头开始,把每一个元素复制到队尾,然后删除队头的这个元素,这样push进来的新元素就到了front的位置: