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

我们先复习一下线性表,线性表就是 具有相同的数据类型的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;
}

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://yingwiki.top/2021/03/19/stack
最后更新于:  35  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟