备案控制台
开发者社区 人工智能 文章 正文

数据结构— —栈的基本操作（顺序栈和链栈）

2024-03-06 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构— —栈的基本操作（顺序栈和链栈）

🎯目的：

1、掌握栈的顺序表示和实现。

2、掌握栈的链式表示和实现。

🎯内容：

1、栈的顺序表示和实现。

2、栈的链式表示和实现。

🎯环境：

TC或VC++。

🎯顺序栈步骤：

🎐1.栈的顺序表示和实现

编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：


  1. 1初始化顺序栈


  1. 2插入元素


  1. 3删除栈顶元素


  1. 4取栈顶元素


  1. 5遍历顺序栈


  1. 6置空顺序栈


🎆注意要点：

顺序栈，入栈时需判断栈是否为满，栈满时不能入栈，否则出现空间溢出；出栈时需判断栈是否为空，为空时不能操作，否则产生错误；取栈顶元素与遍历之前也要判断栈是否为空。

typedef struct {
 
       SElemType *base;//栈底指针
 
       SElemType *top;//栈顶指针
 
       int stacksize;//栈可用的最大容量
 
} SqStack;

🎯顺序栈完整代码：

//顺序栈
#include "iostream"
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0;
#define OVERFLOW -1
typedef int Status;
typedef char SElemType ;
typedef struct{//定义顺序栈 
  SElemType *base;
  SElemType *top;
  int stacksize;
}SqStack;
Status InitStack(SqStack &S){//顺序栈的初始化 
  S.base=new SElemType [MAXSIZE];
  if(!S.base)
  exit(OVERFLOW);
  S.top=S.base;
  S.stacksize=MAXSIZE;
  return OK; 
}
Status Push(SqStack &S,SElemType e){//顺序栈的入栈 
  if(S.top-S.base==S.stacksize)
  return ERROR;
  *S.top++=e;
  return OK;
}
Status Pop(SqStack &S,SElemType &e){//顺序表的出栈 
  if(S.top==S.base)
    return OK;
  e=*--S.top;
  return OK;
}
SElemType GetTop(SqStack S){//取栈顶元素 
  if(S.base!=S.top)
    return *(S.top-1);
}
void StackTraverse(SqStack S){//遍历顺序栈 
  SElemType *p;
  p=S.top;
  cout<<"顺序栈的元素为:";
  while(p!=S.base){
    p--;
    printf("%2c ",*p);
  }
  cout<<endl;
} 
void CleanStack(SqStack &S){//置空栈 
  if(S.base)
  {
    S.top=S.base;
    cout<<"恭喜您，栈已清空"<<endl; 
  }
  else
  cout<<"栈不存在"<<endl;
}
bool isValid(char op[]){
  SqStack T;
  InitStack(T);//初始化 
  int i=0;
  while(op[i]!='\0'){
    if(op[i]=='I')
      Push(T,op[i]);
    else if(op[i]=='O'){
      char c;
      if(Pop(T,c)!=OK||c!='I')
        return false; 
    }
    i++;
  }
  if(T.top==T.base)
    return true;
  else
    return false;
} 
int main(){
  SqStack s;
  int choose=-1;
  SElemType e,n;
  cout<<"1.初始化顺序栈\n2.插入元素\n3.删除栈顶元素\n4.取栈顶元素\n5.遍历栈\n6.置空栈\n7.检验IO操作是否合法\n0.退出"<<endl;
  cout<<"提示:入栈时只能输入单个字符"<<endl; 
  cout<<"-----------------------------"<<endl;
  while(choose!=0){
    cout<<"请输入您的选择:";
    cin>>choose;
    switch(choose){
      case 1:
        if(InitStack(s)==1){
          cout<<"恭喜您初始化成功"<<endl;
        }
        else
          cout<<"很遗憾初始化失败"<<endl;
        break;
      case 2:
        cout<<"请输入您要插入的元素：";
        cin>>e;
        if(Push(s,e)==1)
          cout<<"恭喜您插入成功"<<endl;
        else
          cout<<"很遗憾插入失败"<<endl;
        break;
      case 3:
        if(Pop(s,e)==1){
          cout<<"恭喜您删除栈顶元素成功"<<endl;
          cout<<"删除的栈顶元素为:"<<e<<endl; 
        }
        else
          cout<<"很遗憾删除栈顶元素失败"<<endl;
        break;
      case 4:
        if(s.base==s.top)
          cout<<"您的栈已空"<<endl;
        else{
          n=GetTop(s);
          cout<<"栈顶元素为:"<<n<<endl;
         }
        break;
      case 5:
        if(s.base==s.top)
          cout<<"您的栈已空"<<endl;
        else{
          StackTraverse(s);
        }
        break;
      case 6:
        CleanStack(s);
        break;
      case 7:
        char op[MAXSIZE];
        cout<<"请输入要检验的序列";
        cin>>op;
        if(isValid(op))
          cout<<"输入的序列合法"<<endl;
        else
          cout<<"输入的序列不合法"<<endl; 
        break;
      case 0:
        cout<<"恭喜您已退出"<<endl;
        break;
      default:
        cout<<"输入错误，请您重新输入"<<endl; 
    }
  } 
  return 0;
}

🎯链栈步骤：

🎐2.栈的链式表示和实现

链栈的存储结构定义：

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


  1. 1链栈的初始化


  1. 2链栈的入栈


  1. 3链栈的出栈


  1. 4取链栈的栈顶元素


  1. 5遍历链栈


  1. 6置空链栈


🎆注意要点：

链栈，出栈时需判断栈是否为空，为空时不能操作，否则产生错误；取栈顶元素与遍历之前也要判断栈是否为空。

🎯链栈完整代码：

//链栈
#include "iostream"
using namespace std;
#define OK 1
#define OVERFLOW -1
#define ERROR 0
#define MAXSIZE 100
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){//出栈
  if(S==NULL)
    return ERROR;
  LinkStack p;
  e=S->data;
  p=S;
  S=S->next;
  delete p;
  return OK; 
}
SElemType GetTop(LinkStack S){//取栈顶元素
  if(S!=NULL)
    return S->data; 
}
void TraverseList(LinkStack S){//遍历链栈
  LinkStack p;
  p=S; 
  if(p){
    cout<<p->data<<endl;
    TraverseList(p->next);
  }
}
Status ClearStack(LinkStack &S){//置空链栈 
  LinkStack p;
  if(S=NULL)
    return ERROR;
  while(S!=NULL){
    p=S;
    S=S->next;
    delete p;
  }
    return OK;
}
bool isValid(char op[]){
  LinkStack T;
  InitStack(T);//初始化 
  int i=0;
  while(op[i]!='\0'){
    if(op[i]=='I')
      Push(T,op[i]);
    else if(op[i]=='O'){
      char c;
      if(Pop(T,c)!=OK||c!='I')
        return false; 
    }
    i++;
  }
  if(T==NULL)
    return true;
  else
    return false;
  } 
int main(){
  LinkStack s;
  SElemType e;
  int choose=-1;
  SElemType n;
  cout<<"1.链栈的初始化\n2.入栈\n3.出栈\n4.取栈顶元素\n5.遍历栈\n6.置空栈\n7.检验IO操作是否合法\n0.退出\n";
  cout<<"特别注意：入栈时只可以是单个字符！！！"<<endl;
  cout<<"----------------------------"<<endl;
  while(choose!=0){
    cout<<"请输入您的选择:";
    cin>>choose;
    switch(choose){
      case 1:
        if(InitStack(s)==1)
          cout<<"恭喜您初始化成功"<<endl;
        else
          cout<<"很遗憾初始化失败"<<endl;
        break;
      case 2:
        cout<<"请输入您要入栈的元素:";
        cin>>e; 
        if(Push(s,e)==1)
          cout<<"恭喜您入栈成功"<<endl;
        else
          cout<<"很遗憾入栈失败"<<endl;
        break;
      case 3:
        if(Pop(s,e)==1){
          cout<<"恭喜您出栈成功"<<endl;
          cout<<"出栈元素为:"<<e<<endl; 
        } 
        else
          cout<<"很遗憾出栈失败"<<endl;
        break;
      case 4:
        if(s==NULL)
          cout<<"您的栈已空"<<endl;
        else{
          n=GetTop(s);
          cout<<"栈顶元素为:"<<n<<endl;
         }
        break;
      case 5:
        if(s==NULL)
          cout<<"您的栈已空"<<endl;
        else{
          cout<<"链栈中的元素为:"<<endl;
          TraverseList(s);
        }
        break;
      case 6:
        if(ClearStack(s)==1)
          cout<<"恭喜您栈已置空"<<endl;
        else
          cout<<"很遗憾栈不存在"<<endl;
        break;
      case 7:
        char op[MAXSIZE];
        cout<<"请输入要检验的序列";
        cin>>op;
        if(isValid(op))
          cout<<"输入的序列合法"<<endl;
        else
          cout<<"输入的序列不合法"<<endl; 
        break;
      case 0:
        cout<<"恭喜您已退出"<<endl; 
          break;
      default:
        cout<<"输入错误，请重新输入"<<endl;
    }
  }
}

[附加题]

1、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序、列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。


下面所示的序列中哪些是合法的？


A. IOIIOIOO


B. IOOIOIIO


C. IIIOIOIO


D. IIIOOIOO


通过对以上序列的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false (假定被判定的操作序列巳存入一维字符数组中）。


1. 顺序栈实现检验：

2.链栈实现检验：

文章标签：
算法
存储
关键词：
数据结构栈
数据结构顺序栈
数据结构基本操作
数据结构栈链栈
Y小夜
目录
相关文章
球球不吃虾
|
3天前
|
前端开发 JavaScript 算法
JavaScript 中实现常见数据结构：栈、队列与树
JavaScript 中实现常见数据结构：栈、队列与树
球球不吃虾
9 0
热爱嵌入式的小佳同学
|
4天前
|
存储 NoSQL C语言
数据结构——顺序栈与链式栈的实现-2
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
15 1
数据结构——顺序栈与链式栈的实现-2
热爱嵌入式的小佳同学
|
4天前
|
存储 C语言
数据结构——顺序栈与链式栈的实现-1
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
19 0
数据结构——顺序栈与链式栈的实现-1
toKeep
|
4天前
栈的基本应用
栈的基本应用
toKeep
14 3
toKeep
|
4天前
栈与队列理解
栈与队列理解
toKeep
13 1
Bigcrab__
|
4天前
|
存储 算法
数据结构与算法 栈与队列
数据结构与算法 栈与队列
Bigcrab__
12 0
数据结构与算法 栈与队列
天玑y
|
4天前
|
C++
数据结构（共享栈
数据结构（共享栈
天玑y
9 0
天玑y
|
4天前
|
C++
数据结构（顺序栈
数据结构（顺序栈
天玑y
13 2
叫我龙翔
|
4天前
|
容器
【栈与队列】栈与队列的相互转换OJ题
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
叫我龙翔
11 0
闻缺陷则喜何志丹
|
4天前
|
机器学习/深度学习 算法 测试技术
【单调栈】3113. 边界元素是最大值的子数组数目
【单调栈】3113. 边界元素是最大值的子数组数目
闻缺陷则喜何志丹
16 0