备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】栈实现队列 & 队列实现栈

2023-01-13 47
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】栈实现队列 & 队列实现栈

🌍第1️⃣题：用栈实现队列


🏷️力扣地址：🌈232. 用栈实现队列


请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：


void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空，返回 true ；否则，返回 false

示例1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

输入：

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：

[null, null, null, 1, 1, false]


解释：

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false


💫关键思路：


为了满足队列的 FIFO（先进先出） 的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。

popst出栈 ——pushst入栈

1️⃣pop接口


出数据时，把pushst中的数据倒腾到popst中，实现了先进先出。

此后，若要出数据，直接在popst出栈即可。若出空了，就再如上倒腾一下，那此时就可以按照栈的特性去pop，达到队列的LIFO的目的

🌠动图解析：👇🏻


92ba0822ed0b46e1ae72df8a17d3a45b.png


2️⃣peek接口


判断出数据的栈popst是否为空，若为空，则要把pushst栈的数据倒腾过来，否则可以直接出栈顶数据

🌠动图解析：👇🏻


92ba0822ed0b46e1ae72df8a17d3a45b.png


3️⃣push接口


就只管往pushst中入就行，保持了数据的顺序。

🌠动图解析：👇🏻


92ba0822ed0b46e1ae72df8a17d3a45b.png


4️⃣empty接口


判断两个栈是否都为NULL，是则返回true，否则返回false

💡代码实现：


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))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    int front = StackTop(&obj->popst);
    StackPop(&obj->popst);
    return front;
}
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popst) && StackEmpty(&obj->pushst);
}
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popst);
    StackDestroy(&obj->pushst);
    free(obj);
}


🌍第2️⃣题：用队列实现栈


🏷️力扣地址：🌈225. 用队列实现栈


请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。


实现 MyStack 类：


void push(int x) 将元素 x 压入栈顶

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

示例1


输入：

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]


解释：

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False


🌍解题关键：


用两个栈实现队列，就是用队列来满足栈入数据 & 出数据的性质，即实现后进先出。

💫关键思路：


92ba0822ed0b46e1ae72df8a17d3a45b.png


那到底是如何实现的呢？


为了保持栈的后进先出原则，但队列却是遵循先进先出，那该咋办呢？

此时我们利用两个队列，分别设置为空队列、非空队列（假定法：先假定为空队列，若是非空再反转）

1️⃣pop接口


把非空队列的前(n-1)个数据依次转移（倒腾）到另一个队列里，最后一个数据pop掉。即可实现后进先出。

🌠动图解析：👇🏻


92ba0822ed0b46e1ae72df8a17d3a45b.png


2️⃣push接口


哪一个队列非空，就入哪一个队。保持数据顺序

🌠动图解析：👇🏻


92ba0822ed0b46e1ae72df8a17d3a45b.png


3️⃣top接口


判断两个队列中哪个是非空队列，并返回其队尾的结点即可

4️⃣empty接口


判断两个队列是否都为空，是则返回true，否则false

💡代码实现：


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)) //如果q1不为空，则向q1压栈
    {
        QueuePush(&obj->q1,x);
    }
    else//q1为空，q2有可能为空，也可能不空
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj)
{
    //假设q1为空，q2非空
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top = QueueFront(nonemptyQ);//取出栈顶，记得pop掉
    QueuePop(nonemptyQ);
    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);//先释放q1、q2，最后再是自定义的栈
    QueueDestroy(&obj->q2);
    free(obj);
}


原码直出

由于上面都是要借助现成的栈或者队列才能实现的，（后面学了c++就不会这么麻烦了），前面都只写了主体逻辑，现在把完整的贴过来嗷，有需要自取


栈实现队列


#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
静态
//#define N 10
//typedef int STDataType;
//typedef struct Stack
//{
//  STDataType a[N];
//  int top;
//}ST;
//动态
typedef int STDataType;
typedef struct Stack
{
  STDataType *a;
  int top;//栈顶
  int capacity;//容量
}ST;
// 初始化栈 
void StackInit(ST* ps);
// 入栈 
void StackPush(ST* ps, STDataType data);
// 出栈 
void StackPop(ST* ps);
// 获取栈顶元素 
STDataType StackTop(ST* ps);
// 获取栈中有效元素个数 
int StackSize(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(ST* ps);
// 销毁栈 
void StackDestroy(ST* ps);
// 初始化栈 
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
// 入栈 
void StackPush(ST* ps, STDataType data)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
  //满了就扩容
  int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
  if (tmp == NULL)
  {
    printf("realloc fail\n");
    exit(-1);
  }
  ps->a = tmp;
  ps->capacity = newCapacity;
  }
  ps->a[ps->top] = data;
  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];
}
// 获取栈中有效元素个数 
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;//top就是size个数，看下标
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(ST* ps)
{
  return ps->top == 0;
}
// 销毁栈 
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
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))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    int front = StackTop(&obj->popst);
    StackPop(&obj->popst);
    return front;
}
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);1111111111111111111111111111111111111
}
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popst) && StackEmpty(&obj->pushst);
}
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popst);
    StackDestroy(&obj->pushst);
    free(obj);
}


队列实现栈


#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
// 链式结构：表示队列
typedef int QDataType;
typedef struct SListNode
{
  QDataType data;
  struct SListNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
// 初始化队列
void QueueInit(Queue* q)
{
  assert(q);
  q->head = q->tail = NULL;//不带哨兵位，哨兵位意义不大
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  printf("malloc failed\n");
  exit(-1);
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->tail == NULL)
  {
  q->head = q->tail = newnode;
  }
  else
  {
  q->tail->next = newnode;
  q->tail = newnode;
  }
}
// 队头出队列
void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  //1.一个节点
  //2.多个节点
  if (q->head->next == NULL)
  {
  free(q->head);
  q->head = q->tail = NULL;//避免野指针
  }
  else
  {
  QNode* next = q->head->next;
  free(q->head);
  q->head = next;
  }
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  return q->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
  assert(q);
  QNode* cur = q->head;
  int Size = 0;
  while (cur)
  {
  Size++;
  cur = cur->next;
  }
  return Size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->head;
  while (cur)
  {
  QNode* next = cur->next;
  free(cur);
  cur = next;
  }
  q->head = q->tail = NULL;
}
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)) //如果q1不为空，则向q1压栈
    {
        QueuePush(&obj->q1,x);
    }
    else//q1为空，q2有可能为空，也可能不空
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj)
{
    //假设q1为空，q2非空
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top = QueueFront(nonemptyQ);//取出栈顶，记得pop掉
    QueuePop(nonemptyQ);
    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);//先释放q1、q2，最后再是自定义的栈
    QueueDestroy(&obj->q2);
    free(obj);
}


📢写在最后

能看到这里的都是棒棒哒🙌！

想必《栈和队列》也算是数据结构中比较难🔥的部分了，如果认真看完以上部分，肯定有所收获。

接下来我还会继续写关于📚《循环队列》等…

💯如有错误可以尽管指出💯

🥇想学吗？我教你啊🥇

🎉🎉觉得博主写的还不错的可以一键三连撒🎉🎉


文章标签：
云解析DNS
C++
存储
关键词：
数据结构队列
数据结构栈队列
数据结构栈
张小姐的猫
目录
相关文章
不摸鱼的程序员
|
6天前
|
存储 Java 容器
深入浅出 栈和队列（附加循环队列、双端队列）
深入浅出 栈和队列（附加循环队列、双端队列）
不摸鱼的程序员
26 4
游客6z2krsj5iqmue
|
3天前
|
算法 编译器 Python
栈
栈
游客6z2krsj5iqmue
17 2
不摸鱼的程序员
|
5天前
栈的最后表演：逆波兰表达式求值
栈的最后表演：逆波兰表达式求值
不摸鱼的程序员
11 1
游客jajxe3foty4uc
|
5天前
栈与队列
栈与队列
游客jajxe3foty4uc
12 0
Sessy
|
7天前
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列.
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列
Sessy
18 3
兰雪簪轩
|
7天前
|
存储 测试技术 计算机视觉
栈和队列经典练习题
栈和队列经典练习题
兰雪簪轩
17 3
兰雪簪轩
|
7天前
数据结构之——队列详解
数据结构之——队列详解
兰雪簪轩
13 0
兰雪簪轩
|
7天前
|
C++
数据结构深入理解--栈
数据结构深入理解--栈
兰雪簪轩
17 0
过。
|
7天前
|
Java 索引
Java数据结构——栈
Java数据结构——栈
过。
19 1
TU^
|
11天前
|
存储 调度 索引
数据结构~~栈和队列
在计算机科学中，数据结构是构建高效程序的基础。栈和队列是两种重要且常用的线性数据结构，它们在解决各种问题中发挥着关键作用。
TU^
24 1