栈和队列

发表于

标题：栈和队列的定义和基本操作

栈：栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
  • 栈就可以理解为：先入后出（LIFO）
Stack.h 头文件
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
 #pragma once
 #include <stdio.h>
 #include <assert.h>
 #include <malloc.h>
 #include <stdlib.h>
 #include "Maze.h"
typedef  int DataType;
typedef struct Stack
{
	DataType  *_a;
	int _top;        //栈顶的位置
	int _capacity;   //栈的容量
}Stack;
//栈的初始化 
void StackInit(Stack *ps);
//栈的销毁
void StackDestroy(Stack *ps);
//入栈
void StackPush(Stack *ps, DataType x);
//出栈
void StackPop(Stack *ps);
//取栈顶元素
DataType StackTop(Stack *ps);
//判断栈是否为空
int StackEmpty(Stack *ps);
//栈的大小
int StackSize(Stack *ps);
Stack.c 主函数文件
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
 #include "Stack.h"
//栈的初始化
void StackInit(Stack *ps)
{
	ps->_a = (DataType *)malloc(sizeof(DataType)* 3);	
	// 检查空间是否开辟成功
	assert(ps->_a);    
	ps->_top = 0;
	ps->_capacity = 3;
}
//栈的销毁
void StackDestroy(Stack *ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}
//入栈
void StackPush(Stack *ps, DataType x)
{
	assert(ps);
	//检查是否需要开辟空间
	if (ps->_top >= ps->_capacity){
		ps->_a = (DataType*)realloc(ps->_a, sizeof(Stack)* (ps->_capacity*2));
		assert(ps->_a);
		ps->_capacity *= 2;
	}
	ps->_a[ps->_top] = x;
	ps->_top++;
}
//出栈
void StackPop(Stack *ps)
{
	//判断栈是否为空
	assert(ps->_top>0&&ps);
	ps->_top--;
}
//取栈顶元素
DataType StackTop(Stack *ps)
{
	assert(ps);
	return ps->_a[ps->_top-1];
}
//判断栈是否为空
int StackEmpty(Stack *ps)
{
	assert(ps);
	//如果为空返回0,否则返回1
	return ps->_top == 0 ? 0 : 1;
}
//栈的大小
int StackSize(Stack *ps)
{
	assert(ps);
	return ps->_top;
}
test.c 测试文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 #include "Stack.h"
int main()
{	Stack ps;
	StackInit(ps);
	StackPush(ps, 1);
	StackPush(ps, 2);
	StackPush(ps, 3);
	StackPush(ps, 4);
	while (StackEmpty(ps))
	{
		printf("%d ", StackTop(ps));
		StackPop(ps);
	}
	printf("\n");
	Destroy(ps);
        system("pause");
	return 0;
}

队列：队列（Queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

  • 队列可以理解为:先入先出(FIFO)
Queue.h 头文件
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
 #pragma once 
 #include <stdio.h>
 #include <assert.h>
 #include <stdlib.h>
 #include <malloc.h>
typedef int DataType;
typedef struct QueueNode
{
	struct QueueNode * _next;
	DataType _data;
}QueueNode;
typedef struct Queue
{
	QueueNode *_front; //队头
	QueueNode *_back;  //队尾
}Queue;
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestory(Queue* pq);
//申请节点
QueueNode* BuyQueueNode(DataType x);
//入队
void QueuePush(Queue* pq, DataType x);
//出队
void QueuePop(Queue* pq);
//取队头元素
DataType QueueFront(Queue* pq);
//判断是否为空队列
int QueueEmpty(Queue* pq);
//求队列大小
int QueueSize(Queue* pq);
void TestQueue();
Queue.c 主函数文件
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
 #include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->_back = pq->_front = NULL;
}
//队列的销毁
void QueueDestory(Queue* pq)
{
	QueueNode *next;
	QueueNode *cur;
	assert(pq);
	cur = pq->_front;
	while (cur)
	{
		next = cur->_next;
		free(cur);
		cur = next;
	}
}
//申请节点
QueueNode* BuyQueueNode(DataType x)
{
	QueueNode *ret = (QueueNode*)malloc(sizeof(QueueNode));
	ret->_data = x;
	ret->_next = NULL;
	return ret;
}
//入队
void QueuePush(Queue* pq, DataType x)
{
	assert(pq);
	//如果队列为空,入队尾,同时让队头等于队尾
	//如果队列不为空,直接入队尾
	if (pq->_back){
		pq->_back = pq->_back->_next = BuyQueueNode(x);
	}
	else{
		pq->_front = pq->_back = BuyQueueNode(x);
	}
}
//出队
void QueuePop(Queue* pq)
{
	QueueNode* next;
	assert(pq);
	//判断是否队头等于队尾,如果等于free队头或队尾,并且置空
	//若不相等则释放队头,让队头等于它的next
	if (pq->_front == pq->_back){
		free(pq->_front);
		pq->_back = NULL;
		pq->_front = NULL;
	}
	else{
		next = pq->_front->_next;
		free(pq->_front);
		pq->_front = next;
	}
}
//取队头元素
DataType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->_front->_data;
}
//判断是否为空
int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->_back == NULL ? 0 : 1;
}
//队列大小
int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode *ret;
	assert(pq);
	ret = pq->_front;
	while (ret){
		ret = ret->_next;
		size++;
	}
	free(ret);
	ret = NULL;
	return size;
}
//测试函数
void TestQueue();
test.c 测试文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 #include "Queue.h"
int main()
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);
	QueuePush(&pq, 3);
	QueuePush(&pq, 4);
	while (QueueEmpty(&pq))
	{
		printf("%d ", QueueFront(&pq));
		QueuePop(&pq);
	}
	QueueDestory(&pq);
	system("pause");
	return 0;
}