数据结构：栈

一.栈的概念

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

虽然栈看上去是一个新的名词，但是它比之前学的链表，顺序表可简单太多了。

栈还有两个新的名词：

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

我们把这个就看做是栈。
把一个数据添加进去叫做入栈，注意看这里是从栈顶开始放元素进去的。
这个将元素删除的动作就是出栈，同理这也是从最上面也就是栈顶开始删除元素的。这就是所谓的后进先出。

这就相当于子弹压膛，子弹一个一个压进去，但是打出去的子弹确实最后一个压进去的子弹。

二.栈的实现

栈的实现一般可以使用数组或者链表实现，但是我们通过对比顺序表和链表，可以发现顺序表的尾插尾删比较简便，链表的头插头删比较简便。而我们的栈恰好只能尾插尾删，这也就意味着栈的实现用数组(顺序表)来实现更优。

如果你非要用链表来实现也不是不行，此时你把链表尾部当成栈底，头部当成栈顶就行，这样的话头插头删也可以当成栈的入栈出栈。

2.1定义栈

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int capacity; //栈空间大小
	int top; // 栈顶
}Stack;
1
2
3
4
5
6
7

首先我们要定义好一个结构体，这个结构体里面的指针a代表我们即将要开辟的栈空间的地址，capacity代表的是我们栈空间的总容量，top代表的是栈顶的位置。

2.2栈的初始化

// 初始化栈
void StackInit(Stack* ps)
{
	//首先要保证传进来的指针不为空
	assert(ps);

	//刚开始为栈提前开辟4个元素的空间
	ps->a = (STDataType*)malloc(4 * sizeof(STDataType));
	if (ps->a == NULL)
	{
		perror("StackInit");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0; //这里top指向栈顶元素的下一个位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在此之前我们可以定义好一个结构体变量，现在我们就可以对这个结构体初始化了。

我们一开始初始化的时候给栈开辟4个整型大小的空间，当然这些空间你是可以随便写的。

因为开辟的空间是4，所以初始化时capacity的大小就改成4.

top初始化的大小一般有两种写法：

ps->top = 0;
1

此时top代表的是栈顶元素的下一个位置，刚开始栈的内容为0，也就是没有放元素进去，所以top就为0。没放一个元素top++就往后跳一格。有没有发现这时候top的大小和元素个数的大小其实是等价的。

但是还有一种写法：

ps->top = -1;
1

这是top指向的位置就是栈顶元素的位置，初始化成-1说明刚开始栈里还没有元素，所以top的值应该是0-1，每加一个元素top++.

这里top本身就是一个整型变量不是指针，我在上面图中画箭头是为了让你们清晰的看到top代表的哪个位置，top可以理解为数组的下标。

2.3入栈

//入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//在栈尾添加一个元素

	//首先判断需不需要扩容
	if (ps->capacity == ps->top)
		//相等说明此时元素个数已经和总容量相等了，如果在添加元素需要扩容
	{
		//扩容为原来的两倍
		STDataType* cap = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (cap == NULL)
		{
			perror("StackPush");
			exit(-1);
		}

		ps->a = cap;
		ps->capacity *= 2;
	}

	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
21
22
23
24
25

我们在入栈也就是添加元素时，首先要判断需不需要扩容，因为这是malloc开辟的，刚开始只有四个元素的大小，如果我们要添加的元素个数比4大，这时肯定是要先扩容的。扩容的大小，我们固定一点，每次增加为原来的2倍。

判断是否要扩容之后在添加元素。因为刚开始初始化时ps->top初始化成0，也就意味着top表示的下标就是当前元素的下一个位置。要入栈时这个位置填入先加入的元素即可：

ps->a[ps->top] = data;
1

添加完之后不要忘了top往后加1.

2.4出栈

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈里面没有元素了，就不能进行出栈的操作
	assert(ps->top);

	ps->top--;
}
1
2
3
4
5
6
7
8
9

此时我们不仅要判断指针是否为空，还要判断栈里的元素是否为空，如果是空的话，出栈也就没意义了。

出栈的代码非常简单top–就行。

如果top代表的是栈顶元素的下一个位置，此时3就是栈的栈顶，虽然我们没有把4直接删掉，但是我们的目光已经不在他身上了。

2.5检测栈是否为空

//检测栈是否为空，如果为空返回true，如果不为空返回false
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
1
2
3
4
5
6

如果栈是空的话ps->top == 0这个表达式就为真，所以返回true。同理不为空的时候这个表达式就为假，所以返回false.

2.6获取栈顶元素

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));
		//如果栈的数据是0的话，下面访问的就是ps->a[-1],造成数组越界访问
	return ps->a[ps->top - 1];
}
1
2
3
4
5
6
7
8
9

因为top代表的是栈顶下一个元素的位置，top-1也就代表着栈顶元素的位置，现在直接返回就行。

加入此时栈里的元素为空也就是说top-1为-1如果一个数组访问到下标为-1的位置说明此时已经造成数组越界了，所以要提前断言，StackEmpty()函数是刚写的判断链表是否为空的函数，前面加个!是逻辑非运算，如果为空返回的是真在前面加个!，意味着此时assert里面的内容是假，这时候就会报错。

2.7获取栈的有效个数

//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5
6

在栈的初始化时就说过top其实和栈的元素个数其实是等价的，所以这里直接返回top就行。

2.8打印栈的元素

//打印栈中的元素
void StackPrint(Stack* ps)
{
	assert(ps);

	for (int i = 0; i < ps->top; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

和普通数组一样，直接遍历打印就行。

2.9销毁栈

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
1
2
3
4
5
6
7
8

因为栈是用malloc在堆区开辟的，用完之后程序不会主动释放，需要我们自己手动释放。

三.总结

看到这里可以看到，栈和链表那些相比，简直不知道简单多少。现在我再来几道关于栈的题目，让你们更好的理解入栈出栈的概念

题目：
因为后入先出，这题答案就是B。

题目：
这题稍微麻烦一点，但仔细想想也能看出来，首先元素不是所有的都放进去，然后在一个一个全出了，有可能再放一个元素之前，以前的元素也会出来。

先看A选项：

先把1放进去，然后1再出来，出来之后依次放2，3，4放完之后按后入先出的规律，4，3，2依次出来，所以顺序1，4，3，2是有可能的。

再看B选项：

先放1，再放2，放完2后，2在出来，出来后放3，3放进去之后3再出来，同样4放进去后4再出来，最后就剩个1了，最后1再出来。所以顺序2，3，4，1也是可以的。

看C选项：

先放1，2，3，放完后把3取出来，此时栈里还是1，2但是C的顺序是3出来后，1再出来。但是现在看1好像被2挡着了，只有2出来之后1才能出来。所以C选项的顺序是不可以的。

最后看D选项：

先放1，2，3然后3在取出来，再放4，4放进去之后4在取出来，最后剩1，2然后后入先出，先出2，在出1.所以3，4，2，1也是可以的。