数据结构入门：栈

前言

1. 栈

1.1栈的概念及结构

1.2 栈的实现

前言

无论你是计算机科学专业的学生、程序设计的爱好者，还是正在准备面试的求职者，本文将为你提供一份全面而深入的栈和队列指南。让我们一起探索栈和队列的双重魅力，为你的编程之路增添新的色彩。

1. 栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

1.2 栈的实现

栈的实现方法有两种，一种是顺序表的栈，另外一种就是链表实现的栈。相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，所以这里我们使用顺序表来实现栈。

如果熟练顺序表和链表操作，那栈就会相当轻松，栈的入栈出栈就相当于是尾插尾删，顺序表尾插尾删的效率高，这也是使用顺序表实现的原因。

1.2.1 栈的定义

首先我们需要先定义一个栈：

typedef int Datatype;
typedef struct Stack
{
	Datatype* a;
	int top;
	int capacity;
}Stack;

栈中有栈顶（top），有栈的容量（size），还有存储的数据（a）；

1.2.2 栈的初始化

void InItStack(Stack* ps)
{
	assert(ps);
	ps->top = 0;
	ps->a = NULL;
	ps->capacity = 0;
}

这里对栈进行初始化时栈顶（top）可以置为-1，也可以置为0，置为0为了便于使用top作为数组下标插入数据。

1.2.3 入栈

栈已经定义完成并且进行了初始化，接下来就是入栈操作。这里与顺序表的尾插略微有些不同。

void StackPush(Stack* ps, Datatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		Datatype* tmp = (Datatype*)realloc(ps->a, sizeof(Datatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;//top初始化为0，可以直接作为数组下标
	ps->top++;//入栈后top++，便于统计元素个数和下次入栈
}

由于我们初始化时将栈的容量置为0，在这里我们在入栈操作时就需要进行开辟空间，但这里如果我们使用malloc开辟空间，就还需要进行扩容操作，所以我们直接使用realloc进行开辟空间。

realloc在扩容时，如果原始区域空间为0，那么它的作用就类似于malloc。

此外我们还需要有新开辟空间的大小，这里我们直接使用一个判断语句：newsize = (ps->size == 0 ? 4 : ps->size * 2); 如果size等于0就开辟4个存储数据的空间，如果不等于0就直接扩容为2倍。

1.2.4 出栈

出栈操作就很简单了，也不需要销毁，直接进行top--：

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

但我们需要注意栈为空的情况，所有使用assert强制检查，如果为空直接报错终止程序，简单粗暴。

1.2.5 栈的元素个数

统计栈的元素个数接口也很简单，top就是栈中元素的个数

int Stacksize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

1.2.6 栈顶数据

Datatype TopData(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

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

这个也非常简单，需要注意栈为空的情况。

1.2.7 栈的判空

bool IsEmpty(Stack* ps)
{
	assert(ps);
	return (ps->top == 0);
}

2.栈的应用

这些栈的基本操作我们已经实现了，接下来我们来实际应用一下。虽然栈的基本操作更为简单，但是栈在应用时数据的结构更加复杂，前边的顺序表和链表是栈和队列的基础。

2.1 题目一：括号匹配

这道题目我们可以使用数组实现并解决，但我们已经了解了栈，这道题目我们就使用顺序表栈来实现。我们可以直接复制上述栈基本操作的代码。将 typedef int Datatype;

改为：typedef char Datatype;

题目描述：

示例：

题目链接：

有效括号

2.1.1 思路

这道题目的思路很明确，入栈左括号，遇到匹配的右括号就出栈。如果最终栈为空就匹配成功。但匹配失败的情况有很多，接下来我们进行逐个分析。

2.1.2 分析

首先是入栈，如果为左括号就入栈，为右括号就匹配出栈。这里使用if…else语句更为简洁，入栈就需要我们调用入栈的函数接口。

其次就是匹配、出栈。但在匹配之前我们还需要考虑特殊情况，就是如果没有出栈元素就直接匹配的情况，所以首先我们需要有一个判空操作，如果匹配时栈就为空就直接匹配失败，并销毁栈，这个属于左括号与右括号数量匹配失败。

接着就是顺序匹配失败，这里就需要我们用到栈顶元素了，如果栈顶元素与匹配的括号不匹配就直接返回false，匹配失败，销毁栈。

最后，匹配结束，存放括号数组为空，栈也为空就匹配成功。

2.1.3 题解

匹配括号接口：

bool isValid(char* s) {
	Stack st;
	InItStack(&st);
	char top;
	while (*s)
	{
		if (*s == '(' || *s == '[' || *s == '{')
		{
			StackPush(&st, *s);
		}
		else
		{
			if(IsEmpty(&st))
			{
				DestoryStack(&st);
				return false;
			}
			top=TopData(&st);
			StackPop(&st);
			if((*s==']'&&top!='[')
			||(*s==')'&&top!='(')
			||(*s=='}'&&top!='{'))
            {
                DestoryStack(&st);
                return false;
            }
		}
        s++;
	}
	bool ret = IsEmpty(&st);
    DestoryStack(&st);
	return ret;
}

整体代码：

typedef char Datatype;
typedef struct Stack
{
	Datatype* a;
	int top;
	int size;
}Stack;

void InItStack(Stack* ps);

void DestoryStack(Stack* ps);

void StackPush(Stack* ps, Datatype x);

void StackPop(Stack* ps);

int Stacksize(Stack* ps);

Datatype TopData(Stack* ps);

bool IsEmpty(Stack* ps);

void InItStack(Stack* ps)
{
	assert(ps);
	ps->top = 0;
	ps->a = NULL;
	ps->size = 0;
}

void DestoryStack(Stack* ps)
{
	assert(ps);
	ps->top = ps->size = 0;
	free(ps->a);
	ps->a = NULL;
}
void StackPush(Stack* ps, Datatype x)
{
	assert(ps);
	if (ps->top == ps->size)
	{
		int newsize = (ps->size == 0 ? 4 : ps->size * 2);
		Datatype* tmp = (Datatype*)realloc(ps->a, sizeof(Datatype) * newsize);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->size = newsize;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
int Stacksize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
Datatype TopData(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
bool IsEmpty(Stack* ps)
{
	assert(ps);
	return (ps->top == 0);
}
bool isValid(char* s) {
	Stack st;
	InItStack(&st);
	char top;
	while (*s)
	{
		if (*s == '(' || *s == '[' || *s == '{')
		{
			StackPush(&st, *s);
		}
		else
		{
			if(IsEmpty(&st))
			{
				DestoryStack(&st);
				return false;
			}
			top=TopData(&st);
			StackPop(&st);
			if((*s==']'&&top!='[')
			||(*s==')'&&top!='(')
			||(*s=='}'&&top!='{'))
            {
                DestoryStack(&st);
                return false;
            }
		}
        s++;
	}
	bool ret = IsEmpty(&st);
    DestoryStack(&st);
	return ret;
}

栈相对于链表和顺序表没有那么多的操作，更为简单，但在实际应用时数据结构更加复杂，但是别担心，后续学习C++后可以直接使用现成的库函数，不需要再对栈的各个操作进行实现。

总结

栈是一种重要的数据结构，它以后进先出的方式操作数据。栈在递归算法、表达式求值、函数调用等场景中发挥着重要作用。通过学习栈，我们能够更好地理解数据结构的本质和算法的设计思想。栈不仅仅是一种数据存储的方式，更是一种思维方式和问题解决的工具。无论是计算机科学的学习者、程序设计的爱好者，还是正在准备面试的求职者，通过探索栈的原理和应用，我们能够提升自己的编程能力和解决问题的能力。让我们一起深入探索栈的魅力，为编程之路增添新的色彩。最后，感谢阅读！