AI 助理
文档备案控制台
开发者社区 人工智能 文章 正文

【数据结构与算法】用队列实现栈

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

😎前言


😼前面我们相继实现了 栈 和 队列 ，是不是愁没有练手的地方呢？别担心，本章带大家用队列来实现一个栈！

😽我们都知道，栈和队列可以看作为兄弟，一个后进先出(LIFO)，一个先进先出(FIFO)，他们虽有不同的性质，但总的来说还是不分家的，因为，我们既可以用队列实现栈，也可以用栈实现队列，而本章就先来带大家来了解如何使用队列来实现栈。


如何用队列实现栈？


前面废话这么多，那我们该如何用队列实现栈呢？一个队列当然不行，所以这里需要两个队列来实现。


用两个队列，而每一个队列都是数据先进先出，我们仔细思考栈的后进先出这一性质，如何来操作这两个队列才能达到这样的一个性质？


我们可以这样操作，一开始，两个队列都为空，所以我们随便在一个队列里进数据（就是入栈），当我们要出数据时，根据栈的性质，最后进的数据要出去，也就是在进数据的那个队列里最后进的数据要出去，但由于队列的性质只能先进的先出， 所以这里我们需要用到另外那个空的队列：我们将已有数据的队列依次出数据，并将出的数据入到那个空的队列中，当出数据的队列中只有一个数据时停止出数据，而此时最后剩下的那个数据，就是依据栈的性质所要删除的那个数据，这时，直接将那个数据出掉并不在入入另外一个队列即可。续：我们每次出栈都需要前面的操作，这是最难理解也是最核心的一个步骤。


eda0e89f0c494c79b0d461388fa81f5b.gif


当然了，入栈操作又分两种情况：第一种就是前面所说开始两个队列都为空的情况；第二种就是当一个队列不为空时，我们只需要正常的往这个有数据的队列入栈即可。


此外，用队列实现一个栈，还需要有判空，取栈顶元素，栈的销毁这些功能，不过这些都是小问题，我们可以巧用轮子 （轮子就是我们提前已经实现好的队列的一系列功能） 来灵活解决这些问题。


用队列实现栈


  • 这里我们直接以题目的方式来实现，题目链接：->传送门<- 。


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


3cc4b7a8009a4bf0bf58d6cc345860c9.png

637f33be4334417091a58d3f2fe9cced.png

939b89aecdb646b4a3383d6aa7a75f23.png


该题提供的需要我们实现的接口：

typedef struct {
} MyStack;
MyStack* myStackCreate() {
}
void myStackPush(MyStack* obj, int x) {
}
int myStackPop(MyStack* obj) {
}
int myStackTop(MyStack* obj) {
}
bool myStackEmpty(MyStack* obj) {
}
void myStackFree(MyStack* obj) {
}


  • 由于这里我们用C语言实现，因此需要 “造轮子”，也就是将之前实现过的队列拷贝过去。

接下来，就是对栈的一系列功能接口的实现了：

1.

  • 首先当然是造轮子，有了轮子，我们对队列的一系列操作，只需要调用我们已经实现好的函数接口即可。
  • 我们将之前写的队列直接拷贝过来，拷贝的代码如下：
// 队列的数据的类型
typedef int QDataType;
// 节点结构 
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
// 队列结构
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Que;
// 初始化队列
void QInit(Que* pq);
// 销毁队列
void QDestroy(Que* pq);
// 数据入队列
void QPush(Que* pq, QDataType x);
// 数据出队列
void QPop(Que* pq);
// 获取队列中有效元素个数
int QSize(Que* pq);
// 队列判空
bool QEmpty(Que* pq);
// 取队头数据
QDataType QFront(Que* pq);
// 取队尾数据
QDataType QBack(Que* pq);
// 初始化队列
void QInit(Que* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
// 队列销毁
void QDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
// 数据入队列
void QPush(Que* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->size == 0) pq->head = pq->tail = newnode;
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
// 数据出队列 
void QPop(Que* pq)
{
  assert(pq && !QEmpty(pq));
  if (pq->head == pq->tail)
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }
  else
  {
    QNode* tmp = pq->head->next;
    free(pq->head);
    pq->head = tmp;
  }
  pq->size--;
}
// 获取队列中有效元素个数
int QSize(Que* pq)
{
  assert(pq);
  return pq->size;
}
// 队列判空
bool QEmpty(Que* pq)
{
  assert(pq);
  return pq->size == 0;
}
// 取队头数据
QDataType QFront(Que* pq)
{
  assert(pq && !QEmpty(pq));
  return pq->head->data;
}
// 取队尾数据
QDataType QBack(Que* pq)
{
  assert(pq && !QEmpty(pq));
  return pq->tail->data;
}


  • 有了轮子之后，就是对栈的结构体的创建了，由于栈是由两个队列实现的，因此栈的结构体的成员也是两个队列：

相关代码实现：

// 匿名结构体
typedef struct {
    Que q1;
    Que q2;
} MyStack;   // 重命名为MyStack


  • 然后是创建一个栈，就是开辟一个栈的空间，其间包含对栈里的两个队列的初始化操作。

相关代码实现：

MyStack* myStackCreate() {
  // 开辟一个栈空间
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
  assert(obj);
  // 对栈的两个成员队列调用队列的初始化函数接口初始化
  QInit(&obj->q1);
  QInit(&obj->q2);
  // 最后返回指向栈空间地址的指针
  return obj;
}


  • 接着就是对入栈操作的实现。
  • 前面已经说过，如果开始两个队列都为空，随便入一个就好，后面往有数据的那个队列入即可。

相关代码实现：

void myStackPush(MyStack* obj, int x) {
  // 开始都为空，随便入，后面往不空的入
  if (!QEmpty(&obj->q1)) QPush(&obj->q1, x);
  else QPush(&obj->q2, x);
}


再接着就是最复杂的出栈操作。


由前面的介绍，我们已经知道了思路，而现在最主要的，就是如何判断那个队列为空。


我们首先假设q1为空q2不为空，然后判断一下q1是不是真的为空，如果是，什么事没有，如果不是，就换一下，变成q2为空，q1不为空，思路就是这样，具体还需看代码。


知道谁为空谁不为空后，接下来就是前面所说的思路的操作了。


相关代码实现：

int myStackPop(MyStack* obj) {
  assert(!myStackEmpty(obj));
  // 假定q1为空，q2不为空
  Que* emptyQ = &obj->q1;
  Que* nonemptyQ = &obj->q2;
  // 判断q1是否真的为空，不为空则进去if，交换“身份”
  if (!QEmpty(emptyQ))
  {
    emptyQ = &obj->q2;
    nonemptyQ = &obj->q1;
  }
  // 然后就是前面所说的操作
  // 不为空的依次出队列，并将出队列的数据入到空的队列中
  // 直到出的还剩一个数据停止
  while (QSize(nonemptyQ) > 1)
  {
    int front = QFront(nonemptyQ);
    QPush(emptyQ, front);
    QPop(nonemptyQ);
  }
  // 最后将最后一个数据存起来
  int front = QFront(nonemptyQ);
  // 删除这个数据
  QPop(nonemptyQ);
  // 在返回存的这个数据
  return front;
}


  • 当然还有获取栈顶数据的功能。
  • 我们先找到不为空的那个队列，然后调用其获取队尾数据的函数，最后将这个函数返回的结果返回即可。

相关代码实现：


int myStackTop(MyStack* obj) {
  assert(!myStackEmpty(obj));
  if (!QEmpty(&obj->q1)) return QBack(&obj->q1);
  else return QBack(&obj->q2);
}


  • 论栈的功能怎么能少得了判空呢。
  • 对于该栈的判空，我们实际上只需要判断那两个队列是否为空即可。

相关代码实现：


bool myStackEmpty(MyStack* obj) {
  return QEmpty(&obj->q2) && QEmpty(&obj->q1);
}


  • 最后就是栈的销毁了。
  • 将两个队列销毁（调用自己的销毁函数），然后将栈销毁即可。

相关代码实现：

void myStackFree(MyStack* obj) {
  QDestroy(&obj->q1);
  QDestroy(&obj->q2);
  free(obj);
}



整体的实现代码

// 队列的数据的类型
typedef int QDataType;
// 节点结构 
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
// 队列结构
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Que;
// 初始化队列
void QInit(Que* pq);
// 销毁队列
void QDestroy(Que* pq);
// 数据入队列
void QPush(Que* pq, QDataType x);
// 数据出队列
void QPop(Que* pq);
// 获取队列中有效元素个数
int QSize(Que* pq);
// 队列判空
bool QEmpty(Que* pq);
// 取队头数据
QDataType QFront(Que* pq);
// 取队尾数据
QDataType QBack(Que* pq);
// 初始化队列
void QInit(Que* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
// 队列销毁
void QDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
// 数据入队列
void QPush(Que* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->size == 0) pq->head = pq->tail = newnode;
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
// 数据出队列 
void QPop(Que* pq)
{
  assert(pq && !QEmpty(pq));
  if (pq->head == pq->tail)
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }
  else
  {
    QNode* tmp = pq->head->next;
    free(pq->head);
    pq->head = tmp;
  }
  pq->size--;
}
// 获取队列中有效元素个数
int QSize(Que* pq)
{
  assert(pq);
  return pq->size;
}
// 队列判空
bool QEmpty(Que* pq)
{
  assert(pq);
  return pq->size == 0;
}
// 取队头数据
QDataType QFront(Que* pq)
{
  assert(pq && !QEmpty(pq));
  return pq->head->data;
}
// 取队尾数据
QDataType QBack(Que* pq)
{
  assert(pq && !QEmpty(pq));
  return pq->tail->data;
}
typedef struct {
    Que q1;
    Que q2;
} MyStack;
bool myStackEmpty(MyStack* obj);
MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
  assert(obj);
  QInit(&obj->q1);
  QInit(&obj->q2);
  return obj;
}
void myStackPush(MyStack* obj, int x) {
  if (!QEmpty(&obj->q1)) QPush(&obj->q1, x);
  else QPush(&obj->q2, x);
}
int myStackPop(MyStack* obj) {
  assert(!myStackEmpty(obj));
  Que* emptyQ = &obj->q1;
  Que* nonemptyQ = &obj->q2;
  if (!QEmpty(emptyQ))
  {
    emptyQ = &obj->q2;
    nonemptyQ = &obj->q1;
  }
  while (QSize(nonemptyQ) > 1)
  {
    int front = QFront(nonemptyQ);
    QPush(emptyQ, front);
    QPop(nonemptyQ);
  }
  int front = QFront(nonemptyQ);
  QPop(nonemptyQ);
  return front;
}
int myStackTop(MyStack* obj) {
  assert(!myStackEmpty(obj));
  if (!QEmpty(&obj->q1)) return QBack(&obj->q1);
  else return QBack(&obj->q2);
}
bool myStackEmpty(MyStack* obj) {
  return QEmpty(&obj->q2) && QEmpty(&obj->q1);
}
void myStackFree(MyStack* obj) {
  QDestroy(&obj->q1);
  QDestroy(&obj->q2);
  free(obj);
}



😎写在最后


💝学会了用队列实现栈，那么下一篇文章就是教大家如何用栈实现队列了。栈和队列还真是有趣呢！

❤️‍🔥后续将会持续输出有关数据结构的文章，你们的支持就是我写作的最大动力！


感谢阅读本小白的博客，错误的地方请严厉指出噢~

文章标签：
C语言
算法
关键词：
数据结构栈
数据结构队列
算法栈
算法队列
数据结构与算法队列
游客ufqubef22u3cg
目录
相关文章
大数据文摘
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现，包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构，支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列，并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例（如`enqueue`入队和`dequeue`出队），展示了队列的操作逻辑，帮助读者深入理解其工作机制。
大数据文摘
665 1
RossyYan
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
1084 77
hahaha无
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
254 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
273 0
RossyYan
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
570 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
蓝易云
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
379 11
羑悻的小杀马特
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
500 14
陌陌谣
|
缓存 监控 算法
内网监控管理软件：PHP 语言队列算法揭秘
在数字化办公环境中，内网监控管理软件对企业的稳定运行和信息安全至关重要。本文深入介绍PHP中的队列算法及其在内网监控软件中的应用，包括监控数据收集、任务调度和日志记录等场景，通过代码示例展示其实现方法。队列算法可提高性能、保证数据顺序并实现异步处理，为企业提供高效的安全保障。
陌陌谣
266 1
RossyYan
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
519 7
ephemerals__
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
1288 10

热门文章

最新文章

  • 1
    《数据结构与算法：Python语言描述》一2.2Python的类
  • 2
    算法设计与分析/数据结构与算法实验7：0-1背包问题（分支限界法）
  • 3
    数据结构与算法—哈夫曼树详解与构造
  • 4
    educoder数据结构与算法 队列 第2关 实现一个链接存储的队列
  • 5
    [数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论（章节题库+答案解析）
  • 6
    [数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论（课后习题+答案解析）
  • 7
    【408数据结构与算法】—顺序表的插入、删除和查找（四）
  • 8
    educoder数据结构与算法 线性表 第2关：实现一个链接存储的线性表
  • 9
    【数据结构与算法】二叉树的深度，节点数，第k层的节点数，遍历，二叉树叶节点的个数
  • 10
    数据结构与算法——算法和算法分析
  • 1
    【机器学习】K-近邻算法（KNN）全面解析
    2166
  • 2
    [ICDE2024]多正常模式感知的频域异常检测算法MACE
    1024
  • 3
    探索机器学习中的支持向量机（SVM）算法
    546
  • 4
    快速排序算法详解
    950
  • 5
    归并排序算法深入解析
    595
  • 6
    中草药识别系统Python+深度学习人工智能+TensorFlow+卷积神经网络算法模型
    602
  • 7
    基于DCT变换和位平面分解的数字水印嵌入提取算法matlab仿真
    449
  • 8
    算法--topk问题
    226
  • 9
    C++如何实现一致性算法
    302
  • 10
    JVM性能调优：内存模型及垃圾收集算法
    250

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台
    • 下一篇
    小红书笔记详情API深度解析与实战指南（2025年最新版）