【数据结构】队列和栈

大家中秋节快乐，玩了好几天没有学习，今天分享的是栈以及队列的相关知识，以及栈和队列相关的面试题

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

栈的接口函数

// 初始化栈
voidStackInit(Stack*ps); 
// 入栈
voidStackPush(Stack*ps, STDataTypedata); 
// 出栈
voidStackPop(Stack*ps); 
// 获取栈顶元素
STDataTypeStackTop(Stack*ps); 
// 获取栈中有效元素个数
intStackSize(Stack*ps); 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack*ps); 
// 销毁栈
voidStackDestroy(Stack*ps); 
1
2
3
4
5
6
7
8
9
10
11
12
13

栈的实现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef struct Stack//定义一个栈的结构体变量	
{
	int * a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);//断言，防止为空指针
	ps->a = NULL;//所指向的地址为空
	ps->capacity = ps->top = 0;//容量和栈中元素个数均为0
}
void StackPush(Stack* ps, int data)
{
	assert(ps);
	if (ps->capacity == ps->top)//如果栈中的元素个数等于栈的容量时考虑扩容，
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果刚开始时都等于0，就先给4个空间大小，后面如果满的话，容量扩大1倍
		 int* newnode = (int*)realloc(ps->a,sizeof(int)* newcapcity);//申请空间，将申请好的空间首地址传给newnode指针
		 assert(newnode);//断言，防止malloc失败
		 ps->a = newnode;//将newnode保存的申请空间的首地址传给ps->a,让ps->a指向创建好的空间
		ps->capacity = newcapcity;//容量大小更新为新容量大小



	}
	ps->a[ps->top] = data;//像存数组一样存数据
	ps->top++;//指向下一个
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top ==0;//ps->top为栈中元素个数.==0栈中无元素，无元素要返回1， 无元素ps->t0p==0，这个表达式结果是1，返回1;





}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止栈内无元素，继续出栈
	ps->top--;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//ps->top为栈中元素个数，由于数组下标是从0开始，所以栈顶元素下标为ps->top-1;

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;

}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//free掉动态申请的内存
	ps->a = NULL;//防止野指针
	ps->capacity = ps->top = 0;//容量和栈中元素个数置为0



}
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

栈的功能测试

int main()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d",  StackTop(&st));
		StackPop(&st);


	}



	StackDestroy(&st);


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

实现了栈的后入先出

2.队列

2.1队列的概念及结构

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

队列的实现

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

队列的接口函数

// 初始化队列
voidQueueInit(Queue*q); 
// 队尾入队列
voidQueuePush(Queue*q, QDataTypedata); 
// 队头出队列
voidQueuePop(Queue*q); 
// 获取队列头部元素
QDataTypeQueueFront(Queue*q); 
// 获取队列队尾元素
QDataTypeQueueBack(Queue*q); 
// 获取队列中有效元素个数
intQueueSize(Queue*q); 
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 intQueueEmpty(Queue*q); 
// 销毁队列
voidQueueDestroy(Queue*q);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

队列的实现

typedef struct QListNode
{
	struct QListNode* next;//保存结点的下一个结点的地址
	int  data;//该节点的数据
}QNode;
typedef struct Queue
{
 QNode* front;
 QNode* tail;
}Queue;//定义一个队列结构体，指向队列的前结点和尾结点
// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->tail = NULL;//头节点尾结点置为NULL

}
// 队尾入队列
void QueuePush(Queue* q, int data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//新结点申请空间
	assert(newnode);//防止申请失败
	newnode->next = NULL;//新节点的下一个结点的地址为空，不保存
	newnode->data = data;//新结点的数据
	if (q->front == NULL)//没有一个结点
	{
		q->front = q->tail = newnode;//就让指向头节点和指向尾结点的指针指向新结点

	}
	else//有结点
	{
		q->tail->next = newnode;//新结点尾插到后面
		q->tail = newnode;//移动指向尾结点的指针到队列末尾结点，也就是新结点



	}





}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	return q->front == NULL;//如果没有结点,则q->front==NULL,表达式成立返回1，表明队列为空





}



// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//防止队列为空在出数据
	if (q->front->next == NULL)//如果只有一个结点
	{
		q->front = q->tail ==NULL;//那就把这个结点置空，指向头结点指针和指向尾结点的指针指向空


	}
	else
	{
		QNode* next = q->front->next;//保存下一个结点的地址
		free(q->front);//从头结点开始释放一个结点，也就是头删
		q->front = next;//指向头结点的指针移动到下一个位置




	}
	









}
// 获取队列头部元素
int QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);//防止头节点为空
	return q->front->data;//头结点数据





}
// 获取队列队尾元素
int QueueBack(Queue* q)
{
	assert(q);
	assert(q->tail);//防止尾节点为空
	return q->tail->data;//尾节点数据





}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	int size = 0;//记录元素个数变量
	assert(q);
	QNode* cur = q->front;//遍历队列的指针先指向头
	while (cur)
	{
		size++;//遍历记数
		cur = cur->next;




	}
	return size;//返回有效数据个数
}
// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;//遍历队列的指针
	while (cur)
	{
		QNode* next = cur->next;//保存下一个节点的地址
		free(cur);//释放掉当前cur指针指向当前位置的空间
		cur = next;//指向下一个位置



	}
	q->front = q->tail = NULL;//防止野指针



}


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

队列功能测试

int main()
{
	Queue st;
	QueueInit(&st);
	QueuePush(&st, 1);
	QueuePush(&st, 2);
	QueuePush(&st, 3);
	QueuePush(&st, 4);
	while (!QueueEmpty(&st))
	{
		printf("%d ", QueueFront(&st));
		QueuePop(&st);


	}



	QueueDestroy(&st);









}
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

3.栈和队列面试题

20.有效的括号

思路：定义一个栈，将之前的功能都添在前面，使用栈解决这个问题，就是遍历这个字符串，如果是左括号的话，就入栈,然后s++，遇到右括号的话就取出栈顶元素，和这个右括号匹配，匹配上了就出栈栈顶元素，然后s++;没匹配上说明匹配不上，直接return false;当不是左括号的时候，出现右括号时，可能栈里还没有左括号，此时也匹配不上，直接return false;当遍历完s字符串后（s字符串一直是左括号），此时也属于匹配不上，就是判断栈中是否有元素，有元素都是左括号，然后就判空函数返回0==false，(当然定义栈需要初始化栈，和销毁栈)。

代码实现：

typedef struct Stack
{
	char* a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, int data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		char* newnode = (char*)realloc(ps->a,sizeof(char) * newcapcity);
		assert(newnode);
		ps->a = newnode;
		ps->capacity = newcapcity;



	}
	ps->a[ps->top] = data;
	ps->top++;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;





}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
// 获取栈顶元素
char StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;

}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;



}


bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{if(*s=='['||*s=='('||*s=='{')//左括号入栈
   {StackPush(&st,*s);
	 s++;//移动到下一个字符位置




	 }
	else
	{if(StackEmpty(&st))//可能出现无左括号
	  return false;
   char top=StackTop(&st);//获取栈顶元素
			
			if(*s==']'&&top=='['||*s=='}'&&top=='{'||*s==')'&&top=='(')//匹配上就出栈
			{	StackPop(&st);
				s++;//移动下一个字符位置
		}
		 else
		  return false;//匹配不上直接return false
  }




	}
int ret=StackEmpty(&st);// s字符串全是左括号，全部入栈，栈内不为空return 0匹配不上
StackDestroy(&st);//销毁栈
return ret;











}
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

225.用队列实现栈

思路：队列是先进先出，而栈是后进先出，要用两个队列实现栈，一个队列是空的，然后要出栈栈顶元素，也就是队尾元素，可以先将队尾元素的前面的所有元素都入另一个空的队列，然后在pop这个队尾的元素，就能实现后进的先出，由于两个队列构成的栈，将一个队列中的元素入另一个队列，肯定不是出栈。
1.入栈函数的实现
如果哪个队列不为空就把元素入哪个队列中，保证一个队列为空，刚开始的时候，两个队列都为空，入哪个队列都行，在第二次入队列时候，就能保证元素都入不为空的队列了
2.出栈函数的实现
当保证一个队列为空的时候，要实现对应的后入的先出，就可以将非空队列的除队尾元素其他的都入另一个队列中，当非空队列只剩一个元素时，也就是后入的这个元素，将这个元素出队列，并且不入另一个队列，就相当于出栈，出队列前用一个变量存储这个队尾元素，也就是栈顶元素。
3.返回栈顶元素函数
使用定义好的QueueBack函数返回队尾元素，也就是栈顶元素，==注意肯定返回的是非空队列的队尾元素，也就是栈顶元素
4.判断栈为空的函数
使用定义好的QueueEmpty函数，return QueueEmpty（第一个队列地址）&&QueueEmpty（第二个队列地址），当两个队列都为空的时候，QueueEmpty函数就返回1 ，return 1；表示栈为空，如果有一个队列不为空的话，与的结果就是0， return 0，就是栈不为空。
5.释放栈的函数
使用QueueDestroy，销毁两个队列，然后free掉动态申请来的空间。

//队列功能的实现
typedef struct QListNode
{
	struct QListNode* next;
	int data;
}QNode;

typedef struct Queue
{
	QNode* front;
	QNode* tail;
}Queue;
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->tail = NULL;

}
// 队尾入队列
void QueuePush(Queue* q, int x)
{
	assert(q);
	
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	newnode->data =x;
	newnode->next = NULL;
	if (q->tail == NULL)
	{
		q->tail = q->front = newnode;


	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
		



	}
	







}
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL;



}

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->front->next == NULL)
	{
		free(q->tail);
		q->tail = q->front = NULL;



	}
	else
	{
		QNode* next = q->front->next;
		free(q->front);
		q->front = next;




	}

}
// 获取队列头部元素
int QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->data;


}
// 获取队列队尾元素
int QueueBack(Queue* q)
{
	assert(q);
	assert(q->tail);
	return q->tail->data;



}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;

	QNode* cur = q->front;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;




}
// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;





	}
	q->front = q->tail = NULL;




}
//队列功能实现到这里
typedef struct {
Queue a;
Queue b;   

} MyStack;//定义栈


MyStack* myStackCreate() {
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));//给栈申请动态空间
if(obj==NULL)
   {perror("malloc fail");

       


   }
QueueInit(&obj->a);//栈中两个队列的初始化
QueueInit(&obj->b);
return obj;//返回申请栈空间的地址




}

void myStackPush(MyStack* obj, int x)//入栈函数
 {
if(!QueueEmpty(&obj->a))//哪个队列不为空就入哪个队列
{QueuePush(&obj->a,x);


}
else
{QueuePush(&obj->b,x);



}


}

int myStackPop(MyStack* obj) 
{
  Queue* empty=&obj->a;//不知道哪个为空的队列，先随便保存一个
  Queue* nonempty=&obj->b;
  if(!QueueEmpty(&obj->a))//如果a队列不是空的，就将队列b的地址保存在空的指针里面
  {empty=&obj->b;
   nonempty=&obj->a;
  }
  while(QueueSize(nonempty)>1)//当非空的队列只剩下一个元素时，队尾元素，也就是栈顶元素
      {QueuePush(empty,QueueFront(nonempty));//将非空队列的除队尾元素全部入到另一个空的队列中
      QueuePop(nonempty);//队头元素出队列
       }
       int ret=QueueFront(nonempty);//循环结束，只剩下队尾元素，将队尾元素保存在变量中
			  QueuePop(nonempty);//队尾元素出队列，并且不进另一个队列，相当于出栈

       return ret;//返回栈顶元素
}

int myStackTop(MyStack* obj) {
if(QueueEmpty(&obj->a))
{return  QueueBack(&obj->b);



}
else
{return  QueueBack(&obj->a);


//哪个队列不为空，直接使用QueueBack返回不为空队列的队尾元素

}
}

bool myStackEmpty(MyStack* obj) 
{
return QueueEmpty(&obj->a)&&QueueEmpty(&obj->b);





}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->a);
    QueueDestroy(&obj->b);
    free(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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243

232.用栈实现队列

思路：使用两个栈实现队列，栈为后入先出，队列为后入后出，当要出队头元素，也就是栈底元素时，可以将栈顶元素一个接一个放入另一个栈中popst,然后栈底元素到另一个栈就变成了栈顶元素，然后就可以实现队头元素，也就是栈底元素先出栈。
1.入队列函数的实现
使用 StackPush函数将数据入到栈pushst中
2.出队列函数实现
将pushst栈中的栈顶元素一个接一个全部入到栈popst中，将pushst栈中的元素全部pop掉，此时popst栈顶的元素就是队头元素，用一个变量保存他，然后将popst栈顶元素pop掉，return 栈顶元素。
3.返回队列开头的元素的函数
和出队列函数大致相同，这个不需要pop掉队头元素
4.判断队列为空函数
使用StackEmpty函数，return
StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst);当两个栈都为空的时候返回1 ，表示队列为空，只要有一个不为空的话返回0，表示队列不为空。
5.释放队列函数
使用StackDestroy函数销毁两个栈，然后free掉动态开辟的内存。

typedef struct Stack
{
	int* a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
void StackInit(Stack* ps)//初始化栈
{
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void StackPush(Stack* ps, int data)//入栈
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapcity);
		if (tmp == NULL)
		{
			perror("realloc fail");
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapcity;



		}
		





	}
	ps->a[ps->top] = data;
	ps->top++;







}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top ==0;



}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;

}
// 获取栈顶元素
int StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;





}

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;

}

typedef struct {
Stack popst;
Stack pushst;

} MyQueue;//定义队列


MyQueue* myQueueCreate() {

MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));//动态给队列申请空间
 StackInit(&obj->popst);   //初始化两个栈
 StackInit(&obj->pushst); 
 return obj;//返回队列的地址

}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushst,x);//入队列都入到pushst栈中

}

int myQueuePop(MyQueue* obj) {
if(StackEmpty(&obj->popst))//如果popst栈中为空的话
{while(StackSize(&obj->pushst))//将pushst栈中的元素全部入到popst栈中
{StackPush(&obj->popst,StackTop(&obj->pushst));//栈顶元素一个接一个放到popst的栈中
   StackPop(&obj->pushst);//栈顶元素出栈
}

}
int ret=StackTop(&obj->popst);//变量接收popst栈顶元素的值，然后pop掉
StackPop(&obj->popst);
return ret;//返回队列头元素，也就是popst栈顶元素







}

int myQueuePeek(MyQueue* obj) //与上一个函数同理
{
    if(StackEmpty(&obj->popst))
{while(StackSize(&obj->pushst))
{StackPush(&obj->popst,StackTop(&obj->pushst));
   StackPop(&obj->pushst);
}

}
int ret=StackTop(&obj->popst);

return ret;

}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst);

}

void myQueueFree(MyQueue* obj) 
{
StackDestroy(&obj->popst);
StackDestroy(&obj->pushst);
free(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

622.设计循环队列

思路:用数组实现这个队列较简单，在开辟空间大小时，需要k个空间，我们给他开辟k+1个空间，如果尾的下一个是头的话，就说明队列满了，如果头和尾在一个地方，则队列为空，获取队首元素就是返回obj->a[obj->head]即可，获取队尾元素一般要找到obj->tail-1的位置，因为tail是后加，当存最后一个后，他的tail+1;插入元素，就让obj->a[obj->tail]=value;然后tail++;删除一个元素就让head++就行。
注意边界：
检查队列是否满的边界处理：

插入元素的边界处理：
删除元素边界处理：

获取尾部元素的边界处理

typedef struct {
    int*a;//指向队列空间的指针
    int k;//队列空间大小
    int head;//队列头下标
    int tail;//队列尾下标

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//给描述队列的变量创建空间
obj->a=(int *)malloc(sizeof(int)*(k+1));//给队列创建空间
obj->k=k;//队列空间大小赋值
obj->head=obj->tail=0;//初始化队列队尾队头下标
return obj;//返回创建队列信息的地址
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head==obj->tail;//空的话，头下标等于尾下标
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int next=obj->tail+1;//记录尾下标的下一个下标
    if(obj->tail==obj->k)//边界处理
    next=0;
    return next==obj->head;//相等说明tail对应的下一个元素是head,表示已经满了








}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))//满的话直接返回
 return false;
obj->a[obj->tail]=value;//插入元素
obj->tail++;//尾下标更新+1
if(obj->tail==obj->k+1)//边界处理
obj->tail=0;
return true;//插入成功
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))//空的不能删除return false
return false;
obj->head++;     头下标更新+1；
if(obj->head==obj->k+1)//边界处理
obj->head=0;
return true;  //删除成功return true

}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//空的话返回-1；
    return -1;
    
    
    return obj->a[obj->head];//不空返回头下标对应的元素

}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//空的话返回-1；
    return -1; 
    int prev=obj->tail-1;//记录尾下标的上一个下标
    if(prev==-1)//边界处理
      prev=obj->k; 
    return obj->a[prev];//返回队列尾元素

}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(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

先free掉obj的话，obj->a指针中存放的队列的地址置为随机值，永远free不了obj->a,存在内存泄漏，所以先free obj->a,然后free obj.