C语言/数据结构——每日一题（用栈实现队列）

一.前言

前面我们已经学习了栈的基本实现：https://mp.csdn.net/mp_blog/creation/editor/138923750

和队列的基本实现：htt
ps://blog.csdn.net/yiqingaa/article/details/139033067?spm=1001.2014.3001.5501

现在我们尝试一下，使用栈来实现队列：https://leetcode.cn/problems/implement-queue-using-stacks/submissions/533582565/

二 .正文

1.1题目描述

1.2题目分析

1.21题目想要我们做什么

本题想要我们使用两个栈，来模拟实现队列对数据的队尾插入、队头删除、判断队列是否为空、以及返回队头元素操作这些函数功能的实现。

1.22解题思路

这道题我们可以将这两个栈分别命名为pushst和popst。

pushst专门用来存储数据。

popst专门用来删除数据。

这样让两个栈都有其独特职责，就可以避免每次在删除数据和存储数据的时候都要进行一个栈里面的数据都要导入到另一个栈里面。

1.3代码实现

值得注意的是，当我们使用C语言写这道题的时候， 我们必须自己创建我们自己的栈，力扣官网不会提供。但是当我们使用C++后，力扣官网就会提供栈，以及栈实现数据增删查改函数功能的接口。因为在C语言环境下它没给，因此这些东西我们只能自己实现。

使用栈实现对数据的增删查改，我们已经写过了。有兴趣的小伙伴可以查看一下：

https://blog.csdn.net/yiqingaa/article/details/138923750?spm=1001.2014.3001.5502

typedef int STDataType;
struct Stack
{
STDataType* a;
int top;
int capacity;
};
typedef struct Stack ST;
void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁

void STPush(ST*PS,STDataType x);//入栈
void STPop(ST* ps);//出栈

STDataType STTop(ST* ps);//取栈顶的数据

bool STEmpty(ST*ps);//判空

int STSize(ST* PS);//获取数据个数

void STInit(ST *ps)//栈的初始化
{
assert(ps);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void STDestroy(ST* ps)//栈的销毁
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)//入栈
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 6 : ps->capacity*2;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
return;
}                
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)//删除栈顶元素
{
assert(ps);
assert(ps->a);
ps->top--;
}
STDataType STTop(ST* ps)//取出栈顶元素
{
assert(ps);
assert(ps->top >= 0);
return ps->a[ps->top-1];
}
bool STEmpty(ST* ps)//判断栈内元素是否为空
{
assert(ps);
if (ps->top == 0)
return true;
return false;
}
int STSize(ST* ps)//获取数据个数
{
assert(ps);
return ps->top ;
}


typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&(obj->pushst));
    STInit(&(obj->popst));
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
   
        STPush(&(obj->pushst),x);
}

int myQueuePeek(MyQueue* obj);

int myQueuePop(MyQueue* obj) {
int ret=myQueuePeek(obj);
STPop(&(obj->popst));
return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&(obj->popst))==true)
    {
        while(STEmpty(&(obj->pushst))!=true)
        {
int ret=STTop(&(obj->pushst));
STPush(&(obj->popst),ret);
STPop(&(obj->pushst));
        }
    }
    return STTop(&(obj->popst));
}

bool myQueueEmpty(MyQueue* obj) {
    if(STEmpty(&(obj->pushst))&&STEmpty(&(obj->popst))==true)
    return true;
    return false;
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&(obj->pushst));
    STDestroy(&(obj->popst));
    free(obj);
}

/**
 * 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);
*/

三.结言

本题到这就已经分享结束了，有兴趣的小伙伴，能不能给个三连。 

我们下期再见，拜拜~

原文地址：https://blog.csdn.net/yiqingaa/article/details/139093593

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！