栈

栈的概念和结构

栈：只允许在固定的一端进行插入和删除元素的操作。进行数据的插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循LIFO（Last in First out）原则。

入栈：栈的插入操作叫做进栈/压栈/入栈。

出栈：栈的删除操作叫做出栈。

栈的实现

栈的思想及其结构就像上图所描述的一样，能够实现以上操作就叫做栈，方法有挺多，但是一般使用数组或者链表实现，而其中数组又是最常见的，因为相比链表，数组在尾插和尾删上更有优势。

顺序表就是用数组实现的，所以这里用数组实现的栈与顺序表有很多的相似之处。

栈的结构声明

typedef int StackDateType;
typedef struct Stack
{
	StackDateType* array;
	int top;
	int capacity;
}Stack;
1
2
3
4
5
6
7

top下标始终为栈顶元素的下一个，同时top又代表了栈中元素的数量；

capacity是栈的总容量，当top与capacity相等时，需要扩容。

栈的初始化

void StackInit(Stack* p){
	assert(p);
	p->array = NULL;
	p->top = p->capacity = 0;
}
1
2
3
4
5

栈的初始化给空间也可以，不给空间也可以(在插入元素的时候给空间)。

栈的销毁

void StackDestroy(Stack* p){
	assert(p);
	free(p->array);
	p->array = NULL;
	p->top = p->capacity = 0;
}	
1
2
3
4
5
6

栈的插入元素（入栈）

void StackPush(Stack* p, StackDateType data){
	assert(p);
  //扩容
	if(p->top == p->capacity){
    //当初次使用栈，栈为空时，先给栈4个元素的大小，以后每次扩容时，增为二倍
		int NewCapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		StackDateType* NewArray = (StackDateType*)realloc(p->array, sizeof(StackDateType) * NewCapacity);
		if(NewArray == NULL){
			perror("realloc fail");
			exit(-1);
		}
		p->array = NewArray;
		p->capacity = NewCapacity;
	}
  //将元素插入到栈中，并且top自增
	p->array[p->top++] = data;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

栈的删除元素（出栈）

void StackPop(Stack* p){
	assert(p);
  //断言一下栈为空时，无法出栈
	assert(!StackEmpty(p));
  //由于栈是由数组实现的，而访问数组用的是下标，所以数组尾删时，只需要将下标自减一下就ok
	p->top--;
}
1
2
3
4
5
6
7

获取栈顶元素

StackDateType StackTop(Stack* p){
	assert(p);
  //断言一下栈为空时，无法获取栈顶元素
	assert(!StackEmpty(p));
  //由于top是栈顶元素的下一个元素的下标，所以获取栈顶元素时，需要top - 1
	return p->array[p->top - 1];
}
1
2
3
4
5
6
7

判断栈为空

int StackEmpty(Stack* p){
	assert(p);
  //top代表栈中元素的数量，所以当top为0时，栈为空
	return p->top == 0;
}
1
2
3
4
5

获取栈中元素的数量

int StackSize(Stack* p){
	assert(p);
  //top代表栈中元素的数量
	return p->top;
}
1
2
3
4
5

队列

队列的概念和结构

队列：只允许在一端进行插入元素的操作，在另一段进行删除元素的操作，进行数据的插入的一端称为队尾，进行数据的删除的一端称为队头。队列中的数据元素遵循FIFO（First in First out）原则。

入队：插入元素称为入队。

出队：删除元素称为出队。

队列的实现

队列由于具有先入先出的特性，所以需要进行尾插和头删，而头删则是链表比较擅长的，所以使用链表实现队列是最常见的。

队列的结构声明

typedef int QueueDateType;
typedef struct QueueNode{
	struct QueueNode* next;
	QueueDateType val;
}QueueNode;
typedef struct Queue{
	QueueNode* front;//指向链表的头
	QueueNode* back;//指向链表的尾
  int size;//代表链表的结点数量
}Queue;
1
2
3
4
5
6
7
8
9
10

这里是两个结构体，第一个用来形成链表，第二个用来控制链表。

队列的初始化

void QueueInit(Queue* p){
	assert(p);
	p->front = p->back = NULL;
	p->size = 0;
}
1
2
3
4
5

队列的销毁

void QueueDestroy(Queue* p){
	assert(p);
  //销毁链表的经典操作
	QueueNode* curr = p->front;
	while(curr){
		QueueNode* next = curr->next;
		free(curr);
		curr = next;
	}
	p->front = p->back = NULL;
	p->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

队列的插入元素（入队）

void QueuePush(Queue* p, QueueDateType val){
	assert(p);
  //创建结点
	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
	if(node == NULL){
		perror("malloc fail");
		exit(-1);
	}
	node->next = NULL;
	node->val = val;
  //将结点与头尾两个指针建立联系
  //若back为空，则队列此时无结点，为空，所以将front和back都指向该结点
	if(p->back == NULL){
		p->front = p->back = node;
	}
  //此时，队列不为空，front会一直指向第一个结点，而back则需要链接新结点，并且更新back的指向
	else{
		p->back->next = node;//链接新结点
		p->back = node;//更新back的指向
	}
	p->size++;//队列元素数量加1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

队列的删除元素（出队）

void QueuePop(Queue* p){
	assert(p);
  //断言一下，当队列为空时，无法出队
	assert(!QueueEmpty(p));
  //当队列只有一个元素时
	if(p->front->next == NULL){
		free(p->front);
		p->front = p->back = NULL;
	}
  //当队列有多个元素时，头删
	else{
		QueueNode* next = p->front->next;
		free(p->front);
		p->front = next;
	}
	p->size--;//队列元素数量减1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

获取队头元素

QueueDateType QueueFront(Queue* p){
	assert(p);
	assert(!QueueEmpty(p));
	return p->front->val;
}
1
2
3
4
5

获取队尾元素

QueueDateType QueueBack(Queue* p){
	assert(p);
	assert(!QueueEmpty(p));
	return p->back->val;
}
1
2
3
4
5

判断队列为空

int QueueEmpty(Queue* p){
	assert(p);
	return p->size == 0;
}
1
2
3
4

获取队列中元素的数量

int QueueSize(Queue* p){
	assert(p);
	return p->size;
}
1
2
3
4