通过两个队列实现一个栈（C语言）

stackBy2Queue.h文件

#pragma once#define max_size 1000typedef char DataType;typedef struct Queue
{DataType data[max_size];int head;int tail;//队列中有效元素个数int size;
}Queue;typedef struct Stack
{Queue queue1;Queue queue2;//栈中有效元素个数int size;
}Stack;
//初始化函数
void StackInit(Stack *stack);
//销毁函数
void StackDestroy(Stack *stack);
//入栈操作函数
void StackPush(Stack *stack,DataType value);
//出栈操作函数
void StackPop(Stack *stack);
//取栈顶元素函数
int StackGetTop(Stack *stack,DataType *value);

stackBy2Queue.c文件

#include<stdio.h>
#include"stackBy2Queue.h"#define Test_Header printf("\n==========%s==========\n",__FUNCTION__);//队列初始化函数
void QueueInit(Queue *queue)
{if(queue == NULL){//非法输入return;}queue->head = 0;queue->tail = 0;queue->size = 0;
}
//队列销毁函数
void QueueDestroy(Queue *queue)
{if(queue == NULL){//非法输入return;}queue->head = 0;queue->tail = 0;queue->size = 0;
}
//入队列操作函数
void QueuePush(Queue *queue,DataType value)
{if(queue == NULL){//非法输入return;}if(queue->size >= max_size){//队列满了return;}queue->data[queue->tail++] = value;queue->size++;if(queue->tail > max_size){//如果tail走到了队列的尾部queue->tail = 0;}
}
//出队列操作函数
void QueuePop(Queue *queue)
{if(queue == NULL){//非法输入return;}if(queue->size == 0){//空队列return;}if(queue->head >= max_size){//如果head走到了队列的最后一个元素//呢出队列以后继续回到队列一开始的地方//就相当于是将最后一个元素出对队列queue->head = 0;}//否则直接将head往后移动一步queue->head++;//将对列元素个数-1queue->size--;if(queue->size == 0){queue->head = 0;queue->tail = 0;}
}
//取队首元素函数
int QueueGetTop(Queue *queue,DataType *value)
{if(queue == NULL){//非法输入return 0; }if(queue->size == 0){//空队列return 0;}*value = queue->data[queue->head];return 1;
}
void Print(Queue *queue)
{if(queue == NULL){//非法输入return;}if(queue->size == 0){return;}if(queue->head < queue->tail){int i = queue->head;for(;i < queue->tail;i++){printf("%c ",queue->data[i]);}}else{int i = queue->head;while(queue->head < max_size){printf("%c ",queue->data[queue->head]);queue->head++;}queue->head = 0;for(;i < queue->tail;i++){printf("%c ",queue->data[i]);}}printf("\n\n");
}

以下为通过两个队列实现一个栈的入栈，出栈和取栈顶元素的操作

//栈初始化函数
void StackInit(Stack *stack)
{if(stack == NULL){//非法输入return;}QueueInit(&stack->queue1);QueueInit(&stack->queue2);stack->size = 0;
}
//栈销毁函数
void StackDestroy(Stack *stack)
{if(stack == NULL){//非法输入return;}QueueDestroy(&stack->queue1);QueueDestroy(&stack->queue2);stack->size = 0;
}

入栈操作思路：
情况1：两个队列都为空那就随便哪一个队列将元素入队列即可，也就相当于入栈操作，如下图（虚线表示模拟一个栈）
这里写图片描述
情况2：其中一个队列有元素，一个队列没有元素，则将元素插入到有元素的队列中，如下图，此时待入栈的c和d要插入到队列1中

//入栈操作函数
void StackPush(Stack *stack,DataType value)
{if(stack == NULL){//非法输入return;}//每次入栈时找到队列不为空的那一个队列入队列（相当于入栈）//或者两个栈都为空时随便入哪一个队列都行if(stack->queue1.size != 0){//队列1不为空QueuePush(&stack->queue1,value);}else{//队列2不为空或者两个队列都为空QueuePush(&stack->queue2,value);}//每入栈一个元素将栈的有效元素个数+1stack->size++;
}

出栈操作思路：如图所示，此时队列1 当中有元素
这里写图片描述
但是由于队列只能从队首将元素出队列，而我们入栈的元素顺序是a b c d,所以根据栈后进先出的特点，此时出栈的元素应该是d,所以我们要将队列1 中的元素移动到一个空队列中也就是队列2，但是我们必须留下队列1中的队尾的最后一个元素，只剩下最后一个元素时，将这个元素出队列，就刚好模拟了栈的出栈操作。
这里写图片描述

//出栈操作函数
void StackPop(Stack *stack)
{if(stack == NULL){//非法输入return;}if(stack->size == 0){//空栈return;}Queue *from = NULL;Queue *to = NULL;//将from指向有元素的队列，to指向没有元素的队列if(stack->queue1.size != 0){from = &stack->queue1;to = &stack->queue2;}else{from = &stack->queue2;to = &stack->queue1;}//将from中的元素到腾到to中（但是from中必须要留下最后一个元素用于最后的出队列也就是出栈操作）while(from->size != 1){DataType top;//取到from队列队首元素的值QueueGetTop(from,&top);//然后对from队列进行一次出栈操作QueuePop(from);//将从from队列取到的队首元素值插入到to队列中QueuePush(to,top);}//循环结束//此时from中就剩下最后一个元素将其出队列也就完成出栈操作QueuePop(from);//每出栈一次就将栈的有效元素个数-1stack->size--;
}

取栈顶元素思路：取栈顶元素操作和出栈操作类似，唯一不同的就是，当我们将元素移动到只剩下最后一个元素的时候，我们需要的是读取到该元素的值（取队首元素操作就行了），而这个元素依旧存在于该栈中，所以为了确保栈的元素不被破坏，读取完元素值以后我们依旧要把该元素移动到另外那个队列中去。

//取栈顶元素函数
int StackGetTop(Stack *stack,DataType *value)
{if(stack == NULL || value == NULL){//非法输入return 0;}if(stack->size == 0){//空栈return 0;}Queue *from = NULL;Queue *to = NULL;//将from指向有元素的队列，to指向没有元素的队列if(stack->queue1.size != 0){from = &stack->queue1;to = &stack->queue2;}else{from = &stack->queue2;to = &stack->queue1;}//将from中的元素到腾到to中（但是from中必须要留下最后一个元素用于最后的取队首元素操作也就是取栈顶元素操作）while(from->size != 1){DataType top;//取到from队列队首元素的值QueueGetTop(from,&top);//然后对from队列进行一次出栈操作QueuePop(from);//将从from队列取到的队首元素值插入到to队列中QueuePush(to,top);}//循环结束//此时from中就剩下最后一个元素//对from队列取队首元素操作（也就是取栈顶元素）int ret = QueueGetTop(from,value);//当我们取到栈顶元素之后，在将该元素从from队列出队列QueuePop(from);//并且将该元素入to队列//否则栈就被破坏了QueuePush(to,*value);return ret;
}
//打印函数便于观察测试结果(思路不做解释)
void PrintStackElem(Stack *stack,const char *msg)
{printf("[%s]\n",msg);if(stack == NULL){//非法输入return;}if(stack->size == 0){//空栈return;}Queue *print = NULL;if(stack->queue1.size == 0){print = &stack->queue2;}else{print = &stack->queue1;}Print(print);
}//以下为测试函数
void TestStackBy2Queue()
{Test_Header;Stack stack;//初始化StackInit(&stack);//入栈函数测试StackPush(&stack,'a');StackPush(&stack,'b');StackPush(&stack,'c');StackPush(&stack,'d');PrintStackElem(&stack,"入栈4个元素expected：a b c d");//取栈顶元素测试DataType top;int ret = StackGetTop(&stack,&top);printf("expected ret = 1,actual ret = %d\n",ret);printf("expected top = d,actual top = %c\n",top);//出栈函数测试StackPop(&stack);StackPop(&stack);PrintStackElem(&stack,"出栈两个元素之后expected: a b");//取栈顶元素函数测试2  ret = StackGetTop(&stack,&top);printf("expected ret = 1,actual ret = %d\n",ret);printf("expected top = b,actual top = %c\n",top);StackPop(&stack);StackPop(&stack);PrintStackElem(&stack,"将剩下的两个元素出栈之后expected:");//取栈顶元素函数测试3ret = StackGetTop(&stack,&top);printf("expected ret = 0,actual ret = %d\n",ret);//销毁栈StackDestroy(&stack);
}
//主函数调用测试函数
int main()
{TestStackBy2Queue();return 0;
}