众所周知栈和队列是两个中不同的数据结构，栈是先入后出，队列是先入先出，虽然栈和队列有不同之处，但是他们之间也有相互的联系 两个栈实现一个队列了解一下
首先我们需要两个栈S1，S2,通过两个栈之间元素的交换从而达到先入先出的目的 所以我们对队列Queue定义为 typedef struct Queue { Stack * S1; Stack * S2; size_t _size; } Queue ; 所以我们这里也要对队列进行初始化 void QueueByTwoStackInit( Queue * q ) { StackInit( q ->S1); //对栈S1进行初始化 StackInit( q ->S2); //对栈S2进行初始化 q ->_size = 0; } 这里我们用S1来入元素，S2来出元素
所以这里入队列的入队就很简单，就是把元素入到S1这个栈里面，同时size++ void QueueByTwoStackPush( Queue * q , DataType x ) //入队 { StackPush( q ->S1, x ); //把x入到栈S1中 q ->_size++; }
出队列时候我们分两种情况， 第一种情况，S2为空，我们这时候把依次S1里面的元素出栈入到S2中，那么这时候S2栈顶的元素就是最早入队的元素，出队只要对S2进行出栈即可
第二种情况就是S2中有元素，那么直接对S2栈顶元素进行出栈就行，直到S2为空时候，再次变为第一种情况，再从S1中把元素拿过来，因为出队是在S2中，所以不影响S1中的正常入队
void QueueByTwoStackPop( Queue * q ) //出队 { if ( q ->_size == 0) //队列为空时没有元素可以出队，所以直接return return ; if (StackSize( q ->S2)) //如果S2不为空 { StackPop( q ->S2); //直接对S2进行出栈，size-- q ->_size--; } else //S2为空时 { while (StackSize( q ->S1)) //执行循环直到把S1所有元素拿到S2中 { StackPush( q ->S2, StackTop( q ->S1)); //把S1栈顶元素入到S2中 StackPop( q ->S1); //把S1栈顶元素pop掉 } StackPop( q ->S2); //当所有元素都在S2中时，对2栈顶元素出栈，size-- q ->_size--; } }
当然，上面利用了一些栈的函数接口，这里就只是对用两个栈实现一个队列的相关操作，栈的相关接口实现在这里就不过多涉及了