目录
题目链接
图解思路
整体结构
实现过程
入队列
出队列
实现代码
MyQueue.h
MyQueue.c
stack.h
stack.c
test.c
题目链接
232. 用栈实现队列 - 力扣(LeetCode)
图解思路
整体结构
实现过程
入队列
插入数据时,插入到ist。
出队列
删除数据时,要求先入先出,解决方法是先看看ost有没有数据(第一次出队列一定没有数据,不需要看),没有就把ist的数据全部搬到ost,这样刚好把数据的顺序反过来,就可以先入先出了。
实现代码
MyQueue.h
#pragma once
#include"Stack.h"//定义“栈实现的队列”的结构体
typedef struct
{Stack* ist;//进数据的栈Stack* ost;//出数据的栈
} MyQueue;//创建队列
MyQueue* myQueueCreate();
//释放队列
void myQueueFree(MyQueue* q);
//入队列
void myQueuePush(MyQueue* q, STDataType x);
//出队列
STDataType myQueuePop(MyQueue* q);
//查看队头数据
STDataType myQueuePeek(MyQueue* q);
//查看是否空
bool myQueueEmpty(MyQueue* q);
MyQueue.c
#include"MyQueue.h"//创建队列
MyQueue* myQueueCreate()
{MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));//申请队列空间if (NULL == q)//malloc失败退出程序{perror("malloc failed");exit(-1);}//调用Stack.h的函数初始化栈成员q->ist = STCreate();q->ost = STCreate();return q;//返回初始化好的队列的指针
}//释放队列
void myQueueFree(MyQueue* q)
{assert(q);//调用Stack.h的函数释放栈成员STDestroy(q->ist);STDestroy(q->ost);free(q);//释放队列空间
}//入数据
void myQueuePush(MyQueue* q, STDataType x)
{assert(q);STPush(q->ist, x);//入数据到ist
}//出数据
STDataType myQueuePop(MyQueue* q)
{assert(q);assert(!myQueueEmpty(q));//检查非空,空则没有数据可出if (STEmpty(q->ost))//ost为空,先移动ist的所有数据到ost,再出ost的数据{while (!STEmpty(q->ist))//移动ist的所有数据到ostSTPush(q->ost, STPop(q->ist));}return STPop(q->ost);//ost不为空,直接出ost的数据
}//查看队头数据
STDataType myQueuePeek(MyQueue* q)
{assert(q);assert(!myQueueEmpty(q));//检查非空,空则没有队头数据if (STEmpty(q->ost))//ost为空,先移动ist的所有数据到ost,再查看ost的栈顶数据{while (!STEmpty(q->ist))STPush(q->ost, STPop(q->ist));}return STTop(q->ost);//ost不为空,直接查看ost的栈顶数据
}//查看是否空
bool myQueueEmpty(MyQueue* q)
{assert(q);//ist与ost同时为空,队列才空return STEmpty(q->ist) && STEmpty(q->ost);
}
stack.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* a;int capacity;int top;
} Stack;Stack* STCreate();
void STDestroy(Stack* st);void STPush(Stack* st, STDataType x);
STDataType STPop(Stack* st);
STDataType STTop(Stack* st);
int STSize(Stack* st);
bool STEmpty(Stack* st);
stack.c
#include"Stack.h"Stack* STCreate()
{Stack* st = (Stack*)malloc(sizeof(Stack));if (NULL == st){perror("malloc failed");exit(-1);}st->a = NULL;st->capacity = st->top = 0;return st;
}void STDestroy(Stack* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = st->top = 0;free(st);
}void STPush(Stack* st, STDataType x)
{assert(st);if (st->capacity == st->top){int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* temp = (STDataType*)realloc(st->a, sizeof(STDataType) * newcapacity);if (NULL == temp){perror("realloc failed");exit(-1);}st->a = temp;st->capacity = newcapacity;}st->a[st->top] = x;++st->top;
}STDataType STPop(Stack* st)
{assert(st);assert(st->top);STDataType ret = STTop(st);--st->top;return ret;
}STDataType STTop(Stack* st)
{assert(st);assert(st->top);return st->a[st->top - 1];
}int STSize(Stack* st)
{return st->top;
}bool STEmpty(Stack* st)
{assert(st);return st->top == 0;
}
test.c
#include <stdio.h>
#include"MyQueue.h"static void MyQueuePrint(MyQueue* q)
{int temp = 0;assert(q);printf("InStack:");temp = STSize(q->ist);for (int i = 0; i < temp; ++i){printf("%d->", q->ist->a[i]);}printf("\n");printf("OutStack:");temp = STSize(q->ost);for (int i = 0; i < temp; ++i){printf("%d->", q->ost->a[i]);}printf("\n");
}void testmyqueue()
{MyQueue* q = myQueueCreate();MyQueuePrint(q);myQueuePush(q, 1);myQueuePush(q, 2);MyQueuePrint(q);myQueuePop(q);MyQueuePrint(q);myQueuePush(q, 3);MyQueuePrint(q);printf("delval = %d\n", myQueuePeek(q));myQueueFree(q);
}int main()
{testmyqueue();return 0;
}