【数据结构】栈定义及其常用的基本操作(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)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
105 0
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
75 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
367 77
|
7月前
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
400 6
|
8月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
190 11
|
8月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
9月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
205 7
|
8月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
4月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
110 0

热门文章

最新文章