鱼C论坛

 找回密码
 立即注册
查看: 2196|回复: 1

[学习笔记] 顺序栈

[复制链接]
发表于 2018-4-17 16:29:23 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
小弟学习的《数据结构C++语言描述》 清华大学出版社   任燕编著
中的顺序栈的学习笔记,以下程序是按照书上的思路来进行编写的,
使之能在电脑中运行但是小弟改了书中的一个错误(书中最后拷贝
构造函数写的有问题,小弟已经改过来了),同时小弟还重载了输出运算符,
希望大家学习数据结构不要只是看书,更多的是要进行实践,当然小弟也是
以此贴来记录我的学习数据结构的经历。
  1. #include <iostream>
  2. #include <assert.h>
  3. #include <cstdlib>
  4. #include <cstdbool>
  5. #define STACK_MAX_SIZE 100
  6. #define STACKINCREAMENT 10
  7. using namespace std;

  8. template <typename elemtype>
  9. class SqStack{
  10. public:
  11.         //顺序栈置空
  12.         void clear();

  13.         //求顺序栈中元素的个数
  14.         int getLength();

  15.         //返回档期那已经分派的存储空间的大小
  16.         int getStackSize();

  17.         //读取栈顶元素
  18.         bool getTop(elemtype &e);

  19.         //判断顺序栈是否为空
  20.         bool isEmpty();

  21.         //重载赋值运算符
  22.         SqStack operator=(SqStack right);

  23.         //弹出栈顶元素
  24.         bool pop(elemtype &e);

  25.         //在栈顶压入元素e
  26.         void push(elemtype e);

  27.         //构造函数
  28.         SqStack();

  29.         //析构函数
  30.         virtual ~SqStack();

  31.         //拷贝构造函数
  32.         SqStack(SqStack &other);

  33.         //重载输出运算符
  34.         template <typename out_put>
  35.         friend ostream& operator <<(ostream& out, SqStack<out_put> other);

  36. protected:
  37.         elemtype *base;//栈底指针,就是顺序栈动态存储空间的首地址
  38.         elemtype *top;//栈顶指针
  39.         int stackSize;//顺序栈当前已经分配的存储空间的大小
  40. };


  41. template <typename elemtype>
  42. void SqStack<elemtype>::clear(){
  43.         top = base;
  44.         cout << "顺序栈已经清空" << endl;
  45. }

  46. template <typename elemtype>
  47. int SqStack<elemtype>::getLength(){
  48.         return top - base;
  49. }

  50. template <typename elemtype>
  51. int SqStack<elemtype>::getStackSize(){
  52.         return stackSize;
  53. }

  54. //读取栈顶的元素
  55. template <typename elemtype>
  56. bool SqStack<elemtype>::getTop(elemtype &e){
  57.         if (isEmpty()){
  58.                 return false
  59.         }
  60.         else{
  61.                 e = *(top - 1);
  62.         }
  63.         return true;
  64. }

  65. template <typename elemtype>
  66. bool SqStack<elemtype>::isEmpty(){
  67.         return top == base ? true : false;
  68. }

  69. //重载赋值运算符
  70. template <typename elemtype>
  71. SqStack<elemtype> SqStack<elemtype>::operator =(SqStack<elemtype> right){
  72.         int length = right.getLength();

  73.         if (this != &right){
  74.                 if (stackSize < right.stackSize){
  75.                         delete[] base;  //回收左边的顺序栈的存取空间
  76.                         base = new elemtype[right.stackSize];
  77.                         assert(base != 0);
  78.                         stackSize = right.stackSize;//进行属性的一些重新的赋值
  79.                 }

  80.                 for (int i = 0; i < length; i++){
  81.                         *(base + i) = *(right.base + i);
  82.                 }
  83.                 top = base + length();
  84.         }
  85.         return *this;//返回对象
  86. }

  87. //弹出栈顶元素到e
  88. template <typename elemtype>
  89. bool SqStack<elemtype>::pop(elemtype &e){
  90.         if (isEmpty()){
  91.                 return false;
  92.         }
  93.         else{
  94.                 e = *--top;
  95.         }
  96.         return true;
  97. }

  98. //在栈顶压入元素e
  99. template <typename elemtype>
  100. void SqStack<elemtype>::push(elemtype e){
  101.         int length = top - base;//顺序栈中元素的个数
  102.         elemtype *newBase;//预指向新顺序栈的栈底指针
  103.         //判断当前顺序栈是否已满,如果满了,则需要另外申请存储空间
  104.         if (top - base >= stackSize){
  105.                 newBase = new elemtype[stackSize + STACKINCREAMENT];
  106.                 assert(newBase != 0);

  107.                 for (int j = 0; j < length; j++){
  108.                         *(newBase + j) = *(base + j);
  109.                 }

  110.                 delete[] base;//回收当前已经满了的栈空间
  111.                 base = newBase;
  112.                 top = base + length;
  113.         }

  114.         //如果当前顺序栈没有满,就不用重新申请空间了,就直接以下两个语句就行了
  115.         *top = e;
  116.         top++;
  117. }


  118. template <typename elemtype>
  119. SqStack<elemtype>::SqStack(){
  120.         base = new elemtype[STACK_MAX_SIZE];//申请空间
  121.         assert(base != 0);
  122.         stackSize = STACK_MAX_SIZE;//属性的赋值
  123.         top = base;//栈的初始为空
  124. }

  125. //你懂的
  126. template <typename elemtype>
  127. SqStack<elemtype>::~SqStack(){
  128.         if (base){
  129.                 delete[]base;
  130.         }
  131.         stackSize = 0;
  132.         top = base = NULL;
  133. }

  134. template <typename elemtype>
  135. SqStack<elemtype>::SqStack(SqStack &other){
  136.         int length = other.top - other.base;
  137.         base = new elemtype[other.stackSize];

  138.         assert(base != 0);

  139.         stackSize = other.stackSize;
  140.         for (int i = 0; i < length; i++){
  141.                 *(base + i) = *(other.base + i);
  142.         }
  143.         top = base + length;
  144. }

  145. template <typename out_put>
  146. ostream& operator<<(ostream& out, SqStack<out_put> other){
  147.         int length = other.top - other.base;
  148.         for (int i = 0; i < length; i++){
  149.                 out << *(other.base + i) << "\t";
  150.         }

  151.         return out;
  152. }


  153. int main(void){
  154.         SqStack<int> s1;
  155.         for (int i = 1; i <= 10; i++){
  156.                 s1.push(i);
  157.         }
  158.         cout << "顺序栈为:";
  159.         cout << s1 << endl;//应用的重载的输出运算符
  160.         cout << "####################################" << endl;
  161.         int e;
  162.         while (s1.pop(e)){
  163.                 cout << "弹出栈顶元素为:" << e << endl;
  164.         }

  165.         return 0;
  166. }





复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-4-17 16:32:11 | 显示全部楼层
这个是一些功能的运行成果:
顺序栈为:1      2       3       4       5       6       7       8       9       10
####################################
弹出栈顶元素为:10
弹出栈顶元素为:9
弹出栈顶元素为:8
弹出栈顶元素为:7
弹出栈顶元素为:6
弹出栈顶元素为:5
弹出栈顶元素为:4
弹出栈顶元素为:3
弹出栈顶元素为:2
弹出栈顶元素为:1
请按任意键继续. . .
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 18:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表