栈和队列

使用两个栈实现一个队列，两个队列实现一个栈

总感觉这像是一个面试题 ——hugo

栈是一种后入先出(Last In First Out, LIFO)的数据结构，队列是一种先进先出(First In First Out, FIFO)的数据结构。

两个栈实现一个队列

思路一：s1进行入队操作,s2进行出队操作

入队：

push_s1(item)

出队：

while(top_s1 != -1){
    tmp = pop_s1();
    push_s2(tmp);
}
pop_s2();
while(top_s2 != -1){
    tmp = pop_s2();
    push_s1(tmp);
}

即s1式负责元素的存储，s2作为过渡栈，每次元素出队矩利用到s2;

但是整个过程中出队入队显然太麻烦了，那么对此进行优化有：

我们其实可以发现对s2中的top元素pop后其实不一定需要再全部倒回s1，

那么就有：

思路二：s1进行入队操作,s2进行出队操作

入队：

push_s1(item)

出队：

if(top_s2 == -1){
    while(top_s1 != -1){
    	tmp = pop_s1();
    	push_s2(tmp);
	}
	pop_s2();
}else{
    pop_s2();
}

思路二主要就是减少了两个栈之间元素的转移。

两个队列实现一个栈

思路一：q1负责出栈，q2只是一个中转

入栈：

q1[rear1++]=item

出栈：

while(front1 < rear1 - 1){
    tmp = q1[++front1];
    q2[rear2++] = tmp;
}
item = q1[++front1];
while(front2 < rear2){
    tmp = q2[++front2];
    q1[rear1++] = tmp;
}

思路二：q1和q2都负责进出栈

入栈：

如果q1和q2都为空，随便入一个队即可，这里选择入q1；

如果一个队列为空，另一个队列非空，则入非空队；

如果都非空，则入q1即可。

if(rear1 == front + 1 && rear2 == front2 + 1){
    q1[++rear1] = item;
}else if(rear2 == front2 + 1){
    q2[++rear2] = item;
}else{
    q1[++rear1] = item;
}

出栈：

如果一个队列为空，另一个队列非空，则仿造思路1将非空队列的队尾元素出队；

如果两个队列都非空，则将q1的队尾元素出队，其他元素入队q2。即把不为空的队列中除最后一个元素外的所有元素移动到另一个队列中，然后出队最后一个元素。