(动画详解)LeetCode232.用栈实现队列

devtools/2024/9/23 6:21:54/

💖💖💖欢迎来到我的博客，我是anmory💖💖💖
又和大家见面了
欢迎来到动画详解LeetCode算法系列
用通俗易懂的动画让算法题不再神秘
先来自我推荐一波
个人网站欢迎访问~~以及捐款~~
推荐阅读
如何低成本搭建个人网站
专栏:动画详解leetcode 算法题
C语言知识

玉桂狗yay

题目描述

解题思路

这道题我们引入两个栈，一个用来入栈，一个用来出栈
这样，出栈的栈顶元素就是队列的队头元素了

动画详解

用<a class= 栈实现队列" />

代码实现

这里由于使用的是C语言，需要自己写栈
所以代码量会比较多，大家不要被吓到了哈

typedef int DataType;// 定义一个栈，包含数据，栈顶元素下标，栈的大小
struct Stack
{DataType* data;int top;int capacity;
};typedef struct Stack Stack;// 栈的初始化
void StackInit(Stack* st)
{assert(st);st->data = NULL;st->capacity = 0;// top指向栈顶元素的下一个st->top = 0;
}// 入栈
void StackPush(Stack* st, DataType x)
{assert(st);if (st->top == st->capacity){int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;DataType* new = (DataType*)realloc(st->data,newcapacity*sizeof(DataType));// 如果开辟失败if (new == NULL){perror("malloc fail");return;}// 如果开辟成功st->data = new;st->capacity = newcapacity;}st->data[st->top] = x;st->top++;
}// 出栈
void StackPop(Stack* st)
{assert(st);st->top--;
}// 栈的判空
bool StackIsEmpty(Stack* st)
{assert(st);if (st->top == 0){return true;}else{return false;}
}// 返回栈顶元素
DataType StackTop(Stack* st)
{assert(st);assert(st->top > 0);return st->data[st->top - 1];
}// 栈的大小
int StackSize(Stack* st)
{assert(st);return st->top;
}// 栈的销毁
void StackDestroy(Stack* st)
{assert(st);free(st->data);st->data = NULL;st->top = st->capacity = 0;
}typedef struct 
{Stack pushst;Stack popst;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* new = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&(new->pushst));StackInit(&(new->popst));return new;}void myQueuePush(MyQueue* obj, int x) 
{StackPush(&(obj->pushst),x);}int myQueuePeek(MyQueue* obj);int myQueuePop(MyQueue* obj) 
{int front = myQueuePeek(obj);StackPop(&(obj->popst));return front;
}int myQueuePeek(MyQueue* obj) 
{if(StackIsEmpty(&(obj->popst))){// 导入数据while(!StackIsEmpty(&(obj->pushst))){int top = StackTop(&(obj->pushst));StackPush(&(obj->popst),top);StackPop(&(obj->pushst));}}return StackTop(&(obj->popst));}bool myQueueEmpty(MyQueue* obj) 
{return StackIsEmpty(&(obj->pushst)) && StackIsEmpty(&(obj->popst));}void myQueueFree(MyQueue* obj) 
{StackDestroy(&(obj->pushst));StackDestroy(&(obj->popst));free(obj);obj = NULL;}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/