如何使用C/C++语言实现栈(Stack)的操作

前言:用C语言写数据结构的唯一感觉就是操作内存时两边都是通透的,非常容易上溢出和下溢出,因此应该非常小心!

什么是栈?

在计算机中栈是一种抽象的数据结构,这种数据结构有一个特点:后入先出(Last in first out – LIFO)。因此,如果我们把栈本身给比作一个网球桶,而要入栈的元素比喻成网球的话大概就是这样的:

如果栈是网球桶的话...

I. 它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。

这是百度百科的解释让我们来细品一下:在这个网球桶中,如果你想要放入网球(push元素,压栈)只能(运算受限)从网球桶口放入,而如果你想拿出这个网球(pop元素,弹栈)只能原路挨个按顺序拿出,你不能把桶底扣个洞吧要不然桶就废了(害)。

II. 允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动

栈底简单的理解成网球桶的桶底,而栈顶则是网球桶的开口部分。

头文件的定义,需要什么来创建一个栈呢?

在C语言中我们可以用malloc函数在计算机的堆内存中申请一块逻辑连续的空间,而我们可以用指针来对这块空间进行操作。而要实现栈的操作我们需要2个指针和一个计数器来记录当前的栈总大小。

typedef int ELEMENT_TYPE;

typedef struct Stack
{
	//栈顶指针
	ELEMENT_TYPE* top;

	//栈底指针,在第一次初始化之后该指针不应该被修改
	ELEMENT_TYPE* base;

	//栈总空间长度,这个值不应该在非扩容销毁操作时修改
	int length;
} Stack;
栈图解

对栈的结构体进行声明之后我们应该对对应的几个栈相关函数进行声明:

//初始化虚拟栈在堆空间中,返回初始化是否成功状态;
bool initStack(Stack* s, int initSize);

//将虚拟栈从堆内存中删除并释放内存;
void clear(Stack* s);

//快速删除指定数量的元素,从栈顶开始删除;
bool removeAlot(Stack* s, int num);

//弹出一个元素;
ELEMENT_TYPE pop(Stack* s);

//放入一个元素,如果已经超过了初始容量则自动扩容,扩容后在将元素push进桶中,如果在堆内存中无法申请到内存则返回false;
bool push(Stack* s, ELEMENT_TYPE e);

//将当前的字符栈转化为ELEMENT_TYPE数组
bool toElementArray(Stack* s, ELEMENT_TYPE** dest);

//返回当前栈元素的个数
int stackLen(Stack* s);

//判断栈是否为空
bool isEmpty(Stack* s);

栈相关的函数实现

栈初始化函数(initStack)实现:

要想使用栈,我们首先得初始化栈(InitStack):

bool initStack(Stack* s, int initSize) {
	s->base = (ELEMENT_TYPE*)malloc(initSize * sizeof(ELEMENT_TYPE));

        //判断申请内存是否失败如果失败则退出初始化并返回状态
	if (s->base != NULL)
	{
		s->top = s->base;
		s->length = initSize;
		return true;
	}
	return false;
}

push函数的实现:

有了栈之后,我们可以要向这个栈中加入元素(push操作),我的这个实现可以自动扩容栈,即如果当前栈满则自动扩容,使用了memcpy函数,一次扩容20个元素的空间(其实最好是可以根据扩容次数增加动态调整每次扩容的量(以此减少对内存的频繁操作),参考java的ArrayList扩容方案,但是这里我就懒得写了)

bool push(Stack* s, ELEMENT_TYPE e) {
	//检测栈状态,如果栈被销毁了则终止操作
	if (s->length == -1)
	{
		return false;
	}
	//如果当前的元素快要超过虚拟栈的上限了的话,那么对该虚拟栈扩容
	if (s->top - s->base >= s->length)
	{
		//开始扩容
		ELEMENT_TYPE* temp = s->base;
		s->base = (ELEMENT_TYPE*)malloc(s->length * sizeof(ELEMENT_TYPE) + 20 * sizeof(ELEMENT_TYPE));
		if (s->base != NULL)
		{
			memcpy(s->base, temp, s->length * sizeof(ELEMENT_TYPE));
			s->top = s->base + s->length;
			s->length += 20;
			free(temp);
		}
		else
		{
			s->base = temp;
			return false;
		}
	}
	*(s->top) = e;
	++s->top;
	return true;
}

pop函数的实现:

比较简单,但是一定要注意判断栈是不是已经空了要不然会下溢出

ELEMENT_TYPE pop(Stack* s) {
	if (s->top - s->base < 1)
	{
		return -1;
	}
	return *(--s->top);
}

Clear销毁栈函数实现:

因为每一次释放内存都有释放旧栈空间所以直接释放当前空间即可。

void clear(Stack* s) {
	if (s->length == -1)
	{
		return;
	}
	free(s->base);
	s->top = (ELEMENT_TYPE*)NULL;
	s->length = -1;
}

批量元素删除函数实现:

这里我选择直接移动栈指针,快速删除。

bool removeAlot(Stack* s, int num) {
	if (s->top - s->base < num)
	{
		return false;
	}
	s->top -= num;
	return true;
}

还有几个我自己即兴写的几个函数,有兴趣可以看看

bool toElementArray(Stack* s, ELEMENT_TYPE** dest) {
	if (s->length == -1)
	{
		return false;
	}
	*dest = NULL;
	*dest = (ELEMENT_TYPE*)malloc((s->top - s->base) * sizeof(ELEMENT_TYPE));
	if (*dest == NULL)
	{
		return false;
	}
	memcpy(*dest, s->base, (s->top - s->base) * sizeof(ELEMENT_TYPE));
	return true;
}

int stackLen(Stack* s) {
	if (s->length == -1)
	{
		return 0;
	}
	return s->top - s->base;
}

bool isEmpty(Stack* s) {
	if (stackLen(s) == 0)
	{
		return true;
	}
	return false;
}
本篇文章由Rex创建并发布,若有转载文章的需求或发现内容错误、图片侵权等请发送邮件到:[email protected],本人高中生有可能回复没有那么及时,但是看到一定会第一时间处理回复的qwq。
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
下一篇