数据结构-栈和队列（2）

作者：学Java的冬瓜
博客主页：☀冬瓜的主页🌙
专栏：【C/C++ 数据结构和算法】

前言

说明：本篇博客的学习目标是：实现栈和队列的代码，实现分析请看数据结构上一篇博客。

链接：
上篇：栈和队列的实现分析

一、栈

Stack.h

头文件，结构体声明，函数声明

#pragma once

#include 
#include 
#include 
#include 
#include 

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}Stack;

//初始化栈
void StactInit(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);

//压栈
void StackPush(Stack* ps ,STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶数据
STDataType StackTop(Stack* ps);

//获取栈的有效数据的个数
int StackSize(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* 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

Test.c

main函数和StackTest函数

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

void StackTest()
{
	Stack s;
	StactInit(&s);

	StackPush(&s,1);
	StackPush(&s, 2);
	StackPush(&s, 3);

	//注意：要使用提供的接口去获取，输出，出栈。
	while (!StackEmpty(&s))
	{
		printf("%d ", StackTop(&s));
		StackPop(&s);
	}
	printf("\n");

	//注意：用完后，销毁malloc(或者realloc)在堆的数组空间
	StackDestroy(&s);
}

int main()
{
	StackTest();
	return 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

Stack.c

实现栈的各个功能

1、初始化和销毁

1.1、StackInit

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

//初始化栈
void StactInit(Stack* ps)
{
	assert(ps);

	//注意：动态申请数组空间
	STDataType* tmp = (STDataType*)malloc(4 * sizeof(STDataType));
	//1、申请失败
	if (tmp == NULL)
	{
		printf("realloc fail\n");
		exit(-1);
	}
	//2、申请成功
	else
	{
		ps->data = tmp;
		ps->capacity = 4;
		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

1.2、StackDestroy

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

2、入栈、出栈

2.1、StackPush

//压栈/入栈
void StackPush(Stack* ps, STDataType x)
{
	//1、断言，确保ps不等于NULL。
	assert(ps);

	//2、判断空间是否已满，满了就先增容
	if (ps->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->data, 2 * ps->capacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
	    else
		{
			ps->data = tmp;
			ps->capacity *= 2;
		}
	}
	
	//3、尾插
	ps->data[ps->top] = x;
	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
26
27

2.2、StackPop

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//注意：确保top不越界，栈空时，直接终止程序报错
	assert(ps->top > 0);

	ps->top--;
}
1
2
3
4
5
6
7
8
9

3、其它功能

3.1、StackTop

说明： 获取栈顶元素

//获取栈顶数据
STDataType StackTop(Stack* ps)
{
	assert(ps);
	//注意：若栈中没有数据了，ps->top=0，没有下面这步断言，会导致数组越界
	assert(ps->top > 0);

	return ps->data[ps->top - 1];
}
1
2
3
4
5
6
7
8
9

3.2、StackSize

说明：获取栈有效数据的个数

//获取栈有效数据的个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5
6

3.3、StackEmpty

说明： 判断栈是否为空

//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、队列

Queue.h

头文件，结构体声明，函数声明

#pragma once

#include 
#include 
#include 
#include 


typedef int QDataType;
//链表的节点
typedef struct QNode
{
	QDataType data;
	struct QNode* next;
}QNode;
//存储head和tail两个指针，用来连接链表
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}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);

//获取队列有效数据的个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(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

Test.c

main函数和QueueTest函数

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

void QueueTest()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	printf("\n");
	QueueDestroy(&q);
}
int main()
{
	QueueTest();
	return 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

Queue.c

队列各个功能的实现

1、初始化和销毁

1.1、QueueInit

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

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

	pq->head = NULL;
	pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.2、QueueDestroy

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur != NULL)
	{
		QNode* next = cur->next;

		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、队尾入队、队头出队

2.1、QueuePush

//队尾入队（尾插）
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	//注意1：创建新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//1、空间申请失败
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//2、空间申请成功
	newnode->data = x;
	newnode->next = NULL;


	//注意2：连接链表
	//3、处理队列链表头节点
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//4、处理其它节点
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
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

2.2、QueuePop

//队头出队（头删）
void QueuePop(Queue* pq)
{
	assert(pq);
	//注意1：若队列中没有数据了，就不能出队了，会中止程序
	assert(pq->head);


	//重点：注意2：要把只有一个节点单独提出来，否则tail始终指向最后一个节点，它变成野指针
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//注意3：free()前，记录第一个节点的下一个节点
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

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

3、其它功能

3.1、QueueFront

说明：获取队头元素

//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//重点：pq->head不等于NULL，确保不越界，正常返回数据
	assert(pq->head);

	return pq->head->data;
}

1
2
3
4
5
6
7
8
9
10

3.2、QueueBack

说明：获取队尾元素

//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}

1
2
3
4
5
6
7
8
9

3.3、QueueSize

说明：获取有效数据的个数

//获取有效数据的个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;

	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.4、QueueEmpty

说明：判断队列是否为空

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