AI 助理
文档备案控制台
开发者社区 云计算 文章 正文

【数据结构经典题目】—两个队列实现栈与两个栈实现队列

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

🍂两个队列实现栈

问题的描述以及要求

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

思路整理

首先理清一点，队列实现是先进先出，而栈是后进先出，我们需要使用两个队列来实现栈。对此，我的思路是一个队列用于入栈用，而另外一个队列用于出栈。对此，在这个基础上设立了如下的结构体：

typedef struct QNode//队列节点
{
    int data;
    struct QNode* next;
}QNode;
typedef struct Queue//队列
{
    QNode* front;
    QNode* tail;
}Queue;
typedef struct {
    QNode q1;
    QNode q2;
} MyStack;
具体的思路：

      保持一个队列在出栈前为空的状态，而另外一个队列则是出栈前一直用于入队。然后，当程序需要出栈了，我们将不为空的那个队列，也就是用于入队的队列的前N-1个数据出队，将原本为空的那个队列入队这N-1个数据。在此之后，我们发现原本作为入队的队列仅仅剩下了最后一个数据，而原本为空的队列拥有了N-1个数据，此时那剩下的一个数据不就是栈顶的数据吗？我们只需要将这个数据进行出队操作便可。而在这个数据出队操作完成后，这个两个队列的性质进行了交换，原本为空的队列，现在拥有N-1个数据，原本不为空的队列，现在为空了，因此，在接下来的操作需要转换两个队列的入队性质。


一图带你了解~

每个操作的实现

初始化
MyStack* myStackCreate() {
    MyStack* new=(MyStack*)malloc(sizeof(MyStack));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

      这里对于为什么对new->q1,new->q2取地址做出解释：由于前面结构体的定义为 QNode q1;QNode q2;而QueueInit内传参为指针所以取地址&。

判空
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
入栈
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }else
    {
        QueuePush(&obj->q2,x);
    }
}

  入栈操作主要在于对于两个队列进行判断，判断出入上文思路所述，其中一个为空，以此，将空的队列作为入栈操作。

出栈
int myStackPop(MyStack* obj) {
    assert(obj);
    MyStack* empty=&obj->q1;
    MyStack* nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueTop(nonempty));
        QueuePop(nonempty);
    }
    int re=QueueTop(nonempty);
    QueuePop(nonempty);
    return re;
}

     出栈操作是用两个队列实现栈的最关键的一步。首先创建两个结构体指针，一个用于存放空的队列，另外一个存不为空的队列。这时候有人就要问了，你怎么知道哪个是空的哪个不是空的。别急，这不有个if的判断语句来判断吗？(*^▽^*)。接着，按照思路，将不为空的队列N-1个数据入队到原来为空的的队列，最后再对剩下的一个数据进行出栈。

取栈顶元素
int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

       这个简单，只需要将不为空的队列的最后一个元素给出去就好了！

销毁栈
void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

🍁整体代码

typedef struct QNode//队列节点
{
    int data;
    struct QNode* next;
}QNode;
typedef struct Queue//队列
{
    QNode* front;
    QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* queue);
//队列是否为空
bool QueueEmpty(Queue* queue);
//进队
void QueuePush(Queue* queue, int x);
//出队
void QueuePop(Queue* queue);
//队列头部元素
int QueueTop(Queue* queue);
//队列尾部元素
int QueueBack(Queue* queue);
//队列有效元素个数
int QueueSize(Queue* queue);
//销毁队列
void QueueDestroy(Queue* queue);
void QueueInit(Queue* queue)//初始化
{
    assert(queue);
    queue->front = NULL;
    queue->tail = NULL;
}
//队列是否为空
bool QueueEmpty(Queue* queue)
{
    assert(queue);
    return queue->tail == NULL;
}
//进队
void QueuePush(Queue* queue, int x)
{
    assert(queue);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    assert(newnode);
    newnode->data = x;
    newnode->next = NULL;
    if(queue->tail == NULL)
    {
        queue->front = queue->tail = newnode;
    }
    else
    {
        queue->tail->next = newnode;
        queue->tail = newnode;
    }
}
//出队
void QueuePop(Queue* queue)
{
    assert(queue);
    QNode* next = queue->front->next;
    free(queue->front);
    queue->front = next;
    if(queue->front == NULL)
    {
        queue->tail = NULL;
    }
}
//队列头部元素
int QueueTop(Queue* queue)
{
    assert(queue);
    assert(queue->front);
    return queue->front->data;
}
//队列尾部元素
int QueueBack(Queue* queue)
{
    assert(queue);
    assert(queue->tail);
    return queue->tail->data;
}
//队列有效元素个数
int QueueSize(Queue* queue)
{
    assert(queue);
    int size = 0;
    QNode* cur = queue->front;
    while(cur != NULL)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}
//销毁队列
void QueueDestroy(Queue* queue)
{
    assert(queue);
    QNode* next = queue->front;
    while(next != NULL)
    {
        next = queue->front->next;
        free(queue->front);
        queue->front = next;
    }
    queue->tail = NULL;
}
typedef struct {
    QNode q1;
    QNode q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* new=(MyStack*)malloc(sizeof(MyStack));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }else
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj) {
    assert(obj);
    MyStack* empty=&obj->q1;
    MyStack* nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueTop(nonempty));
        QueuePop(nonempty);
    }
    int re=QueueTop(nonempty);
    QueuePop(nonempty);
    return re;
}  
bool myStackEmpty(MyStack* obj);
int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

🍃两个栈实现队列

问题的描述以及要求

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

思路整理

       首先理清一点，栈实现是后进先出，而队列是先进先出，我们需要使用两个栈来实现队列。对此，我的思路是一个栈用于入队用，而另外一个栈用于出队。对此，在这个基础上设立了如下的结构体：

typedef int STDataType;
typedef struct Stack//变长的数组栈
{
  STDataType* a;
  int top;
  int capacity;
}SLtack;
typedef struct {
    SLtack push;
    SLtack pop;
} MyQueue;
具体的思路：              

        将一个栈当作输入栈，用于压入push 传入的数据；另一个栈当作输出栈，用于 pop操作。每次 pop 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。若不为空，则只有将所有输出栈的数据都pop完后，才将输入栈的数据弹入输出栈。再对输出栈进行pop操作。

一图让你了然~

每个操作的实现

初始化
MyQueue* myQueueCreate() {
    MyQueue* new=(MyQueue*)malloc(sizeof(MyQueue));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    StackInit(&new->push);
    StackInit(&new->pop);
    return new;
}

       这里对于为什么对new->push,new->pop取地址做出解释：由于前面结构体的定义为SLtack push;SLtack pop;而StackInit内传参为指针所以取地址&。

判空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
}
入队
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->push,x);
}

入队操作只需要对push栈进行入栈操作即可

出队
int myQueuePop(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    int re=StackTop(&obj->pop);
    StackPop(&obj->pop);
    return re;
}

    出队操作是实现两个栈实现队列的关键。需要将push栈中的数据全都压栈道pop栈，注意只有pop为空时才进行以上操作。然后就是对于pop栈进行正常的出栈操作即可。

取队头元素
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}

这里主要还是同出队操作差不多，取队头的元素需要在pop栈上的top取！

销毁队列
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->push);
    StackDestroy(&obj->pop);
    free(obj);
    obj==NULL;
}

🌿整体代码

typedef int STDataType;
typedef struct Stack//变长的数组栈
{
  STDataType* a;
  int top;
  int capacity;
}SLtack;
// 初始化栈 
void StackInit(SLtack* ps);
// 入栈 
void StackPush(SLtack* ps, STDataType data);
// 出栈 
void StackPop(SLtack* ps);
// 获取栈顶元素 
STDataType StackTop(SLtack* ps);
// 获取栈中有效元素个数 
int StackSize(SLtack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(SLtack* ps);
// 销毁栈 
void StackDestroy(SLtack* ps);
void StackInit(SLtack* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = ps->capacity = 0;//top初始化为0，则top指向栈顶的下一个元素
}
void StackPush(SLtack* ps, STDataType data)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    ps->capacity =ps->capacity== 0 ? 4 : ps->capacity * 2;
    ps->a = (STDataType*)realloc(ps->a, sizeof(int) * ps->capacity);
  }
  ps->a[ps->top] = data;
  ps->top++;
}
void StackPop(SLtack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
STDataType StackTop(SLtack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
int StackSize(SLtack* ps)
{
  assert(ps);
  return ps->top;
}
int StackEmpty(SLtack* ps)
{
  assert(ps);
  return ps->top == 0;
}
void StackDestroy(SLtack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
typedef struct {
    SLtack push;
    SLtack pop;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* new=(MyQueue*)malloc(sizeof(MyQueue));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    StackInit(&new->push);
    StackInit(&new->pop);
    return new;
}
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->push,x);
}
bool myQueueEmpty(MyQueue* obj);
int myQueuePop(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    int re=StackTop(&obj->pop);
    StackPop(&obj->pop);
    return re;
}
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
}
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->push);
    StackDestroy(&obj->pop);
    free(obj);
    obj==NULL;
}



     感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！

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

热门文章

最新文章

  • 1
    数据结构之洪水填充算法（DFS）
  • 2
    数据结构中的KMP算法及其改进算法
  • 3
    redis 系列8 数据结构之整数集合
  • 4
    小菜一步一步学数据结构之(五)顺序栈
  • 5
    数据结构与算法C#版笔记--排序(Sort)-上
  • 6
    数据结构实验：连通分量个数
  • 7
    数据结构：数组
  • 8
    Redis中ZSet的底层数据结构跳跃表skiplist，你真的了解吗？
  • 9
    单调栈
  • 10
    数据结构例程——应用图的广度优先遍历思路求解问题
  • 1
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
    728
  • 2
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
    656
  • 3
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
    703
  • 4
    软考中级软件设计师专项-数据结构与算法上篇
    868
  • 5
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
    781
  • 6
    Redis基础命令与数据结构概览
    294
  • 7
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
    520
  • 8
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
    846
  • 9
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
    799
  • 10
    Redis核心数据结构与分布式锁实现详解
    1106

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！