数据结构 栈的基本概念和实现

数据结构 栈的基本概念和实现

越行勤 1,231 2021-03-19

数据结构的三要素-- 逻辑结构、数据的运算、存储结构（物理结构）

栈

我们先复习一下线性表，线性表就是 具有相同的数据类型的n（n>=0）个数据元素的有限队列，其中n为表长.

栈（Stack）：是一种特殊的线性表，只允许在一端进行插入和删除操作的线性表，就和我们的羊肉串一样，串的时候，第一个羊肉垫底，吃的时候最后一个穿入的肉肉第一个被吃。

术语

栈顶，栈底，空栈。

术语
  • 栈顶 允许插入和删除的一端
  • 栈底 ：禁止插入和删除的一端
  • 空栈：没有数据元素的栈

栈的特点 ： LIFO, Last In First Out 先进后出

栈的基本操作

  1. InitStack(&S) 初始化一个空栈
  2. DestroyStack(&S) 销毁一个栈
  3. ClearStack(&S) 清空一个栈
  4. Emptystack(S) 判断栈是否为空
  5. GetTop(S) 获取栈顶数据
  6. Push(&S,e) 将e推入栈中，作为新的栈顶
  7. Pop(&S,&e) 推出S的栈顶元素，并用e返回

其中出栈 Pop和入栈在Push是栈的核心操作。

分析采用如何存储结构

当然栈作为逻辑结构实现它有两中方法，顺序栈和链式存储.

通过以上，我们可以得知，栈经常操作的栈的栈顶元素，没有在其他位置插入和删除元素，并没有体现出链式存储结构的优势，所以顺序表是非常适合的存储结构。当然在没有限制使用连续的空间下，个人认为顺序存储结构是一个不错的选择，所以本篇探讨如何 使用顺序存储结构实现 栈。

由于栈的操作没有链表的操作多，显然实现起来就简单许多。

判断多少种合法出栈顺序问题

题目：如果入栈顺序为 A ,B，C, D，那么出栈顺序可能为 A D C B 吗

解题， 假设A，进栈，然后立马出栈。随后 BCD 一次进栈， 那么出栈顺序一定为 DCB，所以上述方式合法。

当然也有不合法的，例如 ADBC就不合法。N个不同元素按顺序进栈，那么出栈顺序有 （1/n+1）Cn2n

种可能。

实现---动态顺序栈

顺序栈又可以分为静态（最大空间不可以改变），和动态，当然这里讨论的为 动态

实现的基本操作无非就是，创销增删改查

image-20210318175144569

定义

我们既然使用顺序结构，那么就规定 连续存储结构的第一个位置为栈底，使用指针base指向 ；末尾作为栈顶，使用top指向；同时我们为了方便增大容量可以使用 stacksize 存储当前栈的容量.

如果栈使用数组存储，那么0号元素被base指向，top指向数组最后一个元素的下一个空位，方便下次存储数据。

#define InitSize 100 // 初始栈大小
#define Addsize 10   //每次增加栈创建的大小

typedef struct {
	ElemType* base, * top;// 栈的基址（栈底指针）和 栈顶指针
	int stacksize; //栈的大小
}SqStack;

Init初始化

我们规定 base == NULL时，栈不存在。规定空栈时候 top==base,每次插入一个元素，top向下移动一个位置。

bool Init_SqStack(SqStack& S)
{
	S.base = (ElemType*)malloc(InitSize * sizeof(ElemType));
	if (!S.base)return false; //大小开辟失败 
	S.top = S.base;
	S.stacksize = InitSize;
	return true;
}

GetTop 获取栈顶元素

获取栈顶元素，栈顶元素被 top-1 指向

bool GetTop(SqStack S, ElemType& e)
{
	if (S.base == NULL)
		return false;
	e = *(S.top - 1);
	return true;
}

Push元素入栈

推入元素的时候，为了算法的健全性，我们不仅要检查栈是否存在，如果存储空间不够（S.top-S.base>=stackSize）了还需要用relloc函数添加Addsize大小的空间.当然使用realloc，记得注意事项哦！C语言 realloc注意事项

bool Push(SqStack& S, ElemType e)
{
	if (S.base == NULL)
		return false;
	if (S.top - S.base >= S.stacksize)//空间不够了，增加空间
	{
		int* new_base = (ElemType*)realloc(S.top, (S.stacksize + AddSize) * sizeof(ElemType));
		if (!new_base) return false;
		S.base = new_base;
		S.stacksize += AddSize;
	}
	*S.top++ = e;//先赋值后++
	return true;
}

Pop 元素出栈

元素出栈，只需要改变top的指向，向后退一个即可,并且带回元素。当然也要考虑栈为空栈，就无需出栈了。

bool Pop(SqStack& S, ElemType& e)
{
	if (S.base == NULL)
		return false;
	if (S.base == S.top) return false;
	e = *--S.top;//先减减再取出元素
	return true;
}

参考代码

# include<stdio.h>
# include<stdlib.h>

# define InitSize 100
# define AddSize 10

typedef struct {
	int* base, * top;// 栈的基址（栈底指针）和 栈顶指针
	int stacksize; //栈的大小
}SqStack;

bool Init_SqStack(SqStack& S);
bool GetTop(SqStack S, int& e);
bool Push(SqStack&S, int e);
bool Pop(SqStack&S, int& e);

void test()
{
	SqStack S;
	int e;
	Init_SqStack(S);
	printf("入栈数据 1--10\n");
	for (int i = 1; i <= 10; i++)
		Push(S, i);
	printf("出栈5个数据\n\n");
	for (int i = 1; i <= 5; i++)
	{
		Pop(S, e);
		printf("此时 数据 ：%3d 出栈\n", e);
	}
	printf("先进后出\n\n");

	getchar();
}

int main()
{
	test();
	return 0;
}

bool Init_SqStack(SqStack& S)
{
	S.base = (int*)malloc(InitSize * sizeof(int));
	if (!S.base)return false;
	S.top = S.base;
	S.stacksize = InitSize;
	return true;
}

bool GetTop(SqStack S, int& e)
{
	if (S.base == NULL)
		return false;
	e = *(S.top - 1);
	return true;
}

bool Push(SqStack& S, int e)
{
	if (S.base == NULL)
		return false;
	if (S.top - S.base >= S.stacksize)//空间不够了，增加空间
	{
		int* new_base = (int*)realloc(S.top, (S.stacksize + AddSize) * sizeof(int));
		if (!new_base) return false;
		S.base = new_base;
		S.stacksize += AddSize;
	}
	*S.top++ = e; //先赋值再++
	return true;
}

bool Pop(SqStack&S, int& e)
{
	if (S.base == NULL)
		return false;
	if (S.base == S.top) return false;
	e = *--S.top; //先-- 再赋值
	return true;
}
数据结构