C++--手动实现循环队列（数组+链表）

力扣：622 循环队列

1.数组

class MyCircularQueue {
private:
    vector<int> data;
    int capacity;//最大容量
    int front;
    int rear;//队尾元素的下一个位置
public:
    MyCircularQueue(int k) {
        this->data=vector<int>(k+1);//牺牲一个单元用来判满
        this->capacity=k+1;
        this->front=0;
        this->rear=0;
    }    
    bool enQueue(int value) {//入队
        //先判满
        if(isFull())
        {
            return false;
        }
        data[rear]=value;
        rear=(rear+1)%capacity;
        return true;
    }
    bool deQueue() {//出队
        //先判空
        if(isEmpty())
        {
            return false;
        }
        front=(front+1)%capacity;
        return true;
    }
    int Front() {//队头元素
        //先判空
        if(isEmpty())
        {
            return -1;
        }
        return data[front];
    }
    int Rear() {//队尾元素
        //先判空
        if(isEmpty())
        {
            return -1;
        }
        return data[(rear-1+capacity)%capacity];//注意这里 当rear到front前面时，比如=0时，就需要这样处理
    }
    bool isEmpty() {//判空
        if(front==rear)
        {
            return true;
        }
        return false;
    }
    
    bool isFull() {//判满
        if((rear+1)%capacity==front)
        {
            return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

2.单链表（无头节点和有头节点）

1. 无头节点

class MyCircularQueue {//2，单链表（无头结点）
private:
    ListNode* front;//指向头节点
    ListNode* rear;//指向尾结点
    int capacity;//最大容量
    int size;//元素个数
public:
    MyCircularQueue(int k) {//初始化
        this->front=this->rear=nullptr;//无头节点
        this->capacity=k;
        this->size=0;
    }
    
    bool enQueue(int value) {//入队--尾插
        //判满
        if(isFull())
        {
            return false;
        }
        ListNode* cur=new ListNode(value);
        cur->val=value;
        if(front==nullptr)//第一次插入
        {
            front=cur;
            rear=cur;
        }
        else//不是第一次插入
        {
            rear->next=cur;
            rear=cur;
        }
        size++;
        return true;
    }
    
    bool deQueue() {//出队
        //判空
        if(isEmpty())
        {
            return false;
        }
        front=front->next;
        size--;
        return true;
    }
    
    int Front() {//队头
        if(isEmpty())
        {
            return -1;
        }
        return front->val;
    }
    
    int Rear() {//队尾
        if(isEmpty())
        {
            return -1;
        }
        return rear->val;
    }
    
    bool isEmpty() {//判空
        if(size==0)
        {
            return true;
        }
        return false;
    }
    
    bool isFull() {//判满
        if(size==capacity)
        {
            return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

2. 有头节点

class MyCircularQueue {
private:
    ListNode* front;//指向头节点
    ListNode* rear;//指向尾结点
    int capacity;//最大容量
    int size;//元素个数
public:
    MyCircularQueue(int k) {//初始化
        this->front=this->rear=(ListNode*)malloc(sizeof(ListNode));//头节点
        this->capacity=k;
        this->size=0;
    }
    bool enQueue(int value) {//入队--尾插
        //判满
        if(isFull())
        {
            return false;
        }
        ListNode* cur=new ListNode(value);
        cur->val=value;
        rear->next=cur;
        rear=cur;
        size++;
        return true;
    }
    bool deQueue() {//出队
        //判空
        if(isEmpty())
        {
            return false;
        }
        if(rear==front->next)//判断是否是删除最后一个结点
        {
            rear=front;
        }
        else
        {
            front->next=front->next->next;
        }
        size--;
        return true;
    } 
    int Front() {//队头
        if(isEmpty())
        {
            return -1;
        }
        return front->next->val;
    }
    int Rear() {//队尾
        if(isEmpty())
        {
            return -1;
        }
        return rear->val;
    }
    bool isEmpty() {//判空
        if(size==0)
        {
            return true;
        }
        return false;
    }
    bool isFull() {//判满
        if(size==capacity)
        {
            return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71