【数据结构】栈定义及其常用的基本操作（C/C++）-阿里云开发者社区

【数据结构】栈定义及其常用的基本操作（C/C++）

2023-01-13 159

版权

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

简介： 栈定义及其常用的基本操作（C/C++）

图示（以顺序栈为例）

bc1b7615d7f16e9742af6ff6dab213c5_71a2752fdd1c46a89b5969eb4f720a27.png

●栈的类型定义

1.顺序栈存储结构的定义

typedef struct{
  Selemtype *base;  //栈底指针 
  Selemtype *top;  // 栈顶指针 
  int stacksize;
}Sqstack;

实例如下：

typedef struct {
  char key[10];  //学号
  char name[20];  //姓名
  int age;   //年龄
}Selemtype;
typedef struct{
  Selemtype *base;  
  Selemtype *top;  
  int stacksize;
}Sqstack;

2.链式栈存储结构的定义（对照与链式表理解记忆http://t.csdn.cn/ypvSH）

typedef struct Stacknode {
  Selemtype data;
  struct Stacknode* next;
}Stacknode, * Linkstack;
 实例如下：
typedef struct {
    char key[10];
  char name[20];
    int age;
}Selemtype;
typedef struct Stacknode {
  Selemtype data;
  struct Stacknode* next;
}Stacknode, * Linkstack;

●栈常用的基本操作

●顺序栈

1.顺序栈的初始化

int Initstack(Sqstack& S)
{
  S.base = new Selemtype[maxsize];
  if (!S.base)
  exit(0);
  S.top = S.base;
  S.stacksize = maxsize;
  return 1;
}

2.判断顺序栈是否为空

int Stackempty(Sqstack& S)
{
  if (S.top == S.base)
  return 1;
  else
  return 0;
}

3.求顺序栈的长度

int Stacklength(Sqstack& S)
{
  return (S.top - S.base);
}

4.清空顺序栈

int Clearstack(Sqstack &S)
{
  if (S.base)
  S.top = S.base;
  return 1;
}

5.销毁顺序栈

int Destorystack(Sqstack& S)
{
  if (S.base)
  {
  delete S.base;
  S.stacksize = 0;
  S.base = S.top = NULL;
  }
  return 1;
}

6.顺序栈的入栈

int push(Sqstack& S, Selemtype e)
{
  if (S.top - S.base == S.stacksize)
  return 0;
  *S.top = e;
  S.top++;
  return 1;
}

7.顺序栈的出栈

int pop(Sqstack& S, Selemtype e)
{
  if (S.top == S.base)
  return 0;
  --S.top;
  e = *S.top;
  return 1;
}

●链式栈

1. 链栈的初始化

int Initstack(Linkstack& S)
{
  S = NULL;
  return 1;
}

2. 判断链栈是否为空

int Stackempty(Linkstack S)
{
  if (S == NULL)
  return 1;
  else
  return 0;
}

3. 链式栈的入栈

int Push(Linkstack& S, Selemtype e)
{
  Linkstack p;
  p = new Stacknode;
  p->data = e;
  p->next = S;
  S = p;
  return 1;
}

4. 链式栈的出栈

int Pop(Linkstack& S, Selemtype e)
{
  if (S == NULL)
  return 0;
  Linkstack p;
  e = S->data;
  p = S;
  S = S->next;
  delete p;
  return 1;
}

5.取栈顶元素

Selemtype Gettop(Linkstack &S)
{
  if (S != NULL)
  return S->data;
}

●简单案例

1.顺序栈（这里只实现用顺序栈存储3个学生的学号、姓名、年龄并且将其输出查看。若进行其他操作，对代码进行简单修改即可）

#include<iostream>
#define maxsize 100
using namespace std;
//数据准备
typedef struct {
  char key[10];
  char name[20];
  int age;
}Selemtype;
typedef struct{
  Selemtype* top;
  Selemtype* base;
  int stacksize;
}Sqstack;
//顺序栈的初始化
int Initstack(Sqstack& S)
{
  S.base = new Selemtype[maxsize];
  if (!S.base)
  exit(0);
  S.top = S.base;
  S.stacksize = maxsize;
  return 1;
}
//判断顺序栈是否为空
int Stackempty(Sqstack& S)
{
  if (S.top == S.base)
  return 1;
  else
  return 0;
}
//求顺序栈的长度
int Stacklength(Sqstack& S)
{
  return (S.top - S.base);
}
//清空顺序栈
int Clearstack(Sqstack &S)
{
  if (S.base)
  S.top = S.base;
  return 1;
}
//销毁顺序栈
int Destorystack(Sqstack& S)
{
  if (S.base)
  {
  delete S.base;
  S.stacksize = 0;
  S.base = S.top = NULL;
  }
  return 1;
}
//顺序栈的入栈
int push(Sqstack& S, Selemtype e)
{
  if (S.top - S.base == S.stacksize)
  return 0;
  *S.top = e;
  S.top++;
  return 1;
}
//顺序栈的出栈
int pop(Sqstack& S, Selemtype e)
{
  if (S.top == S.base)
  return 0;
  --S.top;
  e = *S.top;
  return 1;
}
//查看栈顶元素
void top(Sqstack& S)
{
  if (S.top == 0)
  exit(0);
  S.top--;
  cout << S.top->key << " " << S.top->name << " " << S.top->age << endl;
}
void showfunc()
{
  cout << "1.顺序栈的初始化" << endl;
  cout << "2.判断顺序栈是否为空" << endl;
  cout << "3.求顺序栈的长度" << endl;
  cout << "4.清空顺序栈" << endl;
  cout << "5.销毁顺序栈" << endl;
  cout << "6.顺序栈的入栈" << endl;
  cout << "7.顺序栈的出栈" << endl;
  cout << "8.查看栈顶元素" << endl;
}
void text()
{
  Sqstack S;
  Selemtype data;
  while(1)
  { 
  showfunc();
  cout << "#要执行的操作#" << endl;
  int n;
  cin >> n;
  switch (n)
  {
  case 1:
    Initstack(S);
    cout << "初始化完成" << endl;
    break;
  case 6:
    cout << "请输入要输入的学生人数：" << endl;
    int num; cin >> num;
    for (int i = 1; i <= num; i++)
    {
    cin >> data.key >> data.name >> data.age;
    push(S,data);
    }
    cout << "插入成功" << endl;
    break;
  case 8:
    top(S);
    break;
  }
  system("pause");
  system("cls");
  }
}
int main()
{
  text();
}

2.链式栈（不做过多演示，对代码进行简单操作即可。如：输入一个学生的信息，并查看）

#include<iostream>
using namespace std;
typedef struct {
  char key[10];
  char name[20];
  int age;
}Selemtype;
typedef struct Stacknode {
  Selemtype data;
  struct Stacknode* next;
}Stacknode, * Linkstack;
//链栈的初始化
int Initstack(Linkstack& S)
{
  S = NULL;
  return 1;
}
//判断链栈是否为空
int Stackempty(Linkstack S)
{
  if (S == NULL)
  return 1;
  else
  return 0;
}
//链式栈的入栈
int Push(Linkstack& S, Selemtype e)
{
  Linkstack p;
  p = new Stacknode;
  p->data = e;
  p->next = S;
  S = p;
  return 1;
}
//链式栈的出栈
int Pop(Linkstack& S, Selemtype e)
{
  if (S == NULL)
  return 0;
  Linkstack p;
  e = S->data;
  p = S;
  S = S->next;
  delete p;
  return 1;
}
//取栈顶元素
void  Gettop(Linkstack &S)
{
  if (S != NULL)
  cout << S->data.key<< S->data.name << S->data.age << endl;
}
void text()
{
  //不做过多演示，对代码进行简单操作即可
  Linkstack S;
  Selemtype Data;
  Initstack(S);
  cout << "初始化成功" << endl;
  cout << "输入一个学生的数据：" << endl;
  cin >> Data.key >> Data.name >> Data.age;
  cout << "将学生信息推入链栈中" << endl;
  Push(S,Data);
  cout << "查看栈顶元素" << endl;
  Gettop(S);
}
int main()
{
  text();
}