初阶数据结构：栈与队列

1. 简述：栈

1. 栈为一种特殊的线性表，它只允许在指定的一端进行数据的插入和删除操作。被指定进行插入和删除操作的一端被称为栈顶，另一端，被称为栈底，其遵循着数据的先进后出原则。
2. 压栈：栈插入数据的操作被称为进栈，压栈等
3. 出栈：栈的删除操作被称为出栈。

2. 栈的功能分析与实现

2.1 功能分析

1. 栈的创建与初始化：stackinit
2. 栈的插入与删除操作：stackpush，stackpop
3. 获取栈顶元素与检测栈中的有效元素个数：stacktop，stacksize
4. 栈的判空与销毁：stackempty，stackdestroy

2.2 栈的实现

2.2.1 栈的结构创建与初始化

静态栈与动态栈：

1. 静态栈：在定义初始化就指定了栈的大小，容量不可根据所需动态增长
2. 动态栈：会根据存储数据的增多不断扩大自身的容量

注：动态栈更具有学习与应用意义，以下内容都默认为动态栈

栈的结构：

补充：栈的数据结构只对逻辑上有要求，必须满足元素的先进后出与栈顶，栈底的逻辑结构。因此，具体实现时使用数组或链表都可，数组的结构方便实现与适合栈。（数组栈）

//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
	STDataType _a[N];
	int _top; // 栈顶
}Stack;

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top; // 栈顶
	int _capacity; // 容量
}Stack;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

栈的扩容与初始化：

//扩容
void CheckCapacity(Stack* ps)
{
	if (ps->_capacity == ps->_top)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* data = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
		if (data == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}

		ps->_a = data;
		ps->_capacity = newcapacity;
	}
}

//初始化
void StackInit(Stack* ps)
{
	ps->_capacity = 0;
	ps->_top = 0;
	ps->_a = NULL;

	CheckCapacity(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

2.2.2 压栈，出栈与判空：

//压栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	
	CheckCapacity(ps);
	ps->_a[ps->_top] = data;
	ps->_top++;
}

//判空
int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->_top == 0;
}

//出栈
void StackPop(Stack* ps)
{
	assert(!StackEmpty(ps));

	ps->_top--;
}
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

2.2.3 获取栈顶元素，检索栈的长度与栈的销毁

//获取栈顶元素
STDataType 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->_capacity = ps->_top = 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

3. 简述：队列

队列为一种只允许在一端插入数据，在另一端删除数据的特殊线性表，其遵循着先进先出的原则。进行插入操作的一侧被称为队尾，进行删除操作的一侧被称为队首。

4. 队列的功能分析与实现

4.1 队列的功能分析

1. 队列的结构与初始化：queueinit
2. 队列的插入与删除操作：queuepush，queuepop
3. 获取队尾与队头元素：queuefront，qeueuback
4. 获取队列中有效元素个数：queuesize
5. 队列判空与销毁：queueempty，queuedestroy

4.2 队列的实现

4.2.1 队列的结构与初始化

注：因为队列的删除操作为头删，所以此处采用头删更为方便的链式结构：链表。

队列的结构：

typedef int QDataType;

//队列结点
typedef struct QListNode
{
	struct QListNode* _pNext;
	QDataType _data;
}QNode;

// 队列的结构（队列的头尾）
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

队列的初始化：

void QueueInit(Queue* q)
{
	assert(q);

	q->_front = q->_rear = NULL;
}
1
2
3
4
5
6

4.2.2 队列的插入和删除操作

创建新结点与插入操作：

//结点申请
QNode* BuyNewNode2(QDataType data)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	newnode->_data = data;
	newnode->_pNext = NULL;

	return newnode;
}

//插入
void QueuePush(Queue* q, QDataType data)
{
	assert(q);

	QNode* newnode = BuyNewNode2(data);
	if (q->_front == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_pNext = newnode;
		q->_rear = q->_rear->_pNext;
	}
}

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

判空与删除操作：

//判空
int QueueEmpty(Queue* q)
{
	assert(q);

	return q->_front == NULL;
}

//删除
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	QNode* cur = q->_front->_pNext;
	free(q->_front);
	q->_front = cur;

	if (q->_front == NULL)
	{
		q->_rear = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4.2.3 返回队首与队尾元素，计算队列有效元素长度

//返回队头元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->_front->_data;
}

//返回队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->_rear->_data;
}

//返回队列有效长度
int QueueSize(Queue* q)
{
	assert(q);

	int count = 0;
	QNode* cur = q->_front;
	while (cur)
	{
		cur = cur->_pNext;
		count++;
	}

	return count;
}
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

4.2.4 队列的销毁

void QueueDestroy(Queue* q)
{
	assert(q);

	while (q->_front)
	{
		QueuePop(q);
	}
}
1
2
3
4
5
6
7
8
9