数据结构—数组栈的实现

前言：各位小伙伴们我们前面已经学习了带头双向循环链表，数据结构中还有一些特殊的线性表，如栈和队列，那么我们今天就来实现数组栈。

目录：

一、
栈的概念
二、
栈的实现
三、
代码测试

栈的概念：

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

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈的实现：

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

接口：

// 初始化栈
void STInit(ST* pst);
// 销毁栈
void STDestroy(ST* pst);

// 入栈
void STPush(ST* pst, STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶元素
STDataType STTop(ST* pst);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* pst);
// 获取栈中有效元素个数
int STSize(ST* pst);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这里我们需要三个文件，一个头文件，一个文件用来实现我们的各种接口，一个文件用来测试我们的代码。

头文件（Stack.h）：

#pragma once
#include
#include
#include
#include


typedef int STDataType;

typedef struct Stack
{
	int* a;
	int top;		// 标识栈顶位置的
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);
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

我们的top是栈顶，如果我们的top=0时，我们指向的就是栈顶元素，如果我们的top=1，那么我们的top指向的就是栈顶元素的下一个位置。

函数实现（Stack.c）

#include"Stack.h"

void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;
}

void STDestroy(ST* pst)
{

}

// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	pst->top--;
}

STDataType STTop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

bool STEmpty(ST* pst);
int STSize(ST* pst);
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

测试代码（test.c）

int main()
{
		ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
		while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们这里入栈五个数据，当我们的栈里面不为空时，我们就访问栈顶元素，在让栈顶元素出栈。直到我们的栈为空时，就退出循环。

int main()
{
	
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	printf("%d ", STTop(&s));
	STPop(&s);
	printf("%d ", STTop(&s));
	STPop(&s);

	STPush(&s, 4);
	STPush(&s, 5);

	
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");

	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

这里我们可以同时入栈和出栈，我们先入栈1,2，3，在出栈，我们的栈是后入先出，也就是说我们后面入栈的元素在出栈的时候先出栈，我们出栈一个也就是3，再出栈就是2，最后入栈就是4,5。