凤岗东莞网站建设,wordpress后台速度慢,呼和浩特网站建设设计,商城网站一般用什么做二次开发上一篇写的是栈这一篇分享队列实现及其与队列相关OJ题 文章目录一、队列概念及实现二、队列源码三、leetcode相关OJ一、队列概念及实现
1、队列概念 队列同栈一样也是一种特殊的数据结构#xff0c;遵循先进先出的原则#xff0c;例如#xff1a;想象在独木桥上走着的人遵循先进先出的原则例如想象在独木桥上走着的人先上去的人定是先从独木桥上下来为啥说是特殊呢因为它只允许在对尾插入数据 (简称入队 然后在对头删除数据(简称出队)只允许在这两端进行插入和删除操作 而基于它的特性选择链表实现还是数组实现更好呢 当然选链表实现比较好因为数组在头删除时需要移动大量的数据时间复杂度为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
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.htypedef 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
#includeQueue.hint 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用栈实现队列 思想用两个栈实现一个栈进行入队操作另一个栈进行出队操作 出队操作当出队的栈不为空是直接进行出栈操作如果为空需要把入队的栈元素全部导入到出队的栈然后再进行出栈操作 //由于栈最先进去的数据要最后才能获得 //假设1234是按顺序依次入队那么它的出队顺序也是1234 //要用栈来实现队列那么就要让原来的数据以逆序43 21的方式存储到栈中然后每次出栈顶的数据就可以实现队列的先进先出而一个栈明显行不通这时让一个栈用来实现入队栈push用来模拟入队那么进栈也就是1234将从push栈依次得到的数据倒入pop栈中pop栈中进栈就是4321那么从栈pop中拿到的数据也就是同进队时的顺序一样的1234在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语言实现的需要自己手写一个栈。 队列是一种特殊的数据结构在后面学习二叉树还会用到因此还是要将其掌握熟练
