网站导航
> 文档中心 > 队列（详解）——手撕队列习题

队列（详解）——手撕队列习题

网友: 文档中心 2022-04-25 23:25:08

队列

  • 队列的简单介绍
  • Queue.h
    • Queue.c
      • Test.c
      • 习题：
  • 用队列实现栈
    • 用栈实现队列
      • 设计循环队列

队列的简单介绍

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
在这里插入图片描述
队列的实现，其实和栈差不多，数组和链表都可以实现，但是由于队列的特殊性，先进先出的这种特性，当我们用数组的时候，出队的时候时间复杂度会一直是O（n），在这里插入图片描述
我们用单链表实现的话
在这里插入图片描述
@[TOC](

Queue.h

#define _CRT_SECURE_NO_WARNING#pragma once #include#include#include#includetypedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QueueNode;typedef struct Queue{QueueNode* front;QueueNode* rear;}Queue;void QueueInit(Queue* ps);//队列的初始化void QueueDestory(Queue* ps);//队列的销毁void QueuePush(Queue* ps,QDataType x);//入队void QueuePop(Queue* ps);//出队bool QueueEmpty(Queue* ps);//判断队列是否为空size_t QueueSize(Queue* ps);//返回队列中元素的个数QDataType QueueFront(Queue* ps);//返回队头元素QDataType QueueRear(Queue* ps);//返回队尾元素

Queue.c

 #define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"void QueueInit(Queue* ps)//队列的初始化{    assert(ps);//如果储存指针的地址都为空的话，肯定是错误的    //刚开始的头指针与尾指针肯定是相等的，并且都是NULL    ps->front = ps->rear = NULL;    }void QueueDestory(Queue* ps)//队列的销毁{    assert(ps);    QueueNode* cur = ps->front;    while (cur)    { QueueNode* ret = cur->next; free(cur); cur = ret;    }    ps->front = ps->rear = NULL;}void QueuePush(Queue* ps, QDataType x)//入队{    assert(ps);//入队肯定是与尾指针rear有关的 先申请一个空间    QueueNode* cur = (QueueNode*)malloc(sizeof(QueueNode));    if (cur == NULL)    { printf("malloc fail\n"); exit(-1);    }    cur->data = x;    cur->next = NULL;   /* QueueNode* ret = ps->rear->next;    ps->rear = cur;这样写的话很有问题，没有判断当两个指针都为空指针的情况    ps->rear = ret;*/    if (ps->rear == NULL)    { assert(ps->front == NULL);//当尾指针为空的时候，头指针不可能不为空 ps->front = ps->rear = cur;    }    else    { ps->rear->next = cur; ps->rear = cur;     }}void QueuePop(Queue* ps)//出队{ assert(ps);//出队也是头删    assert(ps->front != NULL);//如果头指针为空的话肯定是错误的    //队列中只有一个结点    if (ps->front == ps->rear) ps->front = ps->rear = NULL;    else    { //ps->front = ps->front->next;这样写的话涉及到内存泄露 QueueNode* ret = ps->front->next; free(ps->front); ps->front = ret;//这样写的话就不会涉及到什么内存泄露啦    }}bool QueueEmpty(Queue* ps)//判断队列是否为空{    assert(ps);    //当头指针为空的时候，队列就是空的    return ps->front == NULL;}size_t QueueSize(Queue* ps)//返回队列中元素的个数{    assert(ps);    int sum = 0;    QueueNode* cur = ps->front;    while (cur)    { sum++; cur = cur->next;    }    return sum;}QDataType QueueFront(Queue* ps)//返回队头元素{    assert(ps);    assert(ps->front != NULL);    return ps->front->data;}QDataType QueueRear(Queue* ps)//返回队尾元素{    assert(ps);    assert(ps->rear != NULL);    return ps->rear->data;}

Test.c

 #define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"int main(){Queue st;QueueInit(&st);QueuePush(&st, 1);QueuePush(&st, 2323);QueuePush(&st, 86);QueuePush(&st, 567);QueuePush(&st, 999);QueuePush(&st, 666);//printf("%d", QueueSize(&st));while (!QueueEmpty(&st)){printf("%-7d", QueueFront(&st));printf("%-7d", QueueRear(&st));printf("%d\n", QueueSize(&st));QueuePop(&st);}return 0;}

习题：

用队列实现栈

队列（详解）——手撕队列习题

用队列实现栈

在这里插入图片描述
在这里插入图片描述

上面就是这道题的思路了，有一说一，C语言实现这个实在是麻烦，但是我们现在用C语言写还是可以加深一下对这个结构的感觉的

typedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QueueNode;typedef struct Queue{QueueNode* front;QueueNode* rear;}Queue;void QueueInit(Queue* ps)//队列的初始化{    assert(ps);//如果储存指针的地址都为空的话，肯定是错误的    //刚开始的头指针与尾指针肯定是相等的，并且都是NULL    ps->front = ps->rear = NULL;    }void QueueDestory(Queue* ps)//队列的销毁{    assert(ps);    QueueNode* cur = ps->front;    while (cur)    { QueueNode* ret = cur->next; free(cur); cur = ret;    }    ps->front = ps->rear = NULL;}void QueuePush(Queue* ps, QDataType x)//入队{    assert(ps);//入队肯定是与尾指针rear有关的 先申请一个空间    QueueNode* cur = (QueueNode*)malloc(sizeof(QueueNode));    if (cur == NULL)    { printf("malloc fail\n"); exit(-1);    }    cur->data = x;    cur->next = NULL;   /* QueueNode* ret = ps->rear->next;    ps->rear = cur;这样写的话很有问题，没有判断当两个指针都为空指针的情况    ps->rear = ret;*/    if (ps->rear == NULL)    { assert(ps->front == NULL);//当尾指针为空的时候，头指针不可能不为空 ps->front = ps->rear = cur;    }    else    { ps->rear->next = cur; ps->rear = cur;     }}void QueuePop(Queue* ps)//出队{ assert(ps);//出队也是头删    assert(ps->front&&ps->rear);//如果头指针为空的话肯定是错误的    //队列中只有一个结点  if (ps->front->next == NULL){free(ps->front);ps->front = ps->rear = NULL; }     else    { //ps->front = ps->front->next;这样写的话涉及到内存泄露 QueueNode* ret = ps->front->next; free(ps->front); ps->front = ret;//这样写的话就不会涉及到什么内存泄露啦    }}bool QueueEmpty(Queue* ps)//判断队列是否为空{    assert(ps);    //当头指针为空的时候，队列就是空的    return ps->front == NULL;}size_t QueueSize(Queue* ps)//返回队列中元素的个数{    assert(ps);    int sum = 0;    QueueNode* cur = ps->front;    while (cur)    { sum++; cur = cur->next;    }    return sum;}QDataType QueueFront(Queue* ps)//返回队头元素{    assert(ps);    assert(ps->front != NULL);    return ps->front->data;}QDataType QueueRear(Queue* ps)//返回队尾元素{    assert(ps);    assert(ps->rear != NULL);    return ps->rear->data;}typedef struct {    Queue st1;    Queue st2;} MyStack;MyStack* myStackCreate() {   MyStack*obj = (MyStack*)malloc(sizeof(MyStack));     assert(obj);     QueueInit(&(obj->st1));     QueueInit(&(obj->st2));//这边一定不能忘记初始化     return obj;}void myStackPush(MyStack* obj, int x) {  assert(obj); // if(obj->st1->front==NULL) obj->st1是一个队列，不是指针 if(QueueEmpty(&(obj->st1)))  {      QueuePush(&(obj->st2),x);  }  else  {      QueuePush(&(obj->st1),x);  }}int myStackPop(MyStack* obj) {     assert(obj);    //这部分是一个小技巧，通过一个简单的操作使得无论哪个队列为空，我们需要操作的都是    //一样的 避免了代码的重复性     Queue*noEmpty = &(obj->st1);   Queue*Empty = &(obj->st2);   if(QueueEmpty(&obj->st1))//题目要注意的是传进去的都是地址，千万不要忘记取地址了   {noEmpty = &(obj->st2);Empty = &(obj->st1);   }    while(QueueSize(noEmpty)>1)    { QueuePush(Empty,QueueFront(noEmpty)); QueuePop(noEmpty);    }    int ret = QueueFront(noEmpty);    QueuePop(noEmpty);    return ret;      }int myStackTop(MyStack* obj) {    assert(obj);   if(QueueEmpty(&(obj->st1)))    { return QueueRear(&(obj->st2));    }    else     return QueueRear(&(obj->st1));}bool myStackEmpty(MyStack* obj) {      assert(obj);      return QueueEmpty(&(obj->st1))&&QueueEmpty(&(obj->st2));      }void myStackFree(MyStack* obj) {assert(obj);      QueueDestory(&(obj->st2)); QueueEmpty(&(obj->st1));  free(obj); }

用栈实现队列

坚持就是胜利！

队列（详解）——手撕队列习题

用栈实现队列

在这里插入图片描述

在这里插入图片描述在这里插入图片描述

**注意：**一定得保持一个栈始终有数字，另外一个栈始终没有数字，这样写代码的时候方便很多！

typedef int STDataType;typedef struct Stack{STDataType* a;int top;//栈顶的位置int capacity;//容量}ST;void StackInit(ST* ps)//栈的初始化{ assert(ps);//栈可以为空，但是储存栈的结构体不可能是空的ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackDestory(ST* ps)//栈的销毁{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;}void StackPush(ST* ps, STDataType x)//压栈{assert(ps);//压栈之前要检查一下栈是否满 因为我们的top始终是位于栈顶的下一个位置//所以当top的值等于capacity的时候栈就满了或者是一开始栈空的情况if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  ps->a = (ST*)realloc(ps->a, sizeof(ST) * newCapacity);//在原来的基础上扩容，所以用reallocif (ps->a == NULL){printf("malloc fail\n");exit(-1);}ps->capacity = newCapacity;}//压栈ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps)//出栈{assert(ps);//出栈之前要考虑一下栈是否为空，空的话就不用出栈了 所以还需要一个断言assert(ps->top > 0);ps->top--;//因为我们打印的时候是从头开始遍历的，只会遍历到top所以只需要top--}bool StackEmpty(ST* ps)//检测栈是否为空{assert(ps);//如果top = 0的时候就是栈空 所以return ps->top == 0;}int StackSize(ST* ps)//返回栈中元素的个数{assert(ps);return ps->top;}STDataType StackTop(ST* ps)//返回栈顶的元素{assert(ps);//同时这里要确保栈中不为空assert(ps->top > 0);return ps->a[ps->top - 1];}typedef struct {    ST s1;    ST s2;} MyQueue;MyQueue* myQueueCreate() { MyQueue*cur = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&cur->s1); StackInit(&cur->s2); return cur;}//始终保持s1有数字void myQueuePush(MyQueue* obj, int x) {     assert(obj);     StackPush(&obj->s1,x);}int myQueuePop(MyQueue* obj) {     assert(obj);     while(StackSize(&obj->s1)>1)     {  StackPush(&obj->s2,StackTop(&obj->s1));  StackPop(&obj->s1);     }     int ret = StackTop(&obj->s1);     StackPop(&obj->s1);      while(StackSize(&obj->s2)>0)     {  StackPush(&obj->s1,StackTop(&obj->s2));  StackPop(&obj->s2);     }     return ret;}int myQueuePeek(MyQueue* obj) {    assert(obj);    ST*cur = &obj->s1;    return cur->a[0];//队列的开头也就是栈底 栈底也就是a[0];}bool myQueueEmpty(MyQueue* obj) {    assert(obj);      return StackEmpty(&obj->s1);}void myQueueFree(MyQueue* obj) {     assert(obj);     StackDestory(&obj->s1);//摧毁的时候一定要分别free，因为free只会消除其指向的//空间     StackDestory(&obj->s2);     free(obj);}/** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x);  * int param_2 = myQueuePop(obj);  * int param_3 = myQueuePeek(obj);  * bool param_4 = myQueueEmpty(obj);  * myQueueFree(obj);*/

设计循环队列

最后一题啦！
队列（详解）——手撕队列习题

循环队列

在这里插入图片描述

我们先看下循环队列大致是怎样的，然后思考一下我们怎样去实现它

在这里插入图片描述
可以看出 用数组或者是循环单链表都是可以的，但是单链表要考虑的东西有点多，我在这就用数组实现一下

typedef struct {    int *a;    int front;    int rear;    int k;//表示循环队列的长度为k但是有效长度为k-1 因为rear+1==front是判断队列满的条件} MyCircularQueue;bool myCircularQueueIsFull(MyCircularQueue* obj);bool myCircularQueueIsEmpty(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {   MyCircularQueue*cur = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));   cur->a = (int*)malloc(sizeof(int)*(k+1));   cur->front = 0;   cur->rear = 0;//我们代码设置的是rear初始值虽然是0   //但是随着数据入队列，rear始终在最后一个数字的下一位，同时为了方便   //判断队列空和满，我们必须留一个位置 //同时rear与front的值我们必须//记住取模   cur->k = k+1; return cur;   }bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {     assert(obj);//入队之前要判断一下队是否满了     if(myCircularQueueIsFull(obj))     return false;     else     {   obj->a[obj->rear] = value;   obj->rear = (obj->rear+1)%(obj->k);   return true;  }    }bool myCircularQueueDeQueue(MyCircularQueue* obj) {    assert(obj);    //需要判断队列是否为空    if(myCircularQueueIsEmpty(obj))    return false;    else    { obj->front = (obj->front+1)%(obj->k); 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->rear == 0) return obj->a[obj->k-1];    return obj->a[obj->rear - 1];//这边要注意一下 当这个rear值为0的时候呢？    //此时-1的话就会造成越界访问，所以应该加上第二个判定条件}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);return obj->front==obj->rear;}bool myCircularQueueIsFull(MyCircularQueue* obj) {   assert(obj);    return ((obj->rear+1)%(obj->k))==obj->front;}void myCircularQueueFree(MyCircularQueue* obj) {      assert(obj);      free(obj->a);      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);*/
网络标签：

相关问题