【数据结构】栈和队列的实现

---

一、栈的实现

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈低。栈遵循数据后进先出的原则。

创建一个栈：

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int capacity; //容量
	int top; //栈顶
}ST;
1
2
3
4
5
6
7

当栈顶初始化为0时，代码如下：

top先放数据，再++

//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->top = 0;
	ps->capacity = 4;
}
//销毁栈
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
//入栈
void StackPush(ST* ps, STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
//获取栈顶元素
STDatatype StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
//判断栈是否为空，若为空，则返回非零，若不为空，则返回零
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//获取栈中的元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return 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
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

当栈顶初始化为-1时，代码如下：

top先++，再放数据

//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->top = -1;
	ps->capacity = 4;
}
//销毁栈
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = -1;
	ps->capacity = 0;
}
//入栈
void StackPush(ST* ps, STDatatype x)
{
	assert(ps);
	if (ps->top + 1 == ps->capacity)
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->top++;
	ps->a[ps->top] = x;
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
//获取栈顶元素
STDatatype StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top];
}
//判断栈是否为空，若为空，则返回非零，若不为空，则返回零
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == -1;
}
//获取栈中的元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top + 1;
}
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

---

二、队列的实现

队列是一种特殊的线性表，只允许在一端进行插入数据操作，在另一端进行删除数据操作，进行插入数据的一端称为队尾，进行删除数据的一端称为队头。

创建一个栈：

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13

代码实现：

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
	}
	pq->size--;
}
//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
//获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
//判断队列是否为空，若为空，则返回非零，若不为空，则返回零
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}
//获取队列中元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
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