【图解数据结构】栈全面总结

作者：知心宝贝

2022 年 4 月 04 日
本文字数：1635 字
阅读完需：约 5 分钟

一、前言

学习目标：

掌握栈这种抽象数据类型的特点，在相应的实际问题中正确应用相关代码
掌握顺序栈、双栈、栈调用

二、基本概念

定义：只允许在一端进行插入或删除的线性表
栈顶（top） ：允许进行插入或删除的一端
栈底（bottom）: 与栈顶相对应的一端
特点： 先进后出

三、栈的表示和实现

1.顺序栈

定义：一组地址连续的存储单元依次存放自栈底到栈顶的数据元素
top :用来表示栈顶元素的位置
top==-1 表示空栈
top==NULL 表示栈不存在
top>stacksize 元素溢出

结构体定义：

#define n 500//定义顺序栈大小struct stack{    int top;//栈顶指针    int a[n];//顺序栈数组}SeqStack;

复制代码

2.链栈

结构体定义：

typedef struct node{    int data;//定义数据类型    struct node*next;//定义链栈
}ChaiinStack;

复制代码

特点：

链栈没有栈满问题，大小可以随时扩充
插入和删除在栈顶处实行
链式栈的栈顶在链头
与单链表存储结构一致，与顺序表逻辑结构一致

四、顺序栈的常见算法

动态图：

算法讲解：

push 入栈，指针 top 向上移动
pop 出栈，指针 top 向下移动

1.初始化

void InitStack(SeqStack *S){  /*构造一个空栈S*/    S->top = -1;}

复制代码

2.判空

/*顺序栈判栈空*/int IsEmpty(SeqStack *S) {     /*判断栈S为空栈时返回值为真，反之为假*/   return(S->top==-1?TRUE:FALSE); }

复制代码

3.判满

/*顺序栈判栈满*/int IsFull(SeqStack *S)  {   /*判断栈S为满栈时返回值为真，反之为假*/  return(S->top==Stack_Size-1?TRUE:FALSE);}

复制代码

4.顺序栈取栈顶元素

int GetTop(SeqStack *S,StackElementType *x){    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */  if(S->top == -1)      /*栈为空*/    return(FALSE);  else  {      *x = S->elem[S->top];      return(TRUE);  }  }

复制代码

5.顺序栈入栈

/*顺序栈出栈*/int Pop(SeqStack *S,StackElementType *x){    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */  if(S->top == -1)    /*栈为空*/    return(FALSE);  else  {      *x = S->elem[S->top];    S->top++;    /* 修改栈顶指针 */      return(TRUE);  }}

复制代码

6.顺序栈出栈

/*顺序栈出栈*/int Pop(SeqStack *S,StackElementType *x){    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */  if(S->top == -1)    /*栈为空*/    return(FALSE);  else  {      *x = S->elem[S->top];    S->top--;    /* 修改栈顶指针 */      return(TRUE);  }}

复制代码

五、双栈

算法详解：

两个顺序栈 stack1,stack2
顺序栈 1 从左到右依次入栈，top1++
顺序栈 1 从右向左依次入栈，top2--
栈满条件：top1+1==top2

1.双端顺序栈进栈操作

/*双端顺序栈进栈操作。*/int Push(DqStack *S, StackElementType x, int i){  /*把数据元素x压入i号堆栈*/  if(S->top[0]+1==S->top[1])    /*栈已满*/    return(FALSE);  switch(i)  {  case 0:    S->top[0]++;  S->Stack[S->top[0]]=x;  break;  case 1:    S->top[1]--;  S->Stack[S->top[1]]=x;  break;  default:  /*参数错误*/        return(FALSE)   }  return(TRUE);}

复制代码

2.双端顺序栈出栈操作

/*双端顺序栈出栈操作。*/int Pop(DqStack *S,StackElementType *x,int i){  /* 从i 号堆栈中弹出栈顶元素并送到x中 */  switch(i)  {  case 0:    if(S->top[0]==-1)  return(FALSE);    *x=S->Stack[S->top[0]];   S->top[0]--;  break;  case 1:    if(S->top[1]==M)  return(FALSE);    *x=S->Stack[S->top[1]];  S->top[1]++;  break;  default:    return(FALSE);  }  return(TRUE);}

复制代码

六、总结与提高

对于使用 C++编程来说，上文顺序栈的判空、判满、插入、删除等等一系列代码，不需要你完全掌握，C++的 STL 标准库中为你准备好了函数等你调用。

C++stack 头文件：

#include<stack>//#include<bits/stdc++.h>或者万能头文件using namespace std;

复制代码

C++stack 具体操作：

用 stack 定义 s 类（定义什么都可以，只要把 s 变成定义的字母就可以调用 C++中的函数）,具体使用方法为：

发布于: 2022 年 04 月 04 日阅读数: 20

原文链接:【http://xie.infoq.cn/article/cca943156940c5d581632321e】。文章转载请联系作者。

知心宝贝

关注

公众号：穿越计算机的迷雾 2022.03.07 加入

生于尘埃溺于人海死于理想高台

发布

暂无评论

创作场景

【图解数据结构】栈全面总结

一、前言

学习目标：

二、基本概念

三、栈的表示和实现

1.顺序栈

2.链栈

四、顺序栈的常见算法

1.初始化

2.判空

3.判满

4.顺序栈取栈顶元素

5.顺序栈入栈

6.顺序栈出栈

五、双栈

1.双端顺序栈进栈操作

2.双端顺序栈出栈操作

六、总结与提高

知心宝贝

评论