力扣刷题之栈和队列相互实现（力扣225 力扣232）

dl 文档中心 2022-05-31 23:28:49 52

个人主页：欢迎大家光临——>沙漠下的胡杨

各位大帅哥，大漂亮

如果觉得文章对自己有帮助

可以一键三连支持博主

你的每一分关心都是我坚持的动力

☄：本期重点：力扣225 力扣232

希望大家每天都心情愉悦的学习工作。

用队列实现栈（力扣225）：

这是题目，就是在不考虑效率的情况下，使用队列模拟实现栈的性质，我们使用的语言依然是纯C ，所以我们在这之前还是要先写出一个队列出来的，我就借用之前文章的栈和队列来实现了。（队列实现）（栈的实现）

我们分析先下如何实现呢？

队列是先进先出，我们要实现先进后出，我们可以用两个队列，一个队列用来存储数据，一个队列用来倒数据，先把数据放入一个队列中，然后再把除了最后一个数据的其他数据放入另一个队列中，使原本队列只剩一个数据，然后删除，循环倒数据即可实现栈的功能。

代码实现：

下面我们来实现函数接口吧：

插入：
typedef struct {    Queue q1;    Queue q2;} MyStack;//创建结构
创建时我们可以直接进行创建两个队列，方便倒数据。

初始化：
MyStack* myStackCreate() //初始化，并返回一个结点{    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));    QueueInit(&obj->q1);    QueueInit(&obj->q2);    return obj;}
我们必须要 malloc 一个所谓的栈的空间，因为最后要返回这个结构的指针，这个函数要销毁，如果返回栈空间地址，地址值无效，指针就无效了。

然后在一个个初始化这个 q1和q2队列就好了。

入栈：
void myStackPush(MyStack* obj, int x)//入栈{    if(!QueueEmpty(&obj->q1))    { QueuePush(&obj->q1,x);    }    else    { QueuePush(&obj->q2,x);    }}
入栈时比较简单，我们就向队列中有元素的中存放就可以啦。如果都为空，那就无所谓。

删除栈顶元素并返回值：
int myStackPop(MyStack* obj) //删除栈顶数据，并返回{    Queue* Empty = &obj->q1;    Queue* NoEmpty = &obj->q2;    if(!QueueEmpty(&obj->q1))    { Empty = &obj->q2; NoEmpty = &obj->q1;    }    while(QueueSize(NoEmpty)>1)    { QueuePush(Empty,QueueFront(NoEmpty)); QueuePop(NoEmpty);    }    int top = QueueFront(NoEmpty);    QueuePop(NoEmpty);    return top;}
我们首先使用假设法，得到为空的队列和不为空的队列，我们把这个不为空的队列向为空的队列中插入，然后pop掉不为空队列的首元素，一直到这个队列元素数量为 1 时停止，最后我们把原先不为空的队列的元素的唯一一个元素取出来，然后在pop掉，这样原来不为空的队列就为空了，其他的元素也通过插入放入了原来不为空的队列中了。

返回栈顶元素：
int myStackTop(MyStack* obj)//返回栈顶元素 {    if(!QueueEmpty(&obj->q1))    { return QueueBack(&obj->q1);    }    else    { return QueueBack(&obj->q2);    }}
我们就判断那个队列不为空，栈顶的元素就是不为空队列的最后一个元素。

判断栈是否为空：
bool myStackEmpty(MyStack* obj) //判断栈是否为空{    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}
只有两个队列都为空时，栈才是空的，所以用并（&&）来判断。

栈的销毁：
void myStackFree(MyStack* obj) //销毁栈{    QueueDestroy(&obj->q1);    QueueDestroy(&obj->q2);    free(obj);}
因为我们创建时就是创建的 obj 的空间，在逐步创建的q1 和 q2 的空间，所以我们在释放时，我们也该先释放q1 和 q2的空间，如果先释放 obj ，那么就找不到q1 q2了。

整体代码（包含队列的创建）：

typedef int QDataType; typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode; typedef struct Queue{QNode* head;QNode* tail;}Queue; void QueueInit(Queue* qp);//初始化 void QueueDestroy(Queue* qp);//队列的销毁 void QueuePush(Queue* qp,QDataType x);//队列插入 void QueuePop(Queue* qp);//队列删除 QDataType QueueFront(Queue* qp);//取出队列首元素 QDataType QueueBack(Queue* qp);//取出队列末尾元素 bool QueueEmpty(Queue* qp);//判断队列是否为空 int QueueSize(Queue* qp);//返回队列的元素个数 void QueueInit(Queue* qp)//初始化{assert(qp); qp->head = qp->tail = NULL;} void QueueDestroy(Queue* qp)//队列的销毁{assert(qp);QNode* cur = qp->head; while (cur){QNode* next = cur->next;free(cur);cur = next;} qp->head = qp->tail = NULL; } void QueuePush(Queue* qp,QDataType x)//队列插入{assert(qp);QNode *newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail\n");exit(-1);}newnode->next = NULL;newnode->data = x;if (qp->head == NULL){qp->head = qp->tail = newnode;}else{qp->tail->next = newnode;qp->tail = newnode;} } void QueuePop(Queue* qp)//队列删除{assert(qp);assert(!QueueEmpty(qp)); if (qp->head->next == NULL){qp->head = qp->tail = NULL;}else{QNode* next = qp->head->next;free(qp->head);qp->head = next;}} QDataType QueueFront(Queue* qp)//取出队列首元素{assert(qp);assert(!QueueEmpty(qp)); return qp->head->data;} QDataType QueueBack(Queue* qp)//取出队列末尾元素{assert(qp);assert(!QueueEmpty(qp)); return qp->tail->data;} bool QueueEmpty(Queue* qp)//判断队列是否为空{assert(qp); return qp->head == NULL;} int QueueSize(Queue* qp)//返回队列的元素{assert(qp);int size = 0;QNode* cur = qp->head; while (cur){++size;cur = cur->next;} return size;}typedef struct {    Queue q1;    Queue q2;} MyStack;//创建结构MyStack* myStackCreate() //初始化，并返回一个结点{    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));    QueueInit(&obj->q1);    QueueInit(&obj->q2);    return obj;}void myStackPush(MyStack* obj, int x)//入栈{    if(!QueueEmpty(&obj->q1))    { QueuePush(&obj->q1,x);    }    else    { QueuePush(&obj->q2,x);    }}int myStackPop(MyStack* obj) //删除栈顶数据，并返回{    Queue* Empty = &obj->q1;    Queue* NoEmpty = &obj->q2;    if(!QueueEmpty(&obj->q1))    { Empty = &obj->q2; NoEmpty = &obj->q1;    }    while(QueueSize(NoEmpty)>1)    { QueuePush(Empty,QueueFront(NoEmpty)); QueuePop(NoEmpty);    }    int top = QueueFront(NoEmpty);    QueuePop(NoEmpty);    return top;}int myStackTop(MyStack* obj)//返回栈顶元素 {    if(!QueueEmpty(&obj->q1))    { return QueueBack(&obj->q1);    }    else    { return QueueBack(&obj->q2);    }}bool myStackEmpty(MyStack* obj) //判断栈是否为空{    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) //销毁栈{    QueueDestroy(&obj->q1);    QueueDestroy(&obj->q2);    free(obj);}

下面我们看下它的兄弟题目

用栈实现队列（力扣 232）：

我们是使用栈来模拟实现队列相关的操作，和上面的类似，我们也要有两个栈，但是我们不需要频繁的倒数据，我们创建一个Push栈，一个Pop栈，Push栈就插入数据，Pop栈就是出数据，如果Pop栈为空，那么我们就先Push栈中要数据，就是把Push栈的数据倒过来就好2了，其他和上面题类似。

入数据：

该出数据时：

在插入数据，删除数据

就是Push栈一直入数据，Pop一直出数据，如果Pop为空，那么就把Push栈的数据倒到Pop栈中，这样循环实现。

代码实现：

还是要先写一个栈，然后在进行操作。

队列的创建，初始化和销毁
typedef struct //初始化{    ST Pushst;    ST Popst;} MyQueue;MyQueue* myQueueCreate() //初始化{    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));    StackInit(&obj->Pushst);    StackInit(&obj->Popst);    return obj;}void myQueueFree(MyQueue* obj)//销毁{    StackDestroy(&obj->Pushst);    StackDestroy(&obj->Popst);    free(obj);}
这些都和上面的类似不在赘述。

判断队列是否为空：
bool myQueueEmpty(MyQueue* obj) //判空{    return StackEmpty(&obj->Pushst) && StackEmpty(&obj->Popst);}
也是和上面类似，只有两个栈为空，队列才是空的。

队列的插入：
void myQueuePush(MyQueue* obj, int x)//插入{    StackPush(&obj->Pushst,x);}
队列的插入，只要插入Push栈就可以啦。

从队列的开头移除并返回元素：
int myQueuePop(MyQueue* obj)//从队列的开头移除并返回元素{    if(StackEmpty(&obj->Popst))    { while(!StackEmpty(&obj->Pushst)) {     StackPush(&obj->Popst,StackTop(&obj->Pushst));     StackPop(&obj->Pushst); }    }    int top = StackTop(&obj->Popst);    StackPop(&obj->Popst);    return top;}
这个只需要判断Pop栈是否为空，如果为空就从Push栈倒数据，不为空就直接保存Pop栈的头元素，然后Pop掉，接着返回就好了。

返回队列开头元素：
int myQueuePeek(MyQueue* obj) {    if(StackEmpty(&obj->Popst))    { while(!StackEmpty(&obj->Pushst)) {     StackPush(&obj->Popst,StackTop(&obj->Pushst));     StackPop(&obj->Pushst); }    }  return StackTop(&obj->Popst);}
同上，比起上面的是我们不需要Pop栈顶元素，所以可以直接返回。

整体代码：

typedef int STDataType; typedef struct Stack{STDataType* a;int top;int capacity;}ST; void StackInit(ST* ps);//初始化 void StackDestroy(ST* ps);//销毁 void StackPush(ST* ps, STDataType x);//插入（入栈），栈的插入是尾插。 void StackPop(ST* ps);//删除（出栈），从尾部删除。 STDataType StackTop(ST* ps);//读出栈顶 bool StackEmpty(ST* ps);//判断栈是否为空 int StackSize(ST* ps);//栈中的元素个数  void StackInit(ST* ps)//初始化{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;} void StackDestroy(ST* ps)//销毁{assert(ps); free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;} void StackPush(ST* ps, STDataType x)//插入（入栈），栈的插入是尾插。{assert(ps); if (ps->capacity == ps->top){int NewCapaticy = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*NewCapaticy);if (tmp == NULL){perror("realoc fail\n");exit(-1);}ps->a = tmp;ps->capacity = NewCapaticy;}ps->a[ps->top] = x;ps->top++;} void StackPop(ST* ps)//删除（出栈），从尾部删除。{assert(ps);assert(!StackEmpty(ps)); ps->top--;} STDataType StackTop(ST* ps)//读出栈顶{assert(ps);assert(!StackEmpty(ps)); return ps->a[ps->top-1];} bool StackEmpty(ST* ps)//判断栈是否为空{assert(ps); return ps->top == 0;} int StackSize(ST* ps)//栈中的元素个数{assert(ps); return ps->top;}typedef struct //初始化{    ST Pushst;    ST Popst;} MyQueue;MyQueue* myQueueCreate() {    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));    StackInit(&obj->Pushst);    StackInit(&obj->Popst);    return obj;}void myQueuePush(MyQueue* obj, int x){    StackPush(&obj->Pushst,x);}int myQueuePop(MyQueue* obj) {    if(StackEmpty(&obj->Popst))    { while(!StackEmpty(&obj->Pushst)) {     StackPush(&obj->Popst,StackTop(&obj->Pushst));     StackPop(&obj->Pushst); }    }    int top = StackTop(&obj->Popst);    StackPop(&obj->Popst);    return top;}int myQueuePeek(MyQueue* obj) {    if(StackEmpty(&obj->Popst))    { while(!StackEmpty(&obj->Pushst)) {     StackPush(&obj->Popst,StackTop(&obj->Pushst));     StackPop(&obj->Pushst); }    }  return StackTop(&obj->Popst);}bool myQueueEmpty(MyQueue* obj) {    return StackEmpty(&obj->Pushst) && StackEmpty(&obj->Popst);}void myQueueFree(MyQueue* obj)//销毁{    StackDestroy(&obj->Pushst);    StackDestroy(&obj->Popst);    free(obj);}

本期到这里结束啦，明天再见！

步森服饰商城

力扣刷题之栈和队列相互实现（力扣225 力扣232）

☄：本期重点：力扣225 力扣232

目录

用队列实现栈（力扣225）：

代码实现：

插入：

初始化：

入栈：

删除栈顶元素并返回值：

返回栈顶元素：

判断栈是否为空：

栈的销毁：

整体代码（包含队列的创建）：

用栈实现队列（力扣 232）：

代码实现：

队列的创建，初始化和销毁

判断队列是否为空：

队列的插入：

从队列的开头移除并返回元素：

返回队列开头元素：

整体代码：

标签

力扣刷题之 栈和队列 相互实现（力扣225 力扣232）

☄： 本期重点：力扣225 力扣232

目录

用队列实现栈（力扣225）：

代码实现：

插入：

初始化：

入栈：

删除栈顶元素并返回值：

返回栈顶元素：

判断栈是否为空：

栈的销毁：

整体代码（包含队列的创建）：

用栈实现队列（力扣 232）：

代码实现：

队列的创建，初始化和销毁

判断队列是否为空：

队列的插入：

从队列的开头移除并返回元素：

返回队列开头元素：

整体代码：

标签

力扣刷题之栈和队列相互实现（力扣225 力扣232）

☄：本期重点：力扣225 力扣232