0
0

《数据结构》力扣题目 “用队列实现栈“ “设计循环队列” 详解

一. 225. 用队列实现栈

题目链接：

  1. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)

题目：用队列实现栈

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

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["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

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

解题思路：

0.先创建一个结构体 MyStack (这个结构体变量就是我们创建的“栈”)，“栈”中包含q1，q2两个队列，核心思想是：q1，q2中保持一个队列存储数据，另外一个队列空着；要出栈时，空队列用来倒数据，下面有出栈示意图(因为 队列是先进先出，栈是先进后出，所以主要是出栈需要改造)


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

出栈示意图：假设开始q1中有1,2,5三个值，q2为空队列 ; 最终q1前N-1个数据给q2，最后一个数据删掉，实现了栈的后进先出(或者先进后出)

逐个分析“栈”对应功能的函数：

1.创建栈：先开辟一块 MyStack 类型的空间并赋值给 指针pst，同时断言检查是否为NULL，再把此空间中的两个队列变量q1和q2都用队列初始化函数进行初始化，并返回这个地址pst

MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    assert(pst);
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

2.入栈： q1和q2一个是空的队列，一个是存数据的队列，方便后面出栈，通过 QueuePush 队列插入函数(相当于单链表尾插) 将数据给到不为空的队列中，因为刚开始都是空队列，所以给q1或q2都行，当其中一个为非空队列时，再次尾插就会尾插到这个非空队列中

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

3.出栈：把不为空的队列的数据前N-1导入另一个空队列,最后剩下的一个删掉。

前面先找出空队列 emptyQ 和非空队列 nonEmptyQ ，讲空队列的前N-1个数据导入另一个空队列,最后剩下的一个删掉。

int myStackPop(MyStack* obj) {
    assert(obj);
    Queue* emptyQ=&obj->q1;
    Queue* nonEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ=&obj->q2;
        nonEmptyQ=&obj->q1;
    }
    while(QueueSize(nonEmptyQ)>1)
    {
    QDataType front=QueueFront(nonEmptyQ);
    QueuePush(emptyQ,front);
    QueuePop(nonEmptyQ);
    }
    QDataType top=QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);
    return top;
}

4.找"栈"的栈顶：即最后一个结点的值，哪个队列不为空，就返回哪个队列的末尾节点的值。

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

5.判断“栈”是否为空：只要q1和q2两个队列全为空队列就返回true

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

6.释放“栈”：销毁q1，q2两个队列，并free“栈”的地址空间即可


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

完整代码实现：

typedef int QDataType;

typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
}Queue;

void QueueInit(Queue* pq);

void QueueDestory(Queue* pq);

void QueuePush(Queue* pq, QDataType x);

void QueuePop(Queue* pq);

bool QueueEmpty(Queue* pq);

size_t QueueSize(Queue* pq);

QDataType QueueFront(Queue* pq);

QDataType QueueBack(Queue* pq);

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = NULL;
    pq->tail = NULL;
}

void QueueDestory(Queue* pq)            //复盘！！！
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head =pq->tail = NULL;
    
}

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    assert(newnode);
    newnode->next = NULL;
    newnode->data = x;

    if (pq->tail == NULL)
    {
        assert(pq->head==NULL);
        pq->head = pq->tail = newnode;
    }
        
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;            //写的时候漏了！！！
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head && pq->tail);
    if (pq->head == pq->tail)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    //return pq->head == NULL && pq->tail == NULL;
    return pq->head == NULL;
}

size_t QueueSize(Queue* pq)
{
    assert(pq);
    size_t size = 0;
    QNode* cur = pq->head;
    while (cur)
    {
        size++;
        cur = cur->next;
    }
    return size;
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->tail);
    return pq->tail->data;

}

//——————————————————————————————————————————————————————以上是队列的操作

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

MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    assert(pst);
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    Queue* emptyQ=&obj->q1;
    Queue* nonEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ=&obj->q2;
        nonEmptyQ=&obj->q1;
    }
    while(QueueSize(nonEmptyQ)>1)
    {
    QDataType front=QueueFront(nonEmptyQ);
    QueuePush(emptyQ,front);
    QueuePop(nonEmptyQ);
    }
    QDataType top=QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);
        // if(!QueueEmpty(&obj->q2))
        // printf("1111111");
        //     if(!QueueEmpty(&obj->q2))
        // printf("2222222");
    return top;
}

int myStackTop(MyStack* obj) {
    assert(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);
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

二.622. 设计循环队列

题目链接：

622. 设计循环队列 - 力扣（LeetCode） (leetcode-cn.com)

题目：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

解题思路：

  1. 次循环队列有数组和单链表两个底层结构，该选哪一个呢？

答：选数组较好。实际上两者各有优劣，其实都差不多，

选数组的原因：

数组的优点：(也是单链表的缺点) 因为tail只能指向末尾数据的下一个地址，如果要找尾结点数据时，单链表找tail的上一个节点很费劲，数组就只需要tail-1就能找到。

数组的缺点：(也是单链表的优点) 如果是数组结构，当tail到最后一个节点时，为了成为循环队列结构，需要手动让tail=0，单链表就不用手动赋值。

0.0 创建结构体 MyCircularQueue ，包含数组队列int* a，整形front代表队列头部的角标，tail代表队列尾部的角标，k代表能存几个数据

typedef struct {
    int* a;
    int front;
    int tail;
    int k;
} MyCircularQueue;

接下来逐一分析我们创建的循环队列对应的各个函数：

1.创建循环队列函数：开辟一个循环队列的结构体的空间，地址名叫obj，通过下面动态图①发现：最开始front=tail=0，每增加一个数据，tail++，当增加k个(假设k=4)数据时，tail又不得不回到角标0处，此时front=tail=0，这样空列表和慢列表无法区分，(图②)为了避免空和满混淆，多开一个空间，front == tail时是空，tail的下一个位置是front就是满

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->tail=0;
    obj->k=k;
    return obj;
}

图①

图②

完整代码实现：

typedef struct {
    int* a;
    int front;
    int tail;
    int k;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->tail=0;
    obj->k=k;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    obj->a[obj->tail]=value;
    if(myCircularQueueIsFull(obj))
        return false;
    if(obj->tail==obj->k)
        obj->tail=0;
    else
        obj->tail++;
        return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
        return false;
    if(obj->front==obj->k)
    {
        obj->front=0;
    }
    else
    {
        obj->front++;
    }
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if( myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if( myCircularQueueIsEmpty(obj))
        return -1;
    if(obj->tail==0)
        return obj->a[obj->k];
    else
        return obj->a[obj->tail-1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front==obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    if(obj->tail==obj->k && obj->front==0)
        return true;
    return obj->tail+1==obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    free(obj->a);
    free(obj);
}
标签： 数据结构
本文转载自: https://blog.csdn.net/zhang_si_hang/article/details/123775302
版权归原作者 Don't forget Gitee 所有， 如有侵权，请联系我们删除。
登录后发布评论

“《数据结构》力扣题目 &ldquo;用队列实现栈&ldquo; &ldquo;设计循环队列&rdquo; 详解”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Linux 再入门整理：详解 /etc/fstab 文件

HBase Java API编程-学习记录

【大数据技术基础 | 实验十二】Hive实验：Hive分区

【前端】CSS

python 爬虫 入门 五、抓取图片、视频

Docker 中使用环境变量的安全实践

[Linux]——常见指令（中）

文章导航