【数据结构】队列

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低

话不多说，我们直接来实现队列：(一定要记得自己去实现一个队列)

1.队列的结构

队列的初始化是比较简单的：由单链表构成，一个结构体为队列的结点，但是只有一个指针，我们需要队头和队尾，方便队头删除，队尾插入(所以不需要前面那些什么头删、尾删，队列中队头是用来删除的，队尾是用来插入的)所以另一个结构体为队列的头、尾指针

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

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13

在这个地方，这里有两个结构体哦，我们不需要二级指针：

我们只需要改结构体（只需要改变结构体里面的head和tail），我们只需要结构体的指针(一级指针)即可

2.初始化

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6

3.销毁

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	pq->head = pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

4.入队

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
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

5.判断是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}
1
2
3
4
5

6.出队

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;

		free(del);
		del = NULL;
	}
	pq->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7.队头元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
1
2
3
4
5
6

8.队尾元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
1
2
3
4
5
6

9.元素个数

QDataType QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	/*int n = 0;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
	return n;*/
	return pq->size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

完整代码

Queue.h

#pragma once

#include 
#include 
#include 
#include 


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

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);

void QueueDestroy(Queue* pq);

void QueuePush(Queue* pq,QDataType x);

void QueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);

QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);

QDataType QueueSize(Queue* pq);
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

Queue.c

#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;

		free(del);
		del = NULL;
	}
	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

QDataType QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	/*int n = 0;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
	return n;*/
	return pq->size;
}
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

test.c

//test.c部分这里只是对上面的部分函数进行测试，如果有需要的话也可以自己设计成菜单界面

#include "Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
    QueueDestroy(&q);
}
int main()
{
	TestQueue();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

对于队列的实现并不难，下面，我们就来做几道有关队列的OJ题目把👇

队列OJ题

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

题目的意思其实很简单：就是让你用两个队列去模拟实现一个栈

思路：思路其实很简单，我们知道队列是先进先出，而栈是后进先出，两个最大的不同在于顺序：

我们假设在队列入了1，2，3，4那么现在要在队列中出一个元素，那就是1
如果在栈中入了1，2，3，4那么现在要在栈中出一个元素，那就是4

我们该怎么改变这种顺序呢？很简单，让有元素队列把前n-1个导入到空的队列，此时取出剩下的元素就是符合栈顺序的元素，我们不妨来画个图：

取出4之后,q1又变成了空队列。继续倒

这道题的思路不难，但是实现起来比较麻烦，可能做的时候多多少少有有一些细节没注意到，导致编译出现错误，不过问题不是很大。话不多说直接搬上我们的代码：

#include 
#include 
#include 
//直接手撸一个队列
typedef int QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode*next;
}QNode;
typedef struct Queue{
    QNode*head;
    QNode*tail;
    int size;
}Queue;

void QueueInit(Queue*pq);
void QueueDestroy(Queue*pq);
void QueuePush(Queue*pq,QDataType x);
void QueuePop(Queue*pq);
QDataType QueueFront(Queue*pq);
QDataType QueueBack(Queue*pq);
bool QueueEmpty(Queue*pq);
QDataType QueueSize(Queue*pq);


void QueueInit(Queue*pq)
{
    assert(pq);
    pq->head = pq->tail =  NULL;
    pq->size = 0;
}
void QueueDestroy(Queue*pq)
{
    assert(pq);
    QNode*cur = pq->head;
    while(cur)
    {
        QNode*del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = pq->tail = NULL;
}
void QueuePush(Queue*pq,QDataType x)
{
    assert(pq);
    QNode*newnode = (QNode*)malloc(sizeof(QNode));
    if(NULL == newnode)
    {
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    if(pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
       pq->tail->next = newnode;
       pq->tail = newnode;
    }
    pq->size++;
}
void QueuePop(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if(pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode*del = pq->head;
        pq->head = pq->head->next;
        free(del);
        del = NULL;
    }
    pq->size--;
}
QDataType QueueFront(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}
QDataType QueueBack(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}
bool QueueEmpty(Queue*pq)
{
    assert(pq);
    return pq->head == NULL&&pq->tail == NULL;
}
QDataType QueueSize(Queue*pq)
{
    return pq->size;
}

//定义了两个队列，一个为q1,另一个为q2
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
    if(NULL == obj)
    {
        exit(-1);
    }
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    //看哪个是否为空
    if(!QueueEmpty(&obj->q1))
    {
        //谁不为空就插入数据
        QueuePush(&obj->q1,x);
    }
    //q2可能为空或不为空
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //删除栈顶的元素，先找出那个不为空的队列，在把数据导入
    Queue*empty = &obj->q1;
    Queue*nonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    //剩下一个元素
    while(QueueSize(nonEmpty)>1)
    {
        //取队头数据存放到空的队列,最后剩下一个，这个就是栈顶的元素
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

int myStackTop(MyStack* obj) {
    //取栈的头相当于非空的队列的队尾
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

一个队列实现栈

还是上面那道题，我们用一个队列来试一试：

#include 
#include 
#include 

typedef int QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode*next;
}QNode;
typedef struct Queue{
    QNode*head;
    QNode*tail;
    int size;
}Queue;

void QueueInit(Queue*pq);
void QueueDestroy(Queue*pq);
void QueuePush(Queue*pq,QDataType x);
void QueuePop(Queue*pq);
QDataType QueueFront(Queue*pq);
QDataType QueueBack(Queue*pq);
bool QueueEmpty(Queue*pq);
QDataType QueueSize(Queue*pq);


void QueueInit(Queue*pq)
{
    assert(pq);
    pq->head = pq->tail =  NULL;
    pq->size = 0;
}
void QueueDestroy(Queue*pq)
{
    assert(pq);
    QNode*cur = pq->head;
    while(cur)
    {
        QNode*del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = pq->tail = NULL;
}
void QueuePush(Queue*pq,QDataType x)
{
    assert(pq);
    QNode*newnode = (QNode*)malloc(sizeof(QNode));
    if(NULL == newnode)
    {
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    if(pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
       pq->tail->next = newnode;
       pq->tail = newnode;
    }
    pq->size++;
}
void QueuePop(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if(pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode*del = pq->head;
        pq->head = pq->head->next;
        free(del);
        del = NULL;
    }
    pq->size--;
}
QDataType QueueFront(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}
QDataType QueueBack(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}
bool QueueEmpty(Queue*pq)
{
    assert(pq);
    return pq->head == NULL&&pq->tail == NULL;
}
QDataType QueueSize(Queue*pq)
{
    return pq->size;
}

//一个队列
typedef struct {
    Queue q;
} MyStack;


MyStack* myStackCreate() {
   MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
   QueueInit(&obj->q);
   return obj;
}

void myStackPush(MyStack* obj, int x) {
    //先让数据入队
    QueuePush(&obj->q,x);
    int i = 0;
    //1个元素就不用处理
    while(i<QueueSize(&obj->q)-1)
    {
        int front = QueueFront(&obj->q);
        QueuePop(&obj->q);
        QueuePush(&obj->q,front);
        i++;
    }
}

int myStackPop(MyStack* obj) {
   int tmp = QueueFront(&obj->q);
   QueuePop(&obj->q);
   return tmp; 
}

int myStackTop(MyStack* obj) {
   return QueueFront(&obj->q);
}

bool myStackEmpty(MyStack* obj) {
   return QueueEmpty(&obj->q);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q);
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

这道题和上面的那道题是相反的，这里要让你用两个栈去实现队列，思路也是差不多的，但是对于两个栈来说，就存在一些差别了：我们还是以入栈1、2、3、4来举例子：

所以两个栈我们可以一个为PopST进行出数据的操作，出空了，再去另一个栈PushST将数据倒过来，仔细琢磨琢磨

废话不多说：

#include 
#include 
#include 
#include 

//手撸一个栈
typedef int STDataType;
typedef struct Stack
{
	STDataType*a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);

void StackDestory(ST* ps);

void StackPush(ST* ps,STDataType x);

void StackPop(ST* ps);

STDataType StackTop(ST* ps);

bool StackEmpty(ST*ps);

int StackSize(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (NULL == tmp)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
	
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue *obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushST);
    StackInit(&obj->popST);
    return obj;
}

//入队
void myQueuePush(MyQueue* obj, int x) {
    //有数据就直接进入PushST栈
    StackPush(&obj->pushST,x);
}

void pushSTtopopST(MyQueue*obj)
{
    //先把popST栈的数据给出栈,如果没有数据就让pushST栈的数据进入
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
}
//出队
int myQueuePop(MyQueue* obj) {
    pushSTtopopST(obj);
    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return front;
}
//取队头元素
int myQueuePeek(MyQueue* obj) {
    pushSTtopopST(obj);
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->popST);
    StackDestory(&obj->pushST);
}

/**
 * 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);
*/
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

循环队列没啥好说的（关键在于取模问题）。而且学校的考试题很喜欢考循环队列这一块，我们不妨来看一道选择题：

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据，假设多给一个空间，实际空间大小为N)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)

解析：答案选B.

下面我们来看一看上面的题目：

对于结构体的定义：我们需要一个数组存放数据，同时还有队头和队尾，以及空间的大小。

我们来区分一下如何判断是否为空和是否为满的情况：

空的时候，队头==队尾

满的时候，(队尾+1)%空间的大小==队头。后面一些细节的东西，我们直接来看代码：

对于这道题给的函数有一点坑：

我们去调用bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);都要去先进行函数的声明，这两个函数是放在下面，或者我们直接把这两个函数提前也可.

typedef struct {
    int*a;
    int front;
    int back;
    int N;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//记得要函数声明
bool myCircularQueueIsFull(MyCircularQueue* obj);//记得函数声明
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多一个空间
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->back = 0;
    obj->N = k+1;
    return obj;
}
//入队——往尾部入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        obj->a[obj->back] = value;
        obj->back++;
       //到尾
        obj->back %= obj->N;
        return true;
    }
}
//出队——头部出数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    //到尾
    obj->front %= obj->N;
    return true;

}
//队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
    return obj->a[obj->front];
    }
}
//队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
     if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //处理当obj->back = 0的时候
    else
    {
        return obj->a[(obj->back-1+obj->N)%obj->N];
    }
}
//判断是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->back;
}
//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //处理一下
    return (obj->back+1)%obj->N==obj->front;
}
//释放
void myCircularQueueFree(MyCircularQueue* 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);
*/
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

---