一、栈的介绍
栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。
允许插入和删除运算的一端称作栈顶(top)。
不允许插入和删除的另一端称作栈底(bottom)。
在栈顶进行的插入操作称为入栈或进栈(push)
在栈顶进行的删除操作称为出栈或退栈(pop)
栈的特点:后进先出,即 LIFO(Last In First Out)
如下图:
顺序栈的数据类型
静态分配:
#define MaxSize 100 #define int ElemType typedef struct {
ElemType data[MaxSize]; // 数组存储空间 int top; //栈顶下标 } SqStack; // 顺序栈数据类型
MaxSize为顺序栈的最大容量;
top为栈顶元素的下标,0 <= top <= MaxSize-1
栈空:top = -1;
栈满:top = MaxSize-1
注意栈空和栈满的判断条件,如上图,栈顶top = 0 时,有数据元素a1,所以top = -1时,才能判断栈空。栈满时,由上图看知。
动态分配:
#define int ElemType typedef struct {
ElemType *base; //栈底的指针 ElemType *top; //栈顶的指针 } SqStack; // 顺序栈数据类型
链式栈的数据型
typedef struct LNode {
ElemType data; //数据域 struct LNode *next; //后继结点指针 } LinkStNode; //链栈结点类型
S:单链表头指针,指向头结点。
栈顶:单链表第一个元素结点的位置,即头结点的后一个位置。
二、顺序栈的基本运算
1、初始化栈
建立一个新的空栈s,实际上是将栈顶指示变量置-1即可。
//初始化空顺序栈 int InitStack(SqStack &S) {
S.top = -1; return 1; }
2、入栈:
①判断栈是否已满,若满则产生上溢出错误,退出算法,否则执行第②步;
②栈顶下标增一(top++),指向新的栈顶位置;
③将新元素置于栈顶。
//item是需要入栈的数据元素 bool Push(SqStack &S, ElemType item) {
if (S.top == MaxSize - 1) {
cout << "栈满" << endl; return false; } S.top++; S.data[S.top] = item; return true; }
3、出栈:
①判断栈是否为空,若空则产生下溢出错误,退出算法,否则执行第②步;
②栈顶元素出栈;
③栈顶下标减一(top++),指向新的栈顶位置;
bool Pop(SqStack &S, ElemType &item) {
if (S.top == -1) {
cout << "栈空" << endl; return false; } item = S.data[S.top]; S.top--; return true; }
4、判断栈是否为空
栈S为空的条件是s.top==-1。
//判栈空 int StackEmpty(SqStack &S) {
if(S.top==-1) return 1; else return 0; }
5、取栈顶元素
在栈不为空的条件下,将栈顶元素赋给e。
//取栈顶 int GetTop(SqStack &S, DataType &e) {
if(S.top <= -1) {
cout<<"栈空"<<endl; return 0; } item=S.items[S.top]; return 1; }
注意:
取栈顶元素和出栈不同,取栈顶元素只是把栈顶元素复制一份,栈顶指针并没有改变。如下图:
入栈时要判断栈是否满,出栈时要判断是否为空。
三、链式栈的基本运算
1、初始化栈
建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。
void (SNode *&s) {
s=(SNode *)malloc(sizeof(SNode));//s=new SNode; s->next=NULL; }
2、入栈:
bool Push(LinkStNode *S, ElemType item) {
//带头结点单链表的表头插入法 LinkStNode *t = new LinkStNode; //①生成新结点 if (t == NULL) {
cout << "内存不足"; return false; } t->data = item; //②在栈顶插入新结点 t->next = S->next; S->next = t; //③ return true; }
3、出栈:
bool Pop(LinkStNode *S, ElemType &item) {
//删除单链表的第一个元素结点 //①判断栈是否为空 if (S->next == NULL) {
cout << "栈空"; return false; } //②删除栈顶元素 LinkStNode *t = S->next; S->next = t->next; item = t->data; delete t; return true; }
4、销毁栈
//释放链栈 void Destroy(SNode *&s) {
SNode *p; while(s!=NULL) {
p=s; s=s->next; delete p; } }
5、判断栈是否为空
栈S为空的条件是s->next==NULL,即单链表中没有数据结点。
//判栈空 int StackEmpty(SNode *s) {
if(s->next==NULL) return 1; else return 0; }
6、取栈顶元素
int GetTop(SNode *s,DataType &e) {
if (s->next==NULL) //栈空的情况 {
return 0; } e=s->next->data; return 1; }
今天的文章
【数据结构与算法】栈的介绍及基本运算(出栈、入栈、销毁栈等)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/80960.html