当前位置：首页 > news >正文

【LeetCode刷题】232.用栈实现队列

news 来源：原创 2024/9/29 3:32:51

题目链接

图解思路

整体结构

实现过程

入队列

出队列

实现代码

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;
}