两个栈实现一个队列，C语言实现，队列可伸缩，容纳任意数目的元素。
一、思路：1、创建两个空栈A和B；2、A栈作为队列的入口，B栈作为队列的出口；3、入队列操作：即是入栈A；4、出队列操作：若栈B为空，则将A栈内容出栈并压人B栈，再出 B栈；不为空就直接出栈；
二、代码：
1、头文件：stack_to_queue.h：封装了:队列、栈的数据结构和各种操作的函数。
1 #ifndef STACK_TO_QUEUE_H
2 #define STACK_TO_QUEUE_H
3
4 #include<stdio.h>
5 #include<stdlib.h>
6
7 #define ALLOC_SIZE 512
8 #define ElemType int
9
10 typedef struct sqstack
11 {
12 ElemType *top; //栈顶指针
13 ElemType *base; //栈底指针
14 ElemType stack_size; //栈目前的元素数目
15 }SqStack; //顺序栈
16
17 typedef struct sqqueue
18 {
19 SqStack front; //队列头，出口，
20 SqStack rear; //队列尾，入口
21 }SqQueue;
22
23 /*栈的初始化函数*/
24 void InitStack(SqStack *s)
25 {
26 if((s->top=(ElemType*)malloc(ALLOC_SIZE*sizeof(ElemType)))==NULL)
27 {
28 printf("stack malloc error\n");
29 exit(1);
30 }
31 s->base=s->top;
32 s->stack_size=ALLOC_SIZE;
33 }
34
35 /*出栈函数，栈为空时返回0，成功出栈时返回1*/
36 int pop_stack(SqStack *s,ElemType *data)
37 {
38 if(s->top!=s->base)
39 {
40 s->top--;
41 *data=*s->top;
42 return 1;
43 }
44 else //返回值为0，表示栈为空
45 {
46 return 0;
47 }
48 }
49
50 /*入栈函数*/
51 void push_stack(SqStack *s,ElemType data)
52 {
53 if((s->top-s->base)>=s->stack_size)
54 {
55 if((s->base=(ElemType *)realloc(s->base,(s->stack_size+ALLOC_SIZE)*sizeof(ElemType)))==NULL)
56 {
57 printf("stack realloc error\n");
58 exit(1);
59 }
60 else
61 {
62 s->top=s->base+s->stack_size;
63 s->stack_size+=ALLOC_SIZE;
64 }
65 }
66 *(s->top)=data;
67 s->top++;
68 }
69
70 /*队列初始化函数*/
71 void InitQueue(SqQueue *q)
72 {
73 SqStack A,B;
74
75 InitStack(&A);
76 InitStack(&B);
77 q->front=B; //将栈B作为队列的出口
78 q->rear=A; //将栈A作为队列的入口
79 }
80
81 /*入队列函数*/
82 void push_queue(SqQueue *q,ElemType data)
83 {
84 push_stack(&q->rear,data);
85 }
86
87 /*出队列函数，队列为空时返回0，成功出队列返回1*/
88 int pop_queue(SqQueue *q,ElemType *data)
89 {
90 if((pop_stack(&q->front,data))==0) //如果作为出口的栈为空，就将入口栈的内容压入
91 {
92 while((pop_stack(&q->rear,data))!=0)
93 {
94 push_stack(&q->front,*data);
95 }
96 }
97 else //否则，返回1
98 {
99 return 1;
100 }
101 if((pop_stack(&q->front,data))==0) //如果将入口栈的内容压人后还为空，说明此时队列为空
102 {
103 return 0;
104 }
105 else
106 {
107 return 1;
108 }
109 }
110 #endif
2、主函数：main.c:只为测试用，通过for循环让1000个数0-999入队列，再打印。
1 #include<stdio.h>
2 #include"stack_to_queue.h"
3
4 int main()
5 {
6 SqQueue q;
7 int i,data;
8
9 InitQueue(&q);
10 for(i=0;i<1000;i++)
11 {
12 push_queue(&q,i);
13 }
14 while((pop_queue(&q,&data))!=0)
15 {
16 printf("%d ",data);
17 }
18
19 return 0;
20 }
之前写的时候犯了一个错误，在stack_to_queue.h中的62行，使用realloc函数重新分配内存后，要将top指针也指向新的位置，我漏掉了这一步，导致出错，检查了很久，最后的解决过程在这：http://q.cnblogs.com/q/54337/
标签: 队列, 两个栈实现一个队列
