从0开始的（c语言）数据结构学习 3：栈

2023-11-16

注：本文以造轮子为主，属于相对理论性、教学性的东西

在实际使用中，如果你是c++，请直接 #include < stack > ！！！！！！！

理解：什么是栈？

你现在有一个放网球的竖球筒，每次你放进去的球都会放在最上面，同理，当你要取出来一个球的时候，也只能取出来最上面的球。

在这里插入图片描述

栈就是相同的道理，它遵从先进后出，后进先出的原则。

对于这个球筒，我们有以下几个常用的方法：

初始化（创建一个球筒）
入栈（在球筒顶部塞一个球进去）
出栈（在球筒顶部拿一个球出来）
取栈顶（看看球筒顶部的球的值，请分清和出栈的关系）

（本质上只有这四个操作，你也可以做一些类似清空栈的操作）
（注：本文为链栈，你也可以以顺序的方式尝试实现栈）

具体代码

注：本代码没有包含main函数（我在其中加入了一些很具体的注释来帮助理解，如果喜欢读代码的朋友可以直接看）
注2：如果你不想纯粹读代码，该代码所有的具体解释请下移

#include<iostream>
#include<fstream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;

typedef struct StackNode {
	SElemType data;//链栈的数据域
	struct StackNode *next;//指针域
} StackNode, *LinkStack;


Status InitStack(LinkStack &S)//初始化栈
{ 
	S = NULL;//简单吗？
	return OK;
}

Status Push(LinkStack &S, SElemType e) //入栈：在栈S顶部插入元素e，在这里SELemType是char
{
	LinkStack p;
	p = new StackNode; //为要加入的结点new空间
	p->data = e; //新结点数据域e
	p->next = S; //将新结点插入栈顶
	S = p; //修改栈顶指针为p
	return OK;
}

Status Pop(LinkStack &S, SElemType &e) //出栈：删除S的栈顶元素，用e返回其值
{
	LinkStack p;
	if (S == NULL)return ERROR; //判断栈是不是空的
	e = S->data; //获得栈顶元素e
	p = S; //保存当前栈顶元素到p，用于之后的释放
	S = S->next; //修改栈顶指针
	delete p; //释放
	return OK;
}

SElemType GetTop(LinkStack S) //取栈顶值，不删除栈顶
{
	if (S != NULL) return S->data; //如果栈此时不为空，就返回栈顶元素
}

对于代码的具体解释

1，前设_宏定义

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;

和之前的宏定义几乎没有区别，最多就改了个别称SElemType.

2，前设_结构

typedef struct StackNode {
	SElemType data;//链栈的数据域
	struct StackNode *next;//指针域
} StackNode, *LinkStack;

由于我们使用的是链栈，本质上和链表差不多。同理这里的数据域可以换为结构，在面向对象中可以改为类。但在实际使用中请直接include stack

3，函数_初始化

Status InitStack(LinkStack &S)
{ 
	S = NULL;
	return OK;
}

简单吗？

4，函数_入栈

Status Push(LinkStack &S, SElemType e)
{
	LinkStack p;
	p = new StackNode; 
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}

【作用解释】

在链栈顶部插入新的结点e

思路：

为新的结点开个空间

	LinkStack p;
	p = new StackNode;

把新的结点放到球筒的顶部
p->data = e;
使新的结点作为栈的顶部

	p->next = S;
	S = p;

在这里，p的next为S，意思是最上面的球，永远是第一个，我们取的时候也是先取它。这样来写就能符合先出后进，先进后出的原则了。

5，函数_出栈

Status Pop(LinkStack &S, SElemType &e)
{
	LinkStack p;
	if (S == NULL)return ERROR; 
	e = S->data; 
	p = S; 
	S = S->next; 
	delete p;
	return OK;
}

【作用解释】

将链栈顶部的结点输出到e并删去。

思路：

判断栈是不是空，如果栈已经空了，我们也就没法从球筒里往外拿球了,此时返回ERROR
if (S == NULL)return ERROR;
拿一个球出来
e = S->data;
现在栈顶是刚刚拿走的球的下一个球了。
p = S; S = S->next;
删除我们已经拿走的球占用的空间。
delete p;

6，函数_取栈顶值

SElemType GetTop(LinkStack S)
{
	if (S != NULL) return S->data; 
}

判断是不是空，不是空就输出栈顶的数据域就好了。（S就是栈顶）

如果你是初学者：

没什么要实现的了，去力扣或者洛谷什么的刷刷题吧。

如果你想要没有注释的代码：

拿走，请。

#include<iostream>
#include<fstream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;

typedef struct StackNode {
	SElemType data;
	struct StackNode *next;
} StackNode, *LinkStack;

Status InitStack(LinkStack &S)
{ 
	S = NULL;
	return OK;
}
Status Push(LinkStack &S, SElemType e) 
{
	LinkStack p;
	p = new StackNode;
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}
Status Pop(LinkStack &S, SElemType &e)
{
	LinkStack p;
	if (S == NULL)return ERROR;
	e = S->data;
	p = S;
	S = S->next;
	delete p;
	return OK;
}
SElemType GetTop(LinkStack S)
{
	if (S != NULL) return S->data;
}
int main()
{
	return 0;
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)