使用两个栈实现一个队列

栈：后进先出。
队列：先进先出。

入队列：
直接入栈1。
出队列：

返回队列的队尾元素：

返回队列的队头元素：
这里写图片描述
队列为空：
栈1为空&&栈2为空。
队列元素个数：
栈1的元素个数+栈2的元素个数。

参考代码：

设置一个队列由两个栈组成：

typedef struct Queue { stack s1; stack s2; }queue;

其中栈：

#define Max 10 #define Datatype int typedef struct stack { Datatype data[Max]; int top ; }stack;

队列的初始化：
队列的初始化即两个栈的初始化

void InitQueue(queue *q) { assert(q); InitStack(&q->s1); InitStack(&q->s2); }

栈的初始化：

 void InitStack(stack *s) { assert(s); s->top = 0; memset(s->data, 0, Max*sizeof(Datatype)); }

入队列：
直接入栈1

void PushQueue(queue *q, Datatype d) { assert(q); //入栈1 PushStack(&q->s1, d); }

入栈：

void PushStack(stack *s, Datatype d) { assert(s); if (s->top >= Max) { printf("队列已满!\n"); return; } s->data[s->top++] = d; }

出队列：
栈2不为空即栈2出栈，若栈2为空，将栈1的元素导入栈2，栈2出栈。

void PopQueue(queue *q) { assert(q); if (EmptyQueue(q)) { printf("队列为空!\n"); return; } //如果栈2为空，将栈1中的元素移入栈2 if (EmptyStack(&q->s2)) { while (!EmptyStack(&q->s1)) { PushStack(&q->s2, TopStack(&q->s1)); PopStack(&q->s1); } } //栈2的栈顶 PopStack(&q->s2); }

出栈：

 void PopStack(stack *s) { assert(s); if (s->top == 0) return; s->top--; }

返回栈顶元素：

Datatype TopStack(stack *s) { assert(s); return s->data[s->top - 1]; }

返回队尾元素：
即栈1的栈顶元素，若栈1为空，将栈2的元素移入栈1，栈1栈顶出栈。

//栈1的栈顶 Datatype QueueBack(queue *q) { assert(q); if (EmptyQueue(q)) { printf("队列为空!\n"); return -1; } //如果栈1为空，将栈2中的元素移入栈1 if (EmptyStack(&q->s1)) { while (!EmptyStack(&q->s2)) { PushStack(&q->s1, TopStack(&q->s2)); PopStack(&q->s2); } } //栈1的栈顶 return TopStack(&q->s1); }

返回队头元素：
即栈2的栈顶元素，若栈2为空，将栈1的元素移入栈2，返回栈2的栈顶。

//栈2的栈顶 Datatype QueueFront(queue *q) { assert(q); if (EmptyQueue(q)) { printf("队列为空!\n"); return -1; } //如果栈2为空，将栈2中的元素移入栈1 if (EmptyStack(&q->s2)) { while (!EmptyStack(&q->s1)) { PushStack(&q->s2, TopStack(&q->s1)); PopStack(&q->s1); } } //栈2的栈顶 return TopStack(&q->s2); }

判断队列是否为空：
队列为空即两个栈均为空。

//栈1为空&&栈2为空 int EmptyQueue(queue *q) { assert(q); return EmptyStack(&q->s1) && EmptyStack(&q->s2); }

栈是否为空：（判断top是否等于0）

int EmptyStack(stack *s) { assert(s); return 0 == s->top; }

队列元素个数：
栈1的元素个数加栈2的元素个数。

//栈1元素个数+栈2元素个数 int SizeQueue(queue *q) { assert(q); return SizeStack(&q->s1) + SizeStack(&q->s2); }

栈元素的个数：

int SizeStack(stack *s) { assert(s); return s->top; }

 整体代码：

.h文件

#include 
               #include 
               #include 
               #include 
               #define Max 10 #define Datatype int typedef struct stack { Datatype data[Max]; int top ; }stack; typedef struct Queue { stack s1; stack s2; }queue; //初始化对列 void InitQueue(queue *q); //入对列 void PushQueue(queue *q, Datatype d); //对列元素个数 int SizeQueue(queue *q); //对列尾 int QueueBack(queue *q); //对列尾 int QueueFront(queue *q); //出对列 void PopQueue(queue *q);

.c文件

#include"TwoStack_Queeue.h" //1.初始化栈 void InitStack(stack *s) { assert(s); s->top = 0; memset(s->data, 0, Max*sizeof(Datatype)); } //1.初始化队列 void InitQueue(queue *q) { assert(q); InitStack(&q->s1); InitStack(&q->s2); } //入栈1 void PushStack(stack *s, Datatype d) { assert(s); if (s->top >= Max) { printf("队列已满!\n"); return; } s->data[s->top++] = d; } //入队列(入栈1) void PushQueue(queue *q, Datatype d) { assert(q); //入栈1 PushStack(&q->s1, d); } //栈元素个数 int SizeStack(stack *s) { assert(s); return s->top; } //队列元素个数 int SizeQueue(queue *q) { assert(q); return SizeStack(&q->s1) + SizeStack(&q->s2); } //栈空 int EmptyStack(stack *s) { assert(s); return 0 == s->top; } //队列空 int EmptyQueue(queue *q) { assert(q); return EmptyStack(&q->s1) && EmptyStack(&q->s2); } //出栈 void PopStack(stack *s) { assert(s); if (s->top == 0) return; s->top--; } //返回栈顶元素 Datatype TopStack(stack *s) { assert(s); return s->data[s->top - 1]; } //出队列 void PopQueue(queue *q) { assert(q); if (EmptyQueue(q)) { printf("队列为空!\n"); return; } //如果栈2为空，将栈1中的元素移入栈2 if (EmptyStack(&q->s2)) { while (!EmptyStack(&q->s1)) { PushStack(&q->s2, TopStack(&q->s1)); PopStack(&q->s1); } } //栈2的栈顶 PopStack(&q->s2); } //队列尾 栈1的栈顶 Datatype QueueBack(queue *q) { assert(q); if (EmptyQueue(q)) { printf("队列为空!\n"); return -1; } //如果栈1为空，将栈2中的元素移入栈1 if (EmptyStack(&q->s1)) { while (!EmptyStack(&q->s2)) { PushStack(&q->s1, TopStack(&q->s2)); PopStack(&q->s2); } } //栈1的栈顶 return TopStack(&q->s1); } //队列头 栈2的栈顶 Datatype QueueFront(queue *q) { assert(q); if (EmptyQueue(q)) { printf("队列为空!\n"); return -1; } //如果栈1为空，将栈2中的元素移入栈1 if (EmptyStack(&q->s2)) { while (!EmptyStack(&q->s1)) { PushStack(&q->s2, TopStack(&q->s1)); PopStack(&q->s1); } } //栈2的栈顶 return TopStack(&q->s2); }

测试文件：

#include"TwoStack_Queeue.h" void Test2StackToQueue() { queue q; InitQueue(&q); PushQueue(&q, 1); PushQueue(&q, 2); PushQueue(&q, 3); PushQueue(&q, 4); PushQueue(&q, 5); printf("%d\n", SizeQueue(&q)); printf("队尾 = %d\n", QueueBack(&q)); printf("队头 = %d\n", QueueFront(&q)); PopQueue(&q); PushQueue(&q, 5); PushQueue(&q, 6); printf("%d\n", SizeQueue(&q)); printf("队尾 = %d\n", QueueBack(&q)); printf("队头 = %d\n", QueueFront(&q)); } int main() { Test2StackToQueue(); system("pause"); return 0; }