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

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

2023-01-13 65
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
公共DNS（含HTTPDNS解析），每月1000万次HTTP解析
全局流量管理 GTM，标准版 1个月
云解析 DNS，旗舰版 1个月
简介： 【数据结构】栈实现队列 & 队列实现栈

🌍第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++
存储
关键词：
数据结构队列
数据结构栈队列
数据结构栈
张小姐的猫
目录
相关文章
ephemerals__
|
2月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
241 9
那年春天
|
2月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
40 1
龙大吉
|
2月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
71 5
德国都芳最好
|
2月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
90 21
html的七十二变
|
2月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
37 2
dufadayang
|
2月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
54 4
肾透侧视攻城狮
|
2月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
31 1
XIAZHI
|
2月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
53 0
星霜旅人
|
3月前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
25 1
java冯坚持
|
3月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
54 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器

热门文章

最新文章

  • 1
    Python编程数据结构的深入理解
  • 2
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
  • 3
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 4
    Python 中的数据结构与其他编程语言数据结构的区别
  • 5
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
  • 6
    Python 中的数据结构和算法优化策略
  • 7
    Python 中数据结构和算法的关系
  • 8
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
  • 9
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 10
    Pandas数据结构：Series与DataFrame
  • 1
    【Python进阶（七）】——Series数据结构
    189
  • 2
    Redis数据结构精讲：选择与应用实战指南
    1335
  • 3
    深入浅出数据结构之布隆过滤器
    75
  • 4
    数据结构/C++：位图 & 布隆过滤器
    49
  • 5
    数据结构/C++：哈希表
    86
  • 6
    数据结构/C++：红黑树
    47
  • 7
    数据结构/C++：AVL树
    49
  • 8
    栈的基本应用
    71
  • 9
    栈与队列理解
    50
  • 10
    数据结构/C++：二叉搜索树
    55

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月