【栈与队列面试题】用队列实现栈（动图演示）-阿里云开发者社区

两个队列实现一个栈

前言：

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣上栈与队列的面试OJ题目

队列的实现（前提准备）

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{ 
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;//表示队列整体,一个是出数据，一个是入数据.
void QueueInit(Queue* pq);// 初始化队列
void QueueDestroy(Queue* pq);// 销毁队列
void QueuePush(Queue* pq, QDataType x);// 队尾入队列
void QueuePop(Queue* pq);// 队头出队列
QDataType QueueFront(Queue* pq);// 获取队列头部元素
QDataType QueueBack(Queue* pq);// 获取队列队尾元素
int QueueSize(Queue* pq);// 获取队列中有效元素个数
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
void QueueInit(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  pq->phead=NULL; // 将队列的头指针置为空
  pq->ptail = NULL;// 将队列的头指针置为空
  pq->size = 0;// 将队列的头指针置为空
}
// void QPrint(Queue* pq)
// {
//  assert(pq);
//  QNode* cur = pq->phead;
//  QNode* next = cur;
//  while (cur != NULL)
//  {
//    printf("%d ", cur->data);
//    cur = cur->next;
//  }
// }
void QueueDestroy(Queue* pq)
{
  assert(pq);// 检查指针是否为空
    QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针
  while (cur)
  {
    QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针
    free(cur);// 释放当前节点的内存
    cur = next;// 将指针 cur 移动到下一个节点
  }
    pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
  pq->size = 0;// 将队列的大小置为0
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点
  if (newnode == NULL)
  {
    perror("malloc fail\n");// 检查内存分配是否成功
    return;
  }
    newnode->data = x;// 设置新节点的数据为传入的元素值
  newnode->next = NULL;// 将新节点的指针域置空
  //一个节点
  //多个节点
  if (pq->ptail == NULL)// 判断队列是否为空
  {
    //assert(pq->phead == NULL);// 如果队列为空，头指针也应为空
        pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点
  }
    else
  {
    pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点
    pq->ptail = newnode;// 更新队列的尾指针为新节点
  }
  pq->size++;// 增加队列的大小计数
}
void QueuePop(Queue* pq)
{
  assert(pq);// 检查指针是否为空
  assert(!QueueEmpty(pq));// 检查队列是否非空
  //assert(pq->phead);// 检查队列的头指针是否存在
  //1.一个节点
  if (pq->phead->next == NULL) // 队列只有一个节点的情况
  {
    free(pq->phead); // 释放队列头节点的内存
    pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
  }
  else
  {
    //头删
    QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针
    free(pq->phead);// 释放队列头节点的内存
    pq->phead = next;// 更新队列的头指针为下一个节点
  }
  pq->size--;//减少队列的大小计数
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));// 检查队列是否非空
  //assert(pq->phead);// 检查队列的头指针是否存在
  return pq->phead->data;// 返回队列头节点的数据
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);// 检查队列是否非空
  assert(!QueueEmpty(pq));// 检查队列是否非空
  //assert(pq->phead);// 检查队列的头指针是否存在
  return pq->ptail->data;//返回队列尾节点的数据
}
int QueueSize(Queue* pq)
{
  assert(pq);//检查指针是否为空
  return pq->size;//返回队列的大小（元素个数）
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //方法一,将队列的头指针以及尾指针置空
  //return pq->phead = NULL && pq->ptail==NULL;
  //方法二,将队列的有效元素置空
  return pq->size == 0;
}

一.题目描述

来源:225. 用队列实现栈 - 力扣（LeetCode）

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

实现 MyStack 类：

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

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

int top() 返回栈顶元素。

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

需要了解的知识：

栈(Stack)：

后进先出(LIFO)顺序:最后压入栈的元素,第一个弹出栈。它像一堆盘子,最后放上的盘子,先拿走。

在栈顶添加,在栈顶删除:所有新元素都放在栈顶,操作栈时只有栈顶元素可以被访问。

压栈和出栈操作不可逆:当一个元素被压入栈后,要等到它到栈顶位置才能将其弹出。栈不允许非栈顶元素先出栈。

有大小限制:每个栈都有最大容量限制,栈满时不能继续压入新元素。

主要操作:栈主要支持两种操作 - 入栈(push)和出栈(pop),所有元素都从栈顶压入/弹出。

适合处理后进先出的任务:栈这种后进先出的特性,适合模拟那些需要后操作的先完成的场景,如函数调用堆栈。

总结：是一种后进先出的线性表,只允许在表的一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的元素最后才能取出,具有先进后出的逻辑顺序。

队列(Queue)：

先进先出(FIFO)顺序:先进入队列的元素会先出队列,后进入的元素后出队列。

在队尾添加,在队头删除:所有新元素都添加在队尾,删除元素时都从队头删除元素。

出队操作不可取消:已进入队列的元素不能中途删除,只能等待它到队头后再删除它。

有大小限制:队列通常有最大容量限制,队列满时不能再加入新元素,必须等待队头元素出队后才能加入。

主要操作:队列主要支持两种操作 - 入队(enqueue)和出队(dequeue),入队是将元素加入队尾,出队是从队头删除元素。

适合处理先进先出的任务:队列适合去处理需要先进先出顺序的任务,比如打印任务队列、排队等。

总结：是一个先进先出、有顺序的线性表,它只允许在一端进行插入,在另一端进行删除,遵循先进先出的原则。这使其非常适合模拟现实生活中的排队等情形。

1.自定义栈的结构

MyStack 这个结构体模拟了一个栈的数据结构,它使用两个队列 q1 和 q2 来实现栈的功能。

typedef struct {
  Queue q1;
  Queue q2;
} MyStack;

2.自定义栈的初始化

使用malloc 函数为 MyStack 结构体对象分配内存空间。sizeof(MyStack) 表示要分配的内存大小等于 MyStack 结构体的大小。返回的指针类型是void* 。

因此需要进行类型转换为 MyStack*类型并将其赋值给 obj变量,初始化 obj 指向的 MyStack 结构体中的队列q1 和 q2。如果内存分配和初始化成功，最后，函数返回指向新创建的MyStack对象的指针obj

代码实现：

MyStack* myStackCreate() {
    MyStack *obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL; 
    }
   //用于初始化 obj 指向的 MyStack 结构体中的队列 q1 和 q2
    QueueInit(&obj->q1);//初始化q1队列
    QueueInit(&obj->q2);//初始化q2队列
    //返回指向已创建并初始化的 MyStack 结构体对象的指针 obj
    return obj;
}

3.将元素压入栈顶

将元素推入栈时：

如果队列 q1 不为空，就将元素直接推入 q1 中；

如果 q1 为空，就将元素推入 q2 中。

这样的实现方式可以确保在栈中的元素都集中在一个队列中（要么是 q1，要是 q2），而另一个队列则保持为空。这种实现方式的优势在于在执行出栈操作时，可以将非空队列中的元素转移到另一个空队列中，以便实现栈的先进后出特性。

void myStackPush(MyStack* obj, int x) {
  if (!QueueEmpty(&obj->q1))// 如果 q1 不为空，将元素推入 q1
  {
    QueuePush(&obj->q1, x);
  }
  else// 如果 q1 为空，将元素推入 q2
  {
    QueuePush(&obj->q2, x);
  }
}

4.移除并返回栈顶元素

演示一遍出栈过程

演示全程出栈过程(只演示栈内部的队列)

代码实现:

int myStackPop(MyStack* obj)//栈出元素
 {
    //假设q1队列是空队列,q2非空队列
    Queue* pEmptyQ=&obj->q1;
    Queue* pNonEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))//如果q1不为空
    {
      //此时空队列指针指向q2
      pEmptyQ=&obj->q2;
      pNonEmptyQ=&obj->q1;//非空队列指针指向q1
    }
    //挪数据,结束条件是非空队列的元素个数为1
    while(QueueSize(pNonEmptyQ)>1)
    {
        QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));//获取非队列头部元素，把非空队列的元素入到空队列，
        QueuePop(pNonEmptyQ);//接着非空队列出元素
    }
    //此时非空队列只有一个元素
    int top=QueueFront(pNonEmptyQ);//获取此时非空队列的头部元素
    QueuePop(pNonEmptyQ);//到这步,非空队列出完所有元素
   // 返非空队列元素
    return top;
}

5.返回栈顶元素

q1队列如果不为空，那么返回q1队列的队尾元素当作自定义栈的栈顶元素，反之q2亦然。

int myStackTop(MyStack* obj)//返回栈顶元素
{
    if(!QueueEmpty(&obj->q1))//q1队列如果不为NULL
    {
        return QueueBack(&obj->q1);//返回q1队尾元素
    }
    else//q2队列如果不为NULL
    {
        return QueueBack(&obj->q2);//返回q2队尾元素
    }
}

6.判断栈是否为空栈

判空就是要判断q1队列和q2队列都为空，才证明这个栈为空栈。

bool myStackEmpty(MyStack* obj)//判断自定义栈是否为空栈
{
    return QueueEmpty(&obj->q1) &&
    QueueEmpty(&obj->q2);
}

7.栈的销毁

错误写法：内存泄露

正确写法：

先把q1和q2队列指向的节点free掉，接着再free掉整个MyStack，这样确保了不会内存泄露。

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

自定义栈的代码实现

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack *obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL; 
    }
    QueueInit(&obj->q1);//初始化q1队列
    QueueInit(&obj->q2);//初始化q2队列
    return obj;
}
// //注意以下写法
// typedef struct
// {
//     Queue* q1;
//     Queue* q2;
// }MyStack;
// MyStack* myStackCreate()
// {
//     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
//     if(obj == NULL)
//     {
//         perror("malloc fail");
//         return NULL;
//     }
//     obj->q1=(Queue*)malloc(sizeof(Queue));
//     obj->q2=(Queue*)malloc(sizeof(Queue));
//     QueueInit(obj->q1);
//     QueueInit(obj->q2);
//    return obj;
// }
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))//
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj)//栈出元素
 {
    //假设q1队列是空队列,q2非空队列
    Queue* pEmptyQ=&obj->q1;
    Queue* pNonEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))//如果q1不为空
    {
      //此时空队列指针指向q2
      pEmptyQ=&obj->q2;
      pNonEmptyQ=&obj->q1;//非空队列指针指向q1
    }
    //挪数据,结束条件是非空队列的元素个数为1
    while(QueueSize(pNonEmptyQ)>1)
    {
        QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));//获取非队列头部元素，把非空队列的元素入到空队列，
        QueuePop(pNonEmptyQ);//接着非空队列出元素
    }
    //此时非空队列只有一个元素
    int top=QueueFront(pNonEmptyQ);//获取此时非空队列的头部元素
    QueuePop(pNonEmptyQ);//到这步,非空队列出完所有元素
   // 返非空队列元素
    return top;
}
int myStackTop(MyStack* obj)//返回栈顶元素
{
    if(!QueueEmpty(&obj->q1))//q1队列如果不为NULL
    {
        return QueueBack(&obj->q1);//返回q1队尾元素
    }
    else//q2队列如果不为NULL
    {
        return QueueBack(&obj->q2);//返回q2队尾元素
    }
}
bool myStackEmpty(MyStack* obj)//判断自定义栈是否为空栈
{
    return QueueEmpty(&obj->q1) &&
    QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

代码执行：

到这里文章就结束了，如有错误欢迎指正，感谢你的来访与支持！

【栈与队列面试题】用队列实现栈（动图演示）