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

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

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

🍂两个队列实现栈

问题的描述以及要求

       使用两个队列实现一个后入先出（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！

关键词：
数据结构栈
数据结构队列
数据结构队列栈
数据结构题目
慕斯(˘▽˘)っ
目录
相关文章
一颗小谷粒
|
1天前
|
算法
数据结构与算法：栈与队列
数据结构与算法：栈与队列
一颗小谷粒
7 0
泥腿子架构师
|
1天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
泥腿子架构师
16 2
誓则盟约
|
4天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
誓则盟约
11 0
jjczqyjxgdegi
|
5天前
|
存储 人工智能 程序员
技术心得记录：堆(heap)与栈(stack)的区别
技术心得记录：堆(heap)与栈(stack)的区别
jjczqyjxgdegi
5 0
枫叶丹4
|
7天前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
枫叶丹4
6 0
倔强的石头_
|
7天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
倔强的石头_
15 0
倔强的石头_
|
7天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
倔强的石头_
14 1
倔强的石头_
|
7天前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
倔强的石头_
10 0
倔强的石头_
|
7天前
|
存储 算法 编译器
【数据结构与算法】使用数组实现栈：原理、步骤与应用
【数据结构与算法】使用数组实现栈：原理、步骤与应用
倔强的石头_
10 0
反季雪
|
7天前
|
算法
【数据结构和算法】---栈和队列的互相实现
【数据结构和算法】---栈和队列的互相实现
反季雪
7 0