栈的介绍与实现（详解）

一、什么是栈

栈（stack）是限定仅在表尾进行插入和删除的线性表。

二、栈的结构

栈顶（top）: 允许插入和删除的一端称为栈顶
栈底（bottom）：另一端为栈底
空栈：不含任何元素数据的栈称为空栈

栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

进栈：栈的插入操作，叫作进栈，也称压栈、入栈
出栈：栈的删除，叫作出栈，也有的叫作弹栈

如图：

三、栈的实现

我是以顺序存储结构实现的，你们还可以用链式存储结构实现

先创建栈的结构体

a：指向栈的起始地址
top:指向栈的顶端
capacity：表示栈的容量

我们在传数据时不知道要传的数据有多少个，所以我们capacity来记录容量的大小，来判断是否要扩容。

typedef int STDataType;
1

truct stack
{
	STDataType *a;//栈
	int top;//栈顶
	int capacity;//容量

};
1
2
3
4
5
6
7

1.初始化栈，建立一个空栈

先开辟四个空间，并初始化栈中的数据，pst->top=0表示没有数据。

void InitStack(struct stack*pst)
{
	pst->a = (struct stack*)malloc(sizeof(struct stack)*4);
	pst->top = 0;
	pst->capacity = 4;

}
1
2
3
4
5
6
7

2.若栈存在，则销毁-栈的销毁

断言pst是否为空。
栈的空间是动态开辟的，当我们用完后就要释放着片空间，防止内存泄漏。

void DestroyStack(struct stack*pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;

}
1
2
3
4
5
6
7
8
9

3.栈的清空

把栈中的数据清空
EmptyStack()函数是判断栈是否为空
故断言一下

void ClearStack(struct stack*pst)
{
    assert(pst);
    assert(!EmptyStack(pst));
	while (pst->top--)
	{
		pst->a[pst->top] = 0;
	}
}
1
2
3
4
5
6
7
8
9

4.栈是否为空

如果pst->pot==0,则栈中没有元素

int EmptyStack(struct stack*pst)//判断栈是否为空
{
	assert(pst);
	return pst->top == 0;
		
}

1
2
3
4
5
6
7

5.返回栈顶元素

LenghtStack()函数是返回栈中元素的个数

int PotStack(struct stack*pst)
{
	assert(pst);
	assert(!EmptyStack(pst));		
	int x = LenghtStack(pst);
	return pst->a[x-1];
}
1
2
3
4
5
6
7

6.返回栈中元素的个数

int LenghtStack(struct stack*pst)
{
	assert(pst);
	return pst->top;//top的值就是元素的个数

}
1
2
3
4
5
6

7.进栈

进栈的时候要判断栈的空间是否足够，是否需要开辟空间
每次开辟都是以2倍的量开辟的，然后再进行入栈

void PushStack(struct stack*pst, STDataType x)
{
	if (pst->capacity == pst->top)
	{
		struct stack*tmp = realloc(pst->a, sizeof(struct stack) * 2*pst->capacity);//开辟新空间
		if (tmp == NULL)//判断空间是否开辟失败
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity = 2 * pst->capacity;
	}
	pst->a[pst->top] = x;//栈顶位置赋值
	pst->top++;//栈顶上移

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

8.出栈

出栈简单，只要pst->top–

void PopStack(struct stack*pst)
{
	assert(pst);
	assert(!EmptyStack(pst));
	pst->top--;
}
1
2
3
4
5
6