【数据结构】栈的实现以及数组和链表的优缺点

个人主页：一代…
个人专栏：数据结构

1.栈

1.1栈的概念及结构

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

栈的实现

栈的实现可以用两种线性结构来实现，一种是数组，另一种是链表。

那么用哪种来实现栈比较合适呢？
那我们就要来考虑数组和链表的各自的好处了。

**学过顺序表的小伙伴都知道顺序表的底层是用数组来实现的。那么顺序表和链表有什么区别呢？

1. 存储空间：
   顺序表的物理和逻辑上是连续的
   链表的物理上不一定连续，但逻辑上连续
2. 随机访问
   顺序表随机访问某一个元素时时间复杂度为O(1)
   链表访问某一个元素时时间复杂度尾O(N)
3. 在任意位置插入和删除元素
   顺序表插入和删除元素的时间复杂度为O(N)
   链表的时间复杂度为O(N)
4. 空间利用
   动态顺序表空间不够是需要扩容，可能造成空间浪费
   链表没容量的概念，新增一个节点就malloc一个大小为STDataType的空间
5. 缓存利用率
   顺序表的缓存利用率高
   链表的缓存利用率低

缓存利用率

这里主存就相当于内存，本地磁盘就相当于硬盘，这两个的一个区别就是带点和不带电的区别，内存和硬盘在带电状态下都能正常工作，但它们的工作方式和工作内容完全不同。
内存是易失性的，即当电源关闭时，内存中的数据会丢失。而硬盘是非易失性的，即使电源关闭，数据也会保留。
在不带电状态下，硬盘可以更安全地进行物理操作，而内存则无法进行任何操作（因为内存模块本身不包含任何电源或机械部件）。

    这里我浅浅讲一下顺序表和链表缓存利用率的区别
1

数组（顺序表）和链表在缓存利用率上的区别主要体现在它们的物理存储结构和访问方式上。
在访问一块数据内存空间时，要先把内存加载到缓存，在对其进行访问，而其并不是没此访问一个内存就将其加载到缓存，而是访问一块内存时将其后面的连续的内存一起加载到缓存，然后在对其进行访问。
数组是一块连续的内存空间，元素紧密排列，空间效率更高。这种物理空间的连续性使得数组在访问数据时具有更高的缓存利用率。当CPU执行指令运算需要访问数据时，会先去缓存中查找这个数据。如果数据已经在缓存中（缓存命中），那么CPU就可以直接从缓存中读取数据，而不需要从主存中读取，从而提高了程序的运行效率。由于数组的物理地址是连续的，因此数组中的数据在缓存中的命中率更高，减少了从主存中读取数据的次数，从而提高了缓存利用率。
相比之下，链表是由节点组成，节点之间通过引用（指针）连接。链表在添加和删除元素时只需要改变指针的指向，以节点为单位进行动态内存分配和回收，灵活并且插入和删除效率高。但是，链表的节点在物理存储上是不连续的，因此链表中的数据在缓存中的命中率相对较低。当CPU需要访问链表中的数据时，可能需要频繁地从主存中读取数据到缓存中，降低了缓存利用率，并且会造成缓存污染。
综上所述，数组（顺序表）由于物理空间的连续性，在缓存利用率上通常优于链表。这也是为什么在需要频繁访问数据的场景下，如数组的遍历、查找等操作，使用数组通常会比链表更高效。

所以链表和数组实现栈的区别并不大，但数组比链表更优一些。
（注：链表实现栈可以用单链表，用首元结点作栈顶，也可以用双链表来实现）
下面我们就开是讲解栈的实现

栈的初始化

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_capacity = 0;
	//top指向栈顶数据的下一个位置
	ps->_top = 0;
	//top指向栈顶数据
	//ps->_top = -1;
	ps->_a = NULL;
}

1
2
3
4
5
6
7
8
9
10
11

这里初始化top既可以为0，也可以为-1，为0为top指向栈顶数据的下一个位置，为-1时指向栈顶数据。

栈的销毁

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}
1
2
3
4
5
6
7

入栈

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//扩容
	if (ps->_top == ps->_capacity)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}

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

出栈

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	ps->_top--;
}

1
2
3
4
5
6
7

取出栈顶元素

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	return ps->_a[ps->_top - 1];
}
1
2
3
4
5
6

栈的大小

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
1
2
3
4
5

栈是否为空

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}
1
2
3
4
5
6
7

栈的全部代码
stack.h

#define  _CRT_SECURE_NO_WARNINGS 1
// 支持动态增长的栈
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(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

stack.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_capacity = 0;
	//top指向栈顶数据的下一个位置
	ps->_top = 0;
	//top指向栈顶数据
	//ps->_top = -1;
	ps->_a = NULL;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//扩容
	if (ps->_top == ps->_capacity)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("relloc fail");
			return;
		}
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	ps->_top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	return ps->_a[ps->_top - 1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 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
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

test.c

#include"stack.h"
int main()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 5);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 6);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	printf("%d\n",StackSize(&st));
	if (StackEmpty(&st))
	{
		printf("栈为空\n");
	}
	else
	{
		printf("栈不为空\n");
	}
	int ret=StackTop(&st);
	printf("%d\n", ret);
	if (!StackEmpty(&st))
	{
		for (int i = 0; i < st._top; i++)
		{
			printf("%d ", st._a[i]);
		}
	}
	StackDestroy(&st);
	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
31
32
33
34