队列实现及leetcode相关OJ题

上一篇写的是栈这一篇分享队列实现及其与队列相关OJ题

---

---

一、队列概念及实现

1、队列概念

队列同栈一样也是一种特殊的数据结构，遵循先进先出的原则，例如：想象在独木桥上走着的人，先上去的人定是先从独木桥上下来，为啥说是特殊呢？因为它只允许在对尾插入数据 (简称入队 ，然后在对头删除数据(简称出队)，只允许在这两端进行插入和删除操作

而基于它的特性选择链表实现还是数组实现更好呢？

当然选链表实现比较好，因为数组在头删除时需要移动大量的数据，时间复杂度为O(N)，而用链表头删时间复杂度为O(1),那么有人会说那链表的尾插时间复杂度不也是O(N)吗，因为每次都要找尾节点

其实可以创建两个指针，一个指向对头，一个指向队尾，这样就不用每次都找尾了，时间复杂度也是O(1)。由于是多个数据，选择用结构体将其封装起来，而我们在链表每次访问长度的时候时间复杂度都为O(N),因此再在这个队列结构体中定义一个size表示队列大小

队列结构定义

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

队列中的元素是每个节点，而每个节点又有多个数据存放下一个节点地址的next,存放每个节点数据的data,相当于队列里面它的成员又是一个结构体然后还有表示队列大小的size

typedef struct Queue
{//Queue结构体中成员又包含结构体QNode* head;//头指针指向头节点QNode* tail;//尾指针指向尾节点int size;//队列中节点的个数
}Queue;

队列实现

队列初始化

void QInit(Queue* pq)
{
// 传过来的时候就怕传一个空地址过来，那么队列都没有还怎么对其操作assert(pq);pq->head = pq->tail = NULL;//pq->size = 0;
}

队列销毁

void QDestroy(Queue* pq)
{assert(pq);assert(pq->head!=NULL);//对都为空那么就不用再释放了while (pq->head){QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->head = pq->tail = NULL;pq->size = 0;
}

入队

void QPush(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->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}//入队之后队列长度就要增一pq->size++;
}

出队

void QPop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//队列不空才出队//队列中只有一个元素的时候,这时也就是对头指针和队尾指针指向同一个节点if (pq->tail == pq->head){free(pq->head);pq->head = pq->tail = NULL;}//找到头节点的下一个节点else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}//出队之后队列长度会减一pq->size--;
}

判空

bool QEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;//直接返回对头指针，对头指针为空的话队列即为空
}

取对头元素

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

取队尾元素

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

获取队列长度

int QSize(Queue* pq)
{assert(pq);assert(pq->head);//由于size直接获得队列大小，因此直接返回size即可return pq->size;
}

---

二、队列源码

Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
typedef struct QNode
{struct QNode* next;QDataType data;
}QNode;typedef struct Queue
{//Queue结构体中成员又包含结构体QNode* head;//头指针QNode* tail;int size;//队列中节点的个数
}Queue;
//初始化
void QInit(Queue* pq);
//销毁队列
void QDestroy(Queue* pq);
//入队
void QPush(Queue* pq, QDataType x);
//出队
void QPop(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//获取对头
QDataType QFront(Queue* pq);
//队大小
int QSize(Queue* pq);
//返回队尾元素
QDataType QTail(Queue* pq);

queue.c

void QInit(Queue* pq)
{
// 传过来的时候就怕传一个空地址过来，那么队列都没有还怎么对其操作assert(pq);pq->head = pq->tail = NULL;//pq->size = 0;
}
void QDestroy(Queue* pq)
{assert(pq);//assert(pq->head!=NULL);//对头都为空那么就不用再释放了while (pq->head){QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QPush(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->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++;
}void QPop(Queue* pq)
{assert(pq);assert(pq->head != NULL);if (pq->tail == pq->head){free(pq->head);pq->head = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}bool QEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}QDataType QFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}int QSize(Queue* pq)
{assert(pq);assert(pq->head);return pq->size;
}QDataType QTail(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}

test.c

#include"Queue.h"int main()
{Queue pq;QInit(&pq);QPush(&pq, 1);QPush(&pq, 2);QPush(&pq, 3);QPush(&pq, 4);/*while (!QEmpty(&pq)){printf("%d ", QFront(&pq));QPop(&pq);}*/printf("%d ", QTail(&pq));printf("%d ", QSize(&pq));QDestroy(&pq);return 0;
}

三、leetcode相关OJ

1、用队列实现栈

由于队列是先进先出，栈是先进后出

具体思想那么要用队列来实现栈就要保证最先进栈的要最后出栈，可是队列又是先进先出，要保证队列最后一个先出去的话，那么让那个不为空的队列其队尾为止前面的元素依次倒入另外一个队列中，然后取出这个数据那个那么就用两个队列才能完成

而队列就是我上面写的咯

QDataType QTail(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}
//栈里有两个队列
typedef struct {Queue q1;Queue q2;
} MyStack;//创建这个栈是要返回栈的地址的
//那么就malloc一个栈出来
//如果不向内存动态申请一个栈而是直接创建一个栈，那么创建的栈就是一个临时变量，它出了这个函数空间就会自动
MyStack* myStackCreate() {MyStack*st = (MyStack*)malloc(sizeof(MyStack));if(st == NULL){perror("malloc fail\n");return NULL;}else{//创建栈之后需要将栈结构体成员中的连个队列也初始化而这个队列又是一个结构体，且要改变队列内容就需传结构体地址传过去//st是栈的结构体指针村的是栈的地址，对->访问它的成员，得到队列q1,q2，由于是用队列实现栈所以操作其实都是队列实现的，相当于操作的是队列，然后&st->q1就是传队列地址QInit(&st->q1);QInit(&st->q2);return st;}
}//入栈是往队列不为空的那个里面入，
//最开始两个队列都是空就随便入一个，但是后面再入栈时就要往不为空的那个队列里面入数据。
void myStackPush(MyStack* obj, int x) {if(!QEmpty(&obj->q1)){QPush(&obj->q1,x);}else{QPush(&obj->q2,x);}
}//栈是一个后进先出的特殊数据结构，且每次要出数据只能从栈顶出
//而队列是一种先进先出的特殊数据结构，且出数据只能在对头出，而我们要用对列来实现这个栈，我们只有将不为空的 那个队列中队尾元素之前的元素倒入那个为空的队列中，然后将原来那个不为空队列的队尾元素保存下来，最后将其出掉，然后如果再次调用出栈这个函数接口，那么也是一样的操作
//这里出队不是将那些元素丢掉，而是将这些出队元素入到原本为空的那个队列中
//
int myStackPop(MyStack* obj) {Queue*empty = &obj->q1;//这里先默认q1为空队列Queue*nonempty = &obj->q2;if(!QEmpty(&obj->q1))//然后再判断队列q1是否为空，队列q1如果不为空，那么队列q2就是空咯{empty = &obj->q2;nonempty = &obj->q1;}//将不为空的队列nonempty中对头元素先入到原来为空的队列empty中去，然后再将对头元素出掉，出到只剩下一个元素为止while(QSize(nonempty)>1){//将要出的数据反手就入到empty空的队列中去QPush(empty,QFront(nonempty));//然后再出数据QPop(nonempty);}int top = QFront(nonempty);QPop(nonempty);return top;}//返回栈顶元素，其实就是返回不为空队列nonempty这个队尾数据
int myStackTop(MyStack* obj) {Queue*empty = &obj->q1;Queue*nonempty = &obj->q2;if(!QEmpty(&obj->q1)){empty = &obj->q2;nonempty = &obj->q1;}return QTail(nonempty);
}//判断栈是否为空就是判断两个队列中是否还有元素，其中一个还有都不为空
bool myStackEmpty(MyStack* obj) {return QEmpty(&obj->q1) &&QEmpty(&obj->q2);
}//销毁栈不嫩一下子就将栈释放了，因为如果一下子就将栈释放了的话，你是释放了你这个栈里面的成员q1,q2,但是人家q1,q2里安他自己还有数据啊，这样造成了内存泄漏不得行
//而是一个先销毁队列中的数据然后再释放栈void myStackFree(MyStack* obj) {QDestroy(&obj->q1);QDestroy(&obj->q2);free(obj);
}

2、leetcode用栈实现队列

思想：用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作 出队操作：当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作

//由于栈最先进去的数据要最后才能获得 //假设1，2，3，4是按顺序依次入队那么它的出队顺序也是1，2，3，4
//要用栈来实现队列那么就要让原来的数据以逆序4，3
，2，1的方式存储到栈中然后每次出栈顶的数据就可以实现队列的先进先出，而一个栈明显行不通，这时让一个栈用来实现入队，栈push用来模拟入队，那么进栈也就是1，2，3，4，将从push栈依次得到的数据倒入pop栈中，pop栈中进栈就是4，3，2，1那么从栈pop中拿到的数据也就是同进队时的顺序一样的1，2，3，4，在push栈向pop栈中倒数据时要保证pop栈为空方可倒不然如果pop栈里还有元素4，这时又从push栈中倒数据5，那么这个4就要在5后面出队，这就不符合对的先进先出了；

代码实现

typedef int STDataType;
typedef struct STNode
{STDataType* a;int top;int capacity;
}ST;
void StackInit(ST* st)
{assert(st);st->a = (STDataType*)malloc(sizeof(STDataType)*4);if (st->a == NULL){printf("malloc fail\n");exit(-1);}st->capacity = 4;st->top = 0;
}
//销毁
void StackDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->top = st->capacity = 0;
}
//进栈
void StackPush(ST* st, STDataType x)
{assert(st);if (st->top == st->capacity){STDataType* tmp = (STDataType*)realloc(st->a,st->capacity*2*(sizeof(STDataType) ));if (tmp == NULL){printf("realloc fail\n");exit(-1);}else{st->a = tmp;st->capacity *= 2;}}st->a[st->top] = x;st->top++;
}
//出栈
void StackPop(ST* st)
{assert(st);assert(st->top > 0);st->top--;
}
//判空
bool StackEmpty(ST* st)
{assert(st);return st->top == 0;
}
//获取栈顶元素
STDataType StackTop(ST* st)
{assert(st);assert(st->top > 0);return st->a[st->top-1];
}
//获取栈的大小
int StackSize(ST* st)
{assert(st);return st->top;
}//栈的结构体定义
//先定义两个栈出来
//和用对列实现栈类似typedef struct {//push栈用来模拟入队//pop栈用来模拟出队ST push;ST pop;
} MyQueue;//这里也和用队列实现栈类似
MyQueue* myQueueCreate() {MyQueue*pq = (MyQueue*)malloc(sizeof(MyQueue));if(pq == NULL){perror("malloc fail");return NULL;}StackInit(&pq->push);StackInit(&pq->pop);return pq;
}//队列是先进先出的特殊数据结构
//栈是先进后出，并且在栈顶插入和删除//直接往push中入数据，不用管push是否为空
void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->push,x);
}//导入数据时注意pop栈为空才倒
int myQueuePop(MyQueue* obj) {if(StackEmpty(&obj->pop)){while(!StackEmpty(&obj->push)){StackPush(&obj->pop,StackTop(&obj->push));StackPop(&obj->push);}}int front = StackTop(&obj->pop);StackPop(&obj->pop);return front;
}//每次返回pop栈顶元素就是对头元素
int myQueuePeek(MyQueue* 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) {StackDestory(&obj->pop);StackDestory(&obj->push);free(obj);
}

由于这时用C语言实现的需要自己手写一个栈。

---

队列是一种特殊的数据结构，在后面学习二叉树还会用到，因此还是要将其掌握熟练