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

简介: 栈定义及其常用的基本操作(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();
}

2d9e28bed2160539d9bbe541c397a9ad_03e46d67840548d595bcecd0e7c759c7.png



目录
相关文章
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
334 77
|
7月前
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
354 6
|
9月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
244 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
141 9
|
9月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
192 7
|
11月前
|
存储 编译器 Linux
【c++】类和对象(上)(类的定义格式、访问限定符、类域、类的实例化、对象的内存大小、this指针)
本文介绍了C++中的类和对象,包括类的概念、定义格式、访问限定符、类域、对象的创建及内存大小、以及this指针。通过示例代码详细解释了类的定义、成员函数和成员变量的作用,以及如何使用访问限定符控制成员的访问权限。此外,还讨论了对象的内存分配规则和this指针的使用场景,帮助读者深入理解面向对象编程的核心概念。
548 4
|
12月前
|
存储 编译器 C语言
C++入门2——类与对象1(类的定义和this指针)
C++入门2——类与对象1(类的定义和this指针)
159 2
|
12月前
|
C++
C++番外篇——对于继承中子类与父类对象同时定义其析构顺序的探究
C++番外篇——对于继承中子类与父类对象同时定义其析构顺序的探究
130 1
|
12月前
|
NoSQL Redis C++
Redis的实现五:二叉堆的数据结构和TTL、c,c++的实现
这篇文章详细探讨了二叉堆的数据结构及其在C和C++中的实现,特别强调了二叉堆在Redis中实现TTL(生存时间)功能的重要性,并通过代码示例展示了如何在Redis中使用二叉堆来管理键的过期时间。
126 0