【Leetcode】队列的性质与应用

文章目录

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（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 都保证栈不为空

分析：

目前没有学习C++，所以先用C语言实现。那么就要手撕一个队列。例子：输入1 2 3 4，输出 4 3 2 1，根据队列的性质先进先出，所以先要进行移数据只剩一个，然后出数据，来回倒腾。

题解：

#include<stdio.h>#include<assert.h>#include<malloc.h>#include<stdbool.h>typedefint QDataType;//这是结点的结构，但是队列是FIFO，所以要记录头指针和尾指针，方便尾入和头出typedefstructQueueNode{structQueueNode* next;
    QDataType data;}QNode;typedefstructQueue{
    QNode* head;//有多个数据就可以再使用一个结构体
    QNode* tail;int size;}Queue;voidQueueInit(Queue* pq);//队列的初始化voidQueueDestroy(Queue* pq);//队列的销毁voidQueuePush(Queue* pq, QDataType x);//队列的尾部插入数据voidQueuePop(Queue* pq);//队列的头部删除数据
bool QueueEmpty(Queue* pq);//判断队列为不为空intQueueSize(Queue* pq);//知道队列有几个有效元素
QDataType QueueFront(Queue* pq);//返回队列的首个元素
QDataType QueueBack(Queue* pq);//返回队列的尾元素voidQueueInit(Queue* pq){assert(pq);
    pq->head = pq->tail =NULL;//队列的初始化将两个指针置为空
    pq->size =0;//有效元素为0}voidQueueDestroy(Queue* pq){assert(pq);//将一个结点指针指向头节点，作为循环的条件
    QNode* cur = pq->head;while(cur){
        QNode* del = cur->next;//一个要删除的结点free(cur);
        cur = del;//指向下一个结点}//销毁时及时将两个指针置为空，避免野指针的出现
    pq->head = pq->tail =NULL;
    pq->size =0;}voidQueuePush(Queue* pq, QDataType x){assert(pq);
    QNode* newnode =(QNode*)malloc(sizeof(QNode));//malloc申请新的结点if(newnode ==NULL){perror("malloc fail");//申请失败报错并返回return;}//如果为空队列，那么就要将指针同时指向新的结点if(pq->head ==NULL){
        pq->head = pq->tail = newnode;}else//这里没加else语句，那么if执行了的话就会混乱{
        pq->tail->next = newnode;
        pq->tail = newnode;//同时将尾指针指向新的结点}//将尾结点的next指向新的结点
    newnode->data = x;//新的结点进行赋值
    newnode->next =NULL;
    pq->size++;//有效元素进行加1}voidQueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));//空的队列就不能删除

     QNode* del = pq->head;
    pq->head = pq->head->next;//将头指针指向下个结点free(del);//释放空间
    del =NULL;//这里要考虑只有一个节点的时候，tail可能会是野指针if(pq->head ==NULL){
        pq->tail =NULL;}
    pq->size--;//有效元素减1}

bool QueueEmpty(Queue* pq){assert(pq);return pq->size ==0;}intQueueSize(Queue* pq){assert(pq);return pq->size;}

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

QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}//创建两个队列typedefstruct{
    Queue q1;
    Queue q2;} MyStack;

MyStack*myStackCreate(){//对队列进行初始化
    MyStack* newStack =(MyStack*)malloc(sizeof(MyStack));if(newStack ==NULL){perror("malloc fail");returnNULL;}QueueInit(&newStack->q1);QueueInit(&newStack->q2);return newStack;}voidmyStackPush(MyStack* obj,int x){//如果一个队列为空，那么就放入另一个队列if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}}intmyStackPop(MyStack* obj){//利用假设法找出有数据的队列
    Queue* emptyq =&obj->q1;
    Queue* nonemptyq =&obj->q2;if(!QueueEmpty(&obj->q1)){
        emptyq =&obj->q2;
        nonemptyq =&obj->q1;}//进行倒元素，直到剩下一个元素while(QueueSize(nonemptyq)>1){QueuePush(emptyq,QueueFront(nonemptyq));QueuePop(nonemptyq);}int top =QueueFront(nonemptyq);QueuePop(nonemptyq);return top;}intmyStackTop(MyStack* obj){//哪一个不为空就返回哪一个if(!QueueEmpty(&obj->q1)){returnQueueBack(&obj->q1);}else{returnQueueBack(&obj->q2);}}

bool myStackEmpty(MyStack* obj){returnQueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}voidmyStackFree(MyStack* obj){//malloc几次，就要释放几次QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

622. 设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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

提示：

所有的值都在 0 至 1000 的范围内；

操作数将在 1 至 1000 的范围内；

请不要使用内置的队列库。

分析：

这道题目可以使用数组实现，这是一个空间固定的数组，如何判断这个数组是满还是空呢？可以多开一个空间作为缓冲位置。

每次插入之前要判断是否满了，每次删除之前要判断是否空了。
还要考虑rear在队尾时如何判满？rear在队头时如何找到最后一个数？front在队尾时如何判断为多少？

题解：

typedefstruct{int* s;int front;int rear;int k;} MyCircularQueue;//创建循环队列
MyCircularQueue*myCircularQueueCreate(int k){
    MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj ==NULL){perror("malloc fail");returnNULL;}//创建数组时，多创建一个空间，以便进行循环
    obj->s =(int*)malloc(sizeof(int)*(k +1));if(obj->s ==NULL){perror("malloc fail");returnNULL;}//将头指针和尾指针置为空，将长度记住
    obj->front = obj->rear =0;
    obj->k = k;return obj;}//如果头指针和尾指针相等，代表为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj){return obj->rear == obj->front;}//为满的情况：1. rear在front前面，直接进行加1是否相等，相等则满了//2. rear在front后面，考虑rear在队尾，那么要将rear指向下标0，就要进行模运算，相等就满了
bool myCircularQueueIsFull(MyCircularQueue* obj){return(obj->rear +1)%(obj->k +1)== obj->front;}

bool myCircularQueueEnQueue(MyCircularQueue* obj,int value){//插入元素，如果为满就返回假if(myCircularQueueIsFull(obj))return false;
    obj->s[obj->rear]= value;//让rear指向下个位置，考虑rear在队尾，那么就要进行模运算
    obj->rear =(obj->rear +1)%(obj->k +1);return true;}

bool myCircularQueueDeQueue(MyCircularQueue* obj){//删除元素，如果为空就返回假if(myCircularQueueIsEmpty(obj))return false;//要将front指向下一个，但是要考虑front在队尾，进行模运算
    obj->front =(obj->front +1)%(obj->k +1);return true;}intmyCircularQueueFront(MyCircularQueue* obj){//队列为空返回-1if(myCircularQueueIsEmpty(obj))return-1;return obj->s[obj->front];}intmyCircularQueueRear(MyCircularQueue* obj){//队列为空返回-1if(myCircularQueueIsEmpty(obj))return-1;//考虑rear在队头的情况，在队头就赋值为队尾元素，其它情况就返回前一个元素int tail = obj->rear ==0?obj->s[obj->k]:obj->s[obj->rear -1];return tail;}voidmyCircularQueueFree(MyCircularQueue* obj){//申请两个空间就要释放两个空间free(obj->s);free(obj);}/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/