数据结构探险（二）——栈

2023-12-28 19:58
文章标签 数据结构 探险

本文主要是介绍数据结构探险（二）——栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

demo说明栈原理,其中放入char类型

  • 先进后出（FILO）
  • 栈顶 栈底

改造栈，使其适用于复杂数据类型Coordinate

#ifndef COORDINATE_H
#define COORDINATE_H
#include<ostream>
using namespace std;class Coordinate
{
public:Coordinate(int x=0, int y=0);//默认构造函数void printCoordinate();private:int m_iX;int m_iY;
};#endif // COORDINATE_H
#include"Coordinate.h"
#include<iostream>using namespace std;Coordinate::Coordinate(int x,int y)
{m_iX=x;m_iY=y;
}void Coordinate::printCoordinate()
{cout<<"("<<m_iX<<","<<m_iY<<")";
}
int main(void)
{MyStack *pStack = new MyStack(5);pStack->push(Coordinate(1,2));//底pStack->push(Coordinate(3,4));pStack->stackTraverse(true);cout<<"栈中元素个数:"<<pStack->stackLength()<<endl;MyStack *pStack1= new MyStack(5);pStack1->push('h');pStack1->push('l');pStack1->push('x');pStack1->stackTraverse(false);cout<<"栈中元素个数:"<<p1Stack->stackLength()<<endl;
}

在这里插入图片描述

改造为类栈模板，使其适用于任何数据类型

  • 模板类myStack的类定义和函数定义要在一个文件尖中（这里放在mystack.h中）
  • 加入template<typename T> class MyStack声明类模板
  • 对每个类的成员函数 template<typename T> void MyStack<T>::stackTraverse(bool isFromButtom) {//... }
  • 实例化时要写 MyStack<Coordinate> *pStack = new MyStack<Coordinate>(5);
  • cout<<m_pBuffer[i];对于不同的数据类型 需要重载操作符cout
    如何重载？声明：friend ostream &operator<<(ostream &out,Coordinate &coor);
    函数体：ostream &operator<<(ostream &out,Coordinate &coor) { out<<"("<<coor.m_iX<<","<<coor.m_iY<<")"; return out; }
#ifndef MYSTACK_H_INCLUDED
#define MYSTACK_H_INCLUDED#include<iostream>using namespace std;template<typename T>
class MyStack
{
public:MyStack(int size);  //分配内存初始栈空间。设定栈容量，栈顶~MyStack();         //回收站空间内存bool stackEmpty();  //判断栈是否为空，为空返回true，非空返回falsebool stackFull();   //判断栈是否已满，为满返回true，不满返回falsevoid clearStack();  //清空栈int stackLength();  //已有元素的个数bool push(T elem); //元素入栈，栈顶上升bool pop(T &elem);  //元素出栈，栈顶下降void stackTraverse(bool isFromButtom);  //遍历栈中所有元素private:T *m_pBuffer; //栈空间指针int m_iSize; //栈容量int m_iTop;  //栈顶，栈中元素个数
};template<typename T>
MyStack<T>::MyStack(int size)
{m_iSize=size;m_pBuffer = new T[size];//因为写了默认构造函数，所以这样是对的不然会有错误m_iTop=0;
}template<typename T>
MyStack<T>::~MyStack()
{delete []m_pBuffer;//释放内存数组,也可以继续指针指为null
}
template<typename T>
bool MyStack<T>::stackEmpty()
{if(0==m_iTop)//一个提高质量的小技巧，这样写比m_iTop==0 便于报错查找错误{return true;}return false;
}
template<typename T>
bool MyStack<T>::stackFull()
{if(m_iTop==m_iSize)//>={return true;}return false;
}
template<typename T>
void MyStack<T>::clearStack()
{m_iTop=0;//栈中元素是否有用用itop标记，置零表示在栈当中放的所有值无效，再放新值覆盖即可
}template<typename T>
int MyStack<T>::stackLength()
{return m_iTop;//itop即可反应元素个数，有五个时m itop=5
}template<typename T>
bool MyStack<T>::push(T elem)
{if(stackFull()){//入栈失败处理://1 throw//2 返回值设为bool push 失败 return flasereturn false;}m_pBuffer[m_iTop]=elem;//这里要注意，复杂数据类型m_iTop++;return true;
}template<typename T>
bool MyStack<T>::pop(T &elem)
{if(stackEmpty()){return false;}m_iTop--;//栈顶指向的总是一个空位置，是下一个要入栈的位置elem=m_pBuffer[m_iTop];return true;
}template<typename T>
void MyStack<T>::stackTraverse(bool isFromButtom)
{if(isFromButtom){for(int i=0;i<m_iTop;i++){cout<<m_pBuffer[i];}}else{for(int i=m_iTop-1;i>=0;i--){cout<<m_pBuffer[i];}}
}#endif // MYSTACK_H_INCLUDED
#ifndef COORDINATE_H
#define COORDINATE_H
#include<ostream>
using namespace std;class Coordinate
{
public:friend ostream &operator<<(ostream &out,Coordinate &coor);Coordinate(int x=0, int y=0);//默认构造函数void printCoordinate();private:int m_iX;int m_iY;
};
Coordinate::Coordinate(int x,int y)
{m_iX=x;m_iY=y;
}void Coordinate::printCoordinate()
{cout<<"("<<m_iX<<","<<m_iY<<")";
}ostream &operator<<(ostream &out,Coordinate &coor)
{out<<"("<<coor.m_iX<<","<<coor.m_iY<<")";return out;
}
#endif // COORDINATE_H
int main(void)
{MyStack<Coordinate> *pStack = new MyStack<Coordinate>(5);pStack->push(Coordinate(1,2));//底pStack->push(Coordinate(3,4));pStack->stackTraverse(true);cout<<"栈中元素个数:"<<pStack->stackLength()<<endl;MyStack<char> *pStack1= new MyStack<char>(5);pStack1->push('h');pStack1->push('l');pStack1->push('x');pStack1->stackTraverse(false);cout<<"栈中元素个数:"<<pStack1->stackLength()<<endl;
}

在这里插入图片描述

栈应用（一）：数值转换

在这里插入图片描述

#include<stdlib.h>
#include<iostream>
#include"MyStack.h"
using namespace std;#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16int main(void)
{char num[]="0123456789ABCDEF";MyStack<int> *pStack = new MyStack<int>(30);int N= 1348;int mod=0;//存余数while(N!=0){mod = N % HEXADECIMAL;pStack->push(mod);N = N/HEXADECIMAL;}//如何打印出栈里面的内容//方法一：从顶往底遍历//pStack->stackTraverse(false);//方法二：避免了十六进制中无法输出ABCDEF的问题/*for(int i=pStack->stackLength()-1;i>=0;i--){num[pStack[i]];//无法用pStack[i]的方式获得元素，需要重载符号[]}*///方法三:使用popint elem=0;while(!pStack->stackEmpty()){pStack->pop(elem);cout<<num[elem];}delete pStack;pStack=NULL;system("pause");return 0;
}

1348的十六进制数为:
在这里插入图片描述

栈应用（二）：括号匹配

在这里插入图片描述

#include<string.h>
#include<stdlib.h>
#include<iostream>
#include"MyStack.h"
using namespace std;int main(void)
{MyStack<char> *pStack = new MyStack<char>(30);MyStack<char> *pNeedStack = new MyStack<char>(30);char str[]="[()]]";//char str[]="[[()]]";//记录当前需要的字符char currentNeed =0;//扫描str字符串for(int i=0;i<strlen(str);i++){//与当前需要的字符对比//不匹配的情况if(str[i]!=currentNeed){pStack->push(str[i]);switch(str[i]){case '['://case 只能是int 或者charif(currentNeed!=0){pNeedStack->push(currentNeed);}currentNeed=']';break;case '(':if(currentNeed!=0){pNeedStack->push(currentNeed);}currentNeed=')';break;default://如果字符是额外的])。一定不匹配 例如[()]]]]]的情况cout<<"字符串括号不匹配"<<endl;system("pause");return 0;}}//匹配的情况else{char elem;pStack->pop(elem);if(!pNeedStack->pop(currentNeed)){currentNeed=0;};}}//栈中是否还有字符（未必绝对，所以需要上述的default）if(pStack->stackEmpty()){cout<<"字符串括号匹配"<<endl;}else{cout<<"字符串括号不匹配"<<endl;}delete pStack;pStack= NULL;delete pNeedStack;pStack= NULL;system("pause");return 0;
}

测试：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

这篇关于数据结构探险（二）——栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/547113。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2