当前位置:网站首页>2. (1) Chained storage of stack, operation of chain stack (illustration, comment, code)
2. (1) Chained storage of stack, operation of chain stack (illustration, comment, code)
2022-07-31 07:09:00 【Programmer who loves to play badminton】
本人坚持更新C语言和数据结构知识,可以收藏+关注随时了解
目录
1.结构体定义
The chain storage of the stack is mainly used两个结构体
A structure holds the top and bottom pointers of the stack
之所以这样,This is because the stack belongs to a linear list with limited operations,Operations on the stack can only be performed at the top of the stack
A structure is the storage node
结点包括数据域和指针域,类似于链表
typedef struct Node //结点
{
int data;
struct Node *pNext;
} Node, *PNODE;
// Node<=>struct Node
// PNODE <=>struct Node *
typedef struct Stack //Stores the top and bottom pointers of the stack
{
PNODE pTop; // pTopThe data type pointed to is struct Node
PNODE pBottom;
} STACK, *PSTACK;
//Stack<=>struct Stack
//PSTACK<=>struct Stack*
2.初始化一个链栈
2.1图解过程
(1)我们创建存放The structure of the pointer to the top of the stack and the bottom of the stack(That is, the structure of the stack),并动态创建一个结点,作为栈底,The pointer field at the bottom of the stack is empty
(2)初始状态下,栈顶指针(S.top)and the stack bottom pointer(S.bottom)都指向栈底
2.2代码
void initStack(PSTACK pS)
{
pS->pTop = (PNODE)malloc(sizeof(Node)); //Generate a node dynamically,使得pTop指针指向它,pTopHolds the address of the first byte of this node
if (NULL == pS->pTop)
{
printf("dynamic memory is failed to allocate,procedure is over!\n");
exit(-1);
}
else
{
pS->pBottom = pS->pTop; //让pBottom和pTop指向同一个结点
pS->pBottom->pNext = NULL; // pS->pTop->pNext = NULL;Make the pointer field at the bottom of the stack empty
}
}
3.压栈
Operations on the stack can only be performed at the top of the stack,So the point is to move the position of the top pointer on the stack,让S.Ptop指向栈顶元素
3.1图解过程
(1)Generate a node dynamicallypNew
(2)pNew指向栈底,栈顶指针指向pNew
(3)以此类推
3.2代码
void pushStack(PSTACK pS, int val)
{
PNODE pNew = (PNODE)malloc(sizeof(Node));
pNew->data = val;
pNew->pNext = pS->pTop; // pS->pTop不能改成pS->pBottom
pS->pTop = pNew; // pTop指向pNew
}
4.出栈
4.1.图解过程
Popping is the reverse process of pushing,只需要将S.pTop指针下移,Then release the memory of the deleted node
4.2代码
/把pS所指向的栈出栈一次,并把出栈的元素存入pVal形参所指向的变量中
bool pop(PSTACK pS, int *pVal)
{
if (empty(pS))
return false;
else
{
PNODE r = pS->pTop;
*pVal = r->data;
pS->pTop = pS->pTop->pNext; // ps->pTop=r->pNext
free(r);
r = NULL;
return true;
}
}
5.栈的判空
栈空的条件为,The stack top pointer and the stack bottom pointer point to the same memory location
bool empty(PSTACK pS)
{
if (pS->pBottom == pS->pTop)
{
return true;
}
else
{
return false;
}
}
6.栈的遍历
6.1图解过程
1.Define a structure pointer to point to the top of the stack,和S.pTop指向同一个位置
2.Every time an element is read it will bepmove down once,直到pThe pointer field to the node pointed to is NULL
6.2代码
void traverse(PSTACK pS)
{
PNODE p;
p = pS->pTop;
cout << "stack's datas are:" << endl;
while (p->pNext != NULL)
{
cout << p->data << endl;
p = p->pNext;
}
}
边栏推荐
- 服务器和客户端信息的获取
- QFileInfo常规方法
- Oracle入门 07 - Linux 操作系统安装配置(REHL 7.x)
- 4-1-7 二叉树及其遍历 家谱处理 (30 分)
- postgresql源码学习(34)—— 事务日志⑩ - 全页写机制
- LeetCode brush # 376 # Medium - swing sequence
- What is float?What is document flow?Several ways and principles of clearing floats?What is BFC, how to trigger BFC, the role of BFC
- Oracle入门 02 - IT软硬件平台及操作系统介绍
- 2.(1)栈的链式存储、链栈的操作(图解、注释、代码)
- Zotero | Zotero translator插件更新 | 解决百度学术文献无法获取问题
猜你喜欢
随机推荐
Analysis of the implementation principle and detailed knowledge of v-model syntactic sugar and how to make the components you develop support v-model
LVM和磁盘配额
Some derivation formulas for machine learning backpropagation
Oracle入门 11 - Linux 开关机及系统进程命令
【云原生】-Docker容器迁移Oracle到MySQL
安装和使用uView
【并发编程】ReentrantLock的lock()方法源码分析
编辑时过滤当前节点及根据限制的层数过滤数据
es6数组/数组对象求并集、交集、差集、去重、排序
Shell编程规范与变量
TCP/IP协议和互联网协议群
04-SDRAM:读操作(突发)
Dart入门
安装gstreamer开发依赖库到项目sysroot目录
线程中断方法
Database Principles Homework 2 — JMU
Install the gstreamer development dependency library to the project sysroot directory
shell的脚本的基本用法
Analysis of pseudo-classes and pseudo-elements
Hook API