《数据结构：栈和队列》

一、栈

1、概念与结构

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

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

二、栈的实现

1、栈的结构和功能

stack.h:

#pragma once

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

typedef int STDateType;

typedef struct stack
{
	STDateType* a;
	int capacity;//存储空间
	int top;//栈顶
}ST;


//初始化栈
void STInit(ST* ps);

//入栈
void STPush(ST* ps,STDateType x);

//出栈
void STPop(ST* ps);

//取栈数据
STDateType STTop(ST* ps);

//栈中有效个数
int STSize(ST* ps);

//栈是否为空
bool STEmpty(ST* ps);
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

2、初始化栈

//初始化栈
void STInit(ST* ps)
{
	assert(ps != NULL);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
1
2
3
4
5
6
7

3、入栈

//入栈
void STPush(ST* ps, STDateType x)
{
	assert(ps != NULL);
	if (ps->capacity == ps->top)
	{
		int new = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDateType* tem = (STDateType*)realloc(ps->a, new * sizeof(STDateType));
		if (tem == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->a = tem;
		tem = NULL;
		ps->capacity = new;
	}
	ps->a[ps->top++] = x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4、出栈

//出栈
void STPop(ST* ps)
{
	assert(ps != 0);
	assert(!STEmpty(ps));
	ps->top--;
}
1
2
3
4
5
6
7

5、判断栈是否为空

//栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps != NULL);
	return ps->top == 0;
}
1
2
3
4
5
6

6、取栈元素和栈有效个数

//取栈数据
STDateType STTop(ST* ps)
{
	assert(ps != NULL);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

//栈中有效个数
int STSize(ST* ps)
{
	assert(ps != NULL);
	return ps->top;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7、销毁栈

//销毁栈
void STDeaTroy(ST* ps)
{
	assert(ps != NULL);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
1
2
3
4
5
6
7
8

三、队列

1、概念与结构

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

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

四、队列的实现

1、队列的实现结构和功能

Queue.h

#pragma once

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

typedef int QNDateType;

typedef struct QueueNode
{
	QNDateType date;
	struct QueueNode* next;//下个结点
}QN;

typedef struct Queue
{
	QN* phead;
	QN* ptail;
	int size;
}Queue;


//初始化队列
void QueueInit(Queue* pq);

//从队尾入队列
void QueuePush(Queue* pq,QNDateType x);

//从对头出队列
void QueuePop(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//取队列头元素
QNDateType QueueFront(Queue* pq);

//取队列尾元素
QNDateType QueueBack(Queue* pq);

//取队列有效数据个数
int QueueSize(Queue* pq);

//销毁队列
void QueueDesTroy(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
38
39
40
41
42
43
44
45
46

2、队列初始化

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq != NULL);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

1
2
3
4
5
6
7
8
9

3、入队列

//从队尾入队列
void QueuePush(Queue* pq, QNDateType x)
{
	assert(pq != NULL);
	QN* newnode = (QN*)malloc(sizeof(QN));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->date = x;
	newnode->next = NULL;
	pq->size++;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq != NULL);
	return pq->phead == NULL && pq->ptail == NULL;
}
1
2
3
4
5
6

5、出队列

//从对头出队列
void QueuePop(Queue* pq)
{
	assert(pq != NULL);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)//只有一个元素
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QN* del = pq->phead;
		pq->phead = pq->phead->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

6、取队头/队尾元素

//取队列头元素
QNDateType QueueFront(Queue* pq)
{
	assert(pq != NULL);
	assert(!QueueEmpty(pq));
	return pq->phead->date;
}

//取队列尾元素
QNDateType QueueBack(Queue* pq)
{
	assert(pq != NULL);
	assert(!QueueEmpty(pq));
	return pq->ptail->date;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

7、取元素个数

//取队列有效数据个数
int QueueSize(Queue* pq)
{
	assert(pq != NULL);
	return pq->size;
}
1
2
3
4
5
6

8、销毁队列

//销毁队列
void QueueDesTroy(Queue* pq)
{
	assert(pq != NULL);
	QN* pcur = pq->phead;
	while (pcur)
	{
		QN* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14