栈的定义和分类
栈是我们线性结构中的一种常见应用。在函数调用、内存分配等也常常跟栈打交道,栈可以简单的理解为是一种可以实现“先进后出”的存储结构。栈又分为静态栈和动态栈。静态栈以类似于数组方式存放,而动态栈以类似于链表的方式存放。
栈区(Stack)和堆区(heap)
栈区主要用于存放局部变量、定义的形参,在定义时局部变量或形参时由系统自动分配,在函数结束时由系统自动回收存储单元。
堆区主要通过new(常用于C++、Java中),malloc(用于C中)等动态开辟的存储块,函数结束时需要我们通过delete(c++中)、free(c中)手动释放
举例说明:
void f(int n)
{
int m;
char ch;
double *q=(double *)malloc(200);
}
其中的n,m,ch,q由栈区分配(由操作系统帮我们自动分配), 200由堆区分配(需要我们手动开辟一块存储单元)。
栈和堆表示的是分配数据的一种方式。静态的或局部变量它们是以压栈和出栈的方式分配内存的(这个就叫栈区),而动态内存它们是以一种叫堆排序的方式分配的内存(这个叫堆区)。笼统的讲:凡是静态分配的全部在栈里面分配, 凡是动态分配的全部在堆里面分配。
对栈进行操作的思路
先讲下思路:我们知道链表主要通过头指针(指向头结点的地址)来对链表中的其它结点进行操作,而头结点本身并没有实际含义(既没有存放有效节点,也没有存放有效节点的个数),但通过它却可以方便我们对链表进行相关操作,如链表的遍历:
void TraverseList(PNODE pHead)
{
PNODE p=pHead->pNext;//将头结点的指针域指向首结点(链表的第一个有效结点),并赋给指针变量p,此时p指向首节点的地址
printf("遍历整个链表:");
while(NULL!=p)//当p指向首节点的地址不为NULL(即链表不为空),循环输入个结点的值
{
//当p指向尾结点的地址时,可输出尾结点的值
//但此时尾结点指针域为NULL,将跳出while循环
printf("%d ",p->data);
p=p->pNext;//将p指向下一个结点的地址赋给p指针
}
printf("\n");
}
在这个对链表进行遍历的函数中,我们可以看到我们只需要一个头指针,就可以遍历整个链表。
同理,我们可以通过初始化造出一个空栈,产生头结点,进而对栈进行相关操作。
typedef struct Node //定义结点的数据类型
{
int data;//数据域
struct Node *pNext;//指针域
}NODE,*PNODE;
typedef struct Stack //定义一个Stack结构类型,它含有两个指针成员
{
PNODE pTop;//指向栈顶元素
PNODE pBottom;//指向栈底元素的下一个没有实际含义的元素
}STACK,*PSTACK;
伪算法:
1.造空栈
void init(PSTACK pS)
{
动态产生一个头结点, 并让pTop指向该节点;
让pTop和pBottom都指向头结点;
再让成员pBottom或pTop所指向头结点的指针域为空
}
2.压栈(也叫进栈)
void push(PSTACK pS,int val)
{
创建一个新临时结点;
把val赋给该节点的数据域;
让该新节点的指针域指向栈顶;
最后让该新节点成为新栈顶;
}
3.出栈
bool pop(PSTACK pS)
{
先判断栈是否为空;
临时保存一份栈顶结点;
让栈顶指针指向下一个结点的地址;
释放预先保存的栈顶结点所占的内存;
}
完整实例说明:
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node //定义结点的数据类型
{
int data;//数据域
struct Node *pNext;//指针域
}NODE,*PNODE;
typedef struct Stack
{
PNODE pTop;//指向栈顶元素
PNODE pBottom;//指向栈底元素的下一个没有实际含义的元素(头结点)
}STACK,*PSTACK;
void init(PSTACK);//产生一个没有实际含义的头结点,并让pTop和pBottom都指向该头结点
void push(PSTACK,int);//压栈(即进栈)
void traverse(PSTACK);//遍历
bool pop(PSTACK);//出栈
int length(PSTACK);//求栈的长度
bool clear(PSTACK);//清空栈
int main()
{
STACK S;//STACK等价于struct Stack,为变量S分配内存,其中变量S含两个成员pTop,pBottom
init(&S);//目的是造出一个空栈,产生一个头结点,以便对栈就行操作
push(&S,1);
push(&S,2);
push(&S,3);
traverse(&S);
pop(&S);
traverse(&S);
printf("栈的长度为:%d\n",length(&S));
clear(&S);
printf("清空后:");
traverse(&S);
push(&S,7);
push(&S,5);
push(&S,9);
printf("进栈后:");
traverse(&S);
return 0;
}
void init(PSTACK pS)//造空栈
{
pS->pTop=(PNODE)malloc(sizeof(NODE));//产生头结点,并让pTop指向该头结点
if(NULL==pS->pTop)
{
printf("动态内存分配失败!\n");
exit(-1);//终止程序
}
pS->pBottom=pS->pTop; //让pTop和pBottom都指向头结点
pS->pBottom->pNext=NULL;
}
void push(PSTACK pS,int val)
{
PNODE pNew=(PNODE)malloc(sizeof(NODE));//创建新临时节点
if(NULL==pNew)
{
printf("动态内存分配失败!\n");
exit(-1);//终止程序
}
pNew->data=val;
pNew->pNext=pS->pTop;
pS->pTop=pNew;
return;
}
void traverse(PSTACK pS)
{
PNODE p=pS->pTop;
while(p!=pS->pBottom)
{
printf("%d ",p->data);
p=p->pNext;
}
printf("\n");
}
bool pop(PSTACK pS)
{
if(pS->pBottom==pS->pTop)
{
printf("栈为空,无法进行出栈操作!\n");
return false;
}
PNODE p=pS->pTop;
printf("出栈元素为:%d\n",p->data);
pS->pTop=p->pNext;
free(p);
p=NULL;
return true;
}
int length(PSTACK pS)
{
int len=0;
if(pS->pBottom==pS->pTop)
{
printf("栈为空! ");
return 0;
}
PNODE p=pS->pTop;
while(p!=pS->pBottom)
{
++len;
p=p->pNext;
}
return len;
}
bool clear(PSTACK pS)
{
if(pS->pBottom==pS->pTop)
{
printf("栈为空,清空失败! \n");
return false;
}
PNODE p=pS->pTop,q;
while(p!=pS->pBottom)
{
q=p->pNext;
pS->pTop=q;
free(p);
p=q;
}
pS->pTop=pS->pBottom;
return true;
}
注意:
1.free(p); 删除的是p指向的那个结点所占的内存,而不是删除p本身所占的内存;释放结点目的主要是为了防止内存泄露(这不像Java,有垃圾回收机制---由垃圾回收器自动帮你回收)。
2.pBottom始终指向的是栈底元素的下一个没有实际含义的元素(头结点),头结点是我们人为造出来的,并不存放有效数据;添加struct Stack(含两个成员pTop、pBottom)这个结构体的目的主要是为了方便我们对栈进行操作。
3.初始化时,让pTop和pBottom都指向头结点的目的:一是让它们初始化时所指向的内存地址相同,在整个程序运行过程中,让pBottom始终指向pTop的初始地址,也就是头结点的地址。这样就可以通过pS->pBottom==pS->pTop?是否成立来判断pTop是否指向初始化时原头结点(不存放有效数据的,为方便对栈进行操作的附加结点)的地址,即可以判断栈是否为空,因为如果栈含有有效元素的话,那么pTop必定存放的是新元素的地址。
4.结构体Stack成员pBottom的好处主要有:一是在初始化造空栈时,指向头结点;二是可以在pS->pBottom==pS->pTop成立时判断栈为空。 结构体Stack成员pTop的好处主要有:一是和pBottom一样,在初始化造空栈时,指向头结点;二是通过pTop来对栈中有效元素进行压栈、出栈、遍历等相关操作。
结束语
有关对线性结构中的栈操作今天就写到这了,明天开始学习线性结构常见应用中的队列。
分享到:
相关推荐
Java中栈内存和堆内存详解,非常容易理解
我开始饿时候一直对java的堆栈之间的关系有点模糊,虽然能说出来他之间的区别,但是并么有理解内涵。后来仔细研究了下这个问题,还单独米勒jvm的书看,自己也有了些许深入的掌握,我在这里面用了些例子说明,可能...
LwIP协议栈源码详解,讲解非常详细,深入理解TCPIP协议栈
很好的解释了Java中内存的分配,使用,和回收的一些过程,让我们在理解和开发是能够的心应手。
1、熟悉栈的原理和实现方式; 2、理解使用栈消除函数递归调用的原理; 3、掌握后缀表达式计算的方法。
JavaScript 栈 栈是一种遵从先进后出(LIFO)原则的有序集合。 新添加或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。 在栈里,新元素都靠近栈顶,旧元素都接近栈底 昨天因为有点事没有更新,今天...
栈是什么,你可以理解为一种先入后出的数据结构(First In Last Out),一种操作受限的线性表。下面这篇文章主要给大家介绍了Python中栈的应用实战,文中给出了多个实例,需要的朋友可以参考借鉴,下面来一起看看吧...
自己移植的,基于STM32F103 + ENC28J60 + uip1.0实现TCP数据传输,并实现了TCP保活功能,可以断线重连。源码中有比较详细的中文注释,帮助大家理解!
主要介绍了java 中的堆内存和栈内存的知识,有需要的朋友可以参考下
Linux内核解析是指对Linux操作系统的内核进行深入分析和理解的过程。Linux内核是操作系统的核心部分,负责管理计算机硬件资源、提供系统调度和进程管理、实现设备驱动程序等关键功能。 Linux内核解析可以涉及以下...
2019最新深入理解JVM内存结构及运行原理(JVM调优)高级核心课程视频教程下载。JVM是Java知识体系中的重要部分,对JVM底层的了解是每一位Java程序员深入Java技术领域的重要因素。本课程试图通过简单易懂的方式,系统...
种攻击,目的就在于:当程序没有对缓冲区溢出做足够防范时,立交 攻击者可能会如何利用这些安全漏洞 ;通过实验,能更好的理解写 出安全的程序的重要性,也能了解到一些编译器和操作 ;以及系统 提供的帮助改善...
栈区存放变量名与变量值内存地址的映射关系,可以简单理解为变量名存储内存地址。 堆区存储变量值。 变量名的赋值与传参所传递的都是引用,即栈区的数据。 栈区的数据是变量名与内存地址的映射关系,即对值的引用。 ...
文档中介绍了: 寄存器 栈 堆 静态域 常量池 帮助java学习者从本质上理解java的运行机制。
而要实现ARP、IP、TCP等功能,则需要对相关协议的理解,由编写相关协议或移植协议栈来实现。 功能描述 1、总线 总线是ISA总线兼容模式,8个IO基址,分别是300H, 310H,320H, 330H, 340H, 350H, 360H, 370H。IO基址...
就像BSD操作系统中的IPv4协议栈源代码极大地帮助了人们理解互联网是如何工作的一样,就像[Ste94](《TCPIP详解》)极大地帮助人们理解BSD网络协议栈的实现一样,本书从规范到KAME软件实现来描述IPv6。 这一节,我们...
数据结构教程》根据高等院校计算机专业数据结构课程的教学大纲要求,结合十年... 《数据结构教程》适合于作为计算机及相关专业应用型本科或专科的教材,也适合于计算机专业水平考试、成人教育、自学考试的人员参考。
对后四种文件的理解很重要,其作用解释如下: (1) 链接脚本文件:在程序编译时起作用。该文件描述代码链接定位的有关信息,包括代码段,数据段,地址段等,链接器必须使用该文件对整个系统的代码做正确的定位...
flask源码的请求处理整个流程,栈管理,上下文管理等,本文档是个人学习心得,总结得非常详细,读完可以理解flask如何运作
细致入微的讲解了TCP/IP协议栈的各个协议,通过本书的学习,对TCP/IP的理解会有很大的提高,一本值得反复读、细读的好书。