回顾

顺序表和链表的区别和联系

顺序表：

​ 优点：空间连续支持随机访问。

​ 缺点：1.中间或前面的插入删除时间复杂度O(N)。

​ 2.增容的代价比较大

链表(带头双向循环)：

​ 缺点：

​ 以借点为单位存储，不支持随机访问。

​ 优点：

​ 1.任意位置插入删除时间复杂度为O(1)

​ 2.没有增容消耗，按需申请结点空间，不用了直接释放。

栈

栈也是线性表，在逻辑上还是挨着放的。

栈的概念以及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

image-20210607120710677

实现方式：

  1. 数组实现

    image-20210607120936928

    总结：

    相当于之前顺序表的尾插尾删，用尾做栈顶，非常合适，唯一缺陷就是，空间不够需要增容(影响不大)。

    (顺序表——【线性表】之顺序表_半生瓜のblog-CSDN博客)

  2. 链表实现

image-20210607121416245

出数据得找到前一个，这样的话用双向链表更好一些。

(所以说数据结构并没有规定用什么方法实现，只要能实现就行，对比的就是效率而已。)

也可以将单链表反过来。

image-20210607121819132

总结：

​ 如果用尾插做栈顶，用双向链表更好。

​ 如果用单链表实现，就用头去做栈顶，这样入栈和出栈效率都是O(1)。

​ 整体来说数组的效率更优一些。

结构定义

1
2
3
4
5
6
7
typedef int StackDataType;
typedef struct Stack
{
	StackDataType* arry;
	int top;//指向栈顶
	int capacity;//栈的容量——能放几个数据
}Stack;

初始化

如果初识的top给0，意味着top指向栈顶的元素的下一个，top给-1，top指向栈顶元素。

一定不能为空的东西，可以使用断言来处理。OJ题不可以使用断言。

1
2
3
4
5
6
7
8
9
10
11
12
void StackInit(Stack* ps)
{
	assert(ps);
	ps->arry = (StackDataType*)malloc(sizeof(StackDataType)*4);
	if (ps->arry == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

销毁

1
2
3
4
5
6
7
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->arry);
	ps->arry = 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
void StackPush(Stack* ps, StackDataType x)
{
	assert(ps);
	//满了
	if (ps->top == ps->capacity)
	{
		StackDataType* tmp = (StackDataType*)realloc(ps->arry, ps->capacity * 2 * sizeof(StackDataType));
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		else
		{
			ps->arry = tmp;
			ps->capacity *= 2;
		}
	}
	ps->arry[ps->top] = x;
	ps->top++;
}

出栈

1
2
3
4
5
6
7
void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈空了调用top，直接终止程序报错
	assert(ps->top > 0);
	ps->top--;
}

返回栈顶元素

1
2
3
4
5
6
StackDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->arry[ps->top - 1];
}

返回栈中元素个数

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

判断栈是否为空

1
2
3
4
5
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//真为空，假为非空。
}

小提示:

上面有的函数只有两行代码，如果直接用里面的那句代码，可以吗？
可以，但是不好，通过那句代码访问到，但严格来说你不应该去访问，这是一种耦合，耦合就是一种强关联，
调用函数，无需去想top在0还是在-1，只管用就完事了。(有点软件工程的思想)

调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(void)
{	
	Stack ps;
	StackInit(&ps);
	StackPush(&ps,1);
	StackPush(&ps,2);
	StackPush(&ps,3);
	while (!StackEmpty(&ps))
	{
		printf("%d ", StackTop(&ps));
		//取完栈顶的数据，想取下一个，那就得删一下
		StackPop(&ps);
	}
	printf("\n");
	StackDestory(&ps);
	return  0;
}