队列小哥哥喊你来排队了~(自带循环的那种)

2024-02-22 11:08:04

大家好，我是melo，一名大二上软件工程在读生，经历了一年的摸滚，现在已经在工作室里边准备开发后台项目啦。
不过这篇文章呢，还是想跟大家聊一聊数据结构与算法，学校也是大二上才开设了数据结构这门课，希望可以一边学习数据结构一边积累后台项目开发经验。
前几篇,我们已经接触了两个数据结构：链表和栈，这篇的主角呢，其实跟栈有点相似，队列小哥哥也一样需要我们掌握，这篇带你来认识认识!

普通队列

队列小哥哥喊你来排队了~(自带循环的那种)

先进先出(两端操作)

只能在头部出队,尾部入队

队列小哥哥喊你来排队了~(自带循环的那种)

c语言版

typedef struct {
    int front;
    int rear;
    int capacity;
    int* queue;
} MyCircularQueue;

//需要先声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

//创建队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* CircularQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CircularQueue->front=0;
    CircularQueue->rear=0;
    CircularQueue->queue=(int*)malloc( k * sizeof(int));;
    CircularQueue->capacity=k;
    return CircularQueue;
}

//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)){
         return false;
    }
    obj->queue[obj->rear]=value;
    //移动rear
    obj->rear=obj->rear+1;
    return true;
}

//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    //移动front
    obj->front= obj->front+1;
    return true;
}

//得到第一个元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    return obj->queue[obj->front];
}

//得到最后一个元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    return obj->queue[(obj->rear)-1];
}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front==obj->rear){
        return true;
    }
    return false;
}

//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //若rear==最大容量了(因为我们数组计数是从0开始)
    if((obj->rear)== (obj->capacity)){
        return true;
    }
    return false;
}

循环队列

这里用了两种思路来实现

1.rear是尾部的下一个,且会留一个空位

注意数组要开大一位,因为我们的特殊设计

注意isFull

return (rear + 1) % capacity == front;

java版

public class MyCircularQueue {

    private int front;
    private int rear;
    private int capacity;
    private int[] arr;

    /**
     * Initialize your data structure here. Set the size of the queue to be k.
     */
    public MyCircularQueue(int k) {
        capacity = k + 1;
        arr = new int[capacity];

        // 在 front 出队，故设计在数组的头部，方便删除元素
        // 删除元素的时候，只索引 +1（注意取模）

        // 在 rear 入队，故设计在数组的尾部，方便插入元素
        // 插入元素的时候，先赋值，后索引 +1（注意取模）
        front = 0;
        rear = 0;
    }

    /**
     * 入队
     */
    public boolean enQueue(int value) {
        //先判断是否满了
        if (isFull()) {
            return false;
        }
        arr[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    /**
     * 出队
     */
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    /**
     * 得到第一个元素(不弹出)
     */
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return arr[front];
    }

    /**
     * 得到最后一个元素(不弹出)
     */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return arr[(rear - 1 + capacity) % capacity];
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * 判断是否满了
     */
    public boolean isFull() {
        // 注意：我们这里设计好了,只剩下一个位置的时候就是满了
        //且rear是指向最后一个元素的下一位
        return (rear + 1) % capacity == front;
    }
}

c语言版

  • 注意函数用到另一个函数的时候,如果在下边需要先声明

注意结构体内部声明一个动态数组时,需要声明成int* queue(数组指针)

然后Creat的时候去malloc

CircularQueue->queue=(int*)malloc( (k+1) * sizeof(int));;

typedef struct {
    int front;
    int rear;
    int capacity;
    int* queue;
} MyCircularQueue;

//需要先声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

//创建队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* CircularQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CircularQueue->front=0;
    CircularQueue->rear=0;
    CircularQueue->queue=(int*)malloc( (k+1) * sizeof(int));;
    CircularQueue->capacity=k+1;
    return CircularQueue;
}

//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)){
         return false;
    }
    obj->queue[obj->rear]=value;
    //移动rear,注意取模
    obj->rear=(obj->rear+1)%(obj->capacity);
    return true;
}

//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    //移动front,注意取模
    obj->front=(obj->front+1)%obj->capacity;
     return true;
}

//得到第一个元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    return obj->queue[obj->front];
}

//得到最后一个元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    return obj->queue[(obj->rear-1+obj->capacity)%obj->capacity];
}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front==obj->rear){
        return true;
    }
    return false;
}

//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear+1)%obj->capacity==obj->front){
        return true;
    }
    return false;
}

队列满的条件以及队列的长度

可能相差一圈,就要联想到去取模这个一圈的长度

队列小哥哥喊你来排队了~(自带循环的那种)

***队列长度(我的版本)

rear小于front: rear-front+QueueSize

rear大于front: rear-front

  • 既然如此,可以拿rear-front+QueueSize去模QueueSize,
    • 若rear-front小于0,那结果就是rear-front+QueueSize
    • 若大于0,就只剩下rear-front

2.tag标志位来标志是空了还是满了

如果我们不采用第一种方法(多留一个空位的话)

其实会发现我们判空和判满都是同一个条件: rear==front

这样我们就没有办法区分开两种情况了

所以我们用另一个tag标志位来标志是空了还是满了

队列小哥哥喊你来排队了~(自带循环的那种)

单纯根据tag来判断是满还是空(错误版本)

这样是错的,因为初始化tag就是0了,一直入队没满他也还是0,总是以为是空队列

#include "allinclude.h"  //DO NOT edit this line
//入队
Status EnCQueue(CTagQueue &Q, ElemType x) { 
    // Add your code here
    //若满了
    if(Q.tag==1) return ERROR;
    Q.elem[Q.rear]=x;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    //加完后满了
    if(Q.rear==Q.front) Q.tag=1;
    return OK;
}

//出队
Status DeCQueue(CTagQueue &Q, ElemType &x){
   // Add your code here
   //若空
  if(Q.tag==0) return ERROR;
  x=Q.elem[Q.front];
  Q.front=(Q.front+1)%MAXQSIZE;
  //若出队完空了
  if(Q.rear==Q.front) Q.tag=0;
  return OK;
}

判断rear==front以及判断tag (正解)

#include "allinclude.h"  //DO NOT edit this line
//入队
Status EnCQueue(CTagQueue &Q, ElemType x) { 
    // Add your code here
    //若满了
    if(Q.tag==1&&Q.rear==Q.front) return ERROR;
    Q.elem[Q.rear]=x;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    //加完后满了
    if(Q.rear==Q.front) Q.tag=1;
    return OK;
}

//出队
Status DeCQueue(CTagQueue &Q, ElemType &x){
   // Add your code here
   //若空
  if(Q.tag==0&&Q.rear==Q.front) return ERROR;
  x=Q.elem[Q.front];
  Q.front=(Q.front+1)%MAXQSIZE;
  //若出队完空了
  if(Q.rear==Q.front) Q.tag=0;
  return OK;
}

写在最后

  • 其实这一块知识学了蛮久了,当时没有把链队列的一并整理进来,等以后期末复习有需要的时候,会回来整理的!!!(立个flag!)
上一篇：数据结构学习日记（六）


下一篇：【实验一】二分查找