文章主要是介绍如何通过两个队列实现一个栈，文章内容包括实现原理和实现源码。

一、实现原理

首先看图1

                                                                               图1

首先两个队列queue1、queue2都是空队列，比方说我们一开始往栈内压入元素a,则我们选择把a插入两个任意队列一个。我们这里选择把a插入queue1。接着往栈内压入b、c两个元素，我们把它们都插入queue1。这个时候queue1包含三个元素a、b和c，其中a位于队列的头部，c位于队列的尾部。

接下来出栈一个元素，根据栈的后入先出原则，最后被压入的c应该最新被弹出。由于c位于queue1的尾部，而我们每次只能从队列的头部删除元素，因此我们可先从queue1中依次删除元素a、b并插入到queue2中，再从queue1删除元素c。这相当于从栈中弹出元素c。对于元素b可同理出栈。

接下来我们考虑往栈内压入一个元素d。此时queue1已经有一个元素，我们就把d插入到queue1的尾部。如果我们再从栈内出一个元素，此时被弹出的元素应该是最后被压入的d，由于d位于queue1的尾部，我们只能先从头删除queue1的元素并插入到queue2，直到queue1中遇到d再直接把它删除。

二、代码实现

代码实现的过程是先入栈0~9个整数，然后出栈最后5个数，然后再入栈5个数，最后再出栈所有的数。源码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef struct _QNode
{int data;struct _QNode *next;
}QNode;typedef struct _Queue
{QNode *front,*rear;
}Queue;/*入栈*/
void stack_in(Queue *q1, Queue *q2, int val)
{		QNode *p;if(q1==NULL || q2==NULL){printf("Error: queue is err!\n");return;}if(q1->front==q1->rear && q2->front==q2->rear){//printf("First stack in val:%d\n",val);/*if q1 and q2 is all empty,let data in q1*/p=(QNode *)malloc(sizeof(QNode));if(!p){printf("Error:malloc queue fail!\n");return;}p->data = val;p->next = NULL;q1->rear->next = p;q1->rear = p;//return;}else if(q1->front!=q1->rear){/*let data in queue who had data*///printf("Q1 stack in val:%d\n",val);p=(QNode *)malloc(sizeof(QNode));if(!p){printf("Error:malloc queue fail!\n");return;}p->data = val;p->next = NULL;q1->rear->next = p;q1->rear = p;}else{//printf("Q2 stack in val:%d\n",val);p=(QNode *)malloc(sizeof(QNode));if(!p){printf("Error:malloc queue fail!\n");return;}p->data = val;p->next = NULL;q2->rear->next = p;q2->rear = p;}return;
}/*出栈*/
int stack_out(Queue *q1,Queue *q2)
{int val;QNode *p,*q;if(q1==NULL && q2==NULL){return;}if(q1->front != q1->rear){/*q1队列中有元素*/q1->rear=q1->front;p=q1->front->next;q1->front->next=NULL;while(p->next){q=p;stack_in(q1,q2,p->data);	p=p->next;free(q);}		val=p->data;	free(p);return val;}else{/*q2队列中有元素*/q2->rear=q2->front;p=q2->front->next;q2->front->next=NULL;while(p->next){q=p;stack_in(q1,q2,p->data);	p=p->next;free(q);}		val=p->data;	free(p);return val;}	
}/*打印队列里的内容*/
void queue_print(Queue *Q)
{if(Q==NULL)return;QNode *p=NULL;p=Q->front->next;while(Q->rear != p){printf("Queue value:%d\n",p->data);p=p->next;}printf("Queue value:%d\n",p->data);
}/*队列初始化*/
void initQueue(Queue **Q)
{if(Q==NULL){return;}*Q=(Queue *)malloc(sizeof(Queue));if((*Q)==NULL){return;}(*Q)->front=(*Q)->rear=(QNode *)malloc(sizeof(QNode));
}int main()
{int i;	int val;Queue *queue1=NULL;Queue *queue2=NULL;initQueue(&queue1);initQueue(&queue2);for(i=0; i<10; i++){stack_in(queue1, queue2, i);}queue_print(queue1);for(i=0;i<5;i++)	{val=stack_out(queue1,queue2);printf("Stack out val:%d\n",val);	}for(i=11; i<=15; i++){stack_in(queue1, queue2, i);}for(i=0;i<10;i++)	{val=stack_out(queue1,queue2);printf("Stack out val:%d\n",val);	}return 0;		
}

执行的效果图如下：