线性表之顺序栈C++实现

2018-06-27 10:01:00来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

线性表之顺序栈

栈是限定仅在表尾(栈顶)进行插入删除操作的线性表,FILO:先进后出

一、顺序栈的头文件:SeqStack.h

  1 //顺序栈头文件
  2 #include<iostream>
  3 using namespace std;
  4 //设置顺序栈的大小
  5 const int StackSize = 10;
  6 template<class DataType>
  7 //定义顺序栈的模板类型
  8 class SeqStack{
  9 public:
 10   //无参构造器,初始化栈顶指针
 11   SeqStack(){ top = -1; }
 12   //析构函数为空
 13   ~SeqStack(){}
 14   //入栈操作,将元素入栈
 15   void Push(DataType x);
 16   //出栈操作,将栈顶元素弹出栈
 17   DataType Pop();
 18   //取出栈顶元素,不删除栈顶元素(即取出的元素还在栈内)
 19   DataType GetTop();
 20   //判断栈是否为空
 21   int IsEmpty();
 22 private:
 23   //存放站元素的指针
 24   DataType data[StackSize];
 25   //栈顶指针:栈顶元素在数组中的下标
 26   int top;
 27 };
 28 
 29  
 30 
 31 //实现顺序栈入栈操作
 32 template<class DataType>
 33 void SeqStack<DataType>::Push(DataType x)
 34 {
 35   //判断当前顺序栈是否已是满栈
 36   if (top == StackSize - 1)
 37   {
 38     throw "栈已满";
 39   }
 40   else
 41   {
 42     //如果当前顺序栈不满,则栈顶值栈向上移动一个单元
 43     top++;
 44     //给新的栈顶元素赋值
 45     data[top] = x;
 46   }
 47 }
 48 
 49  
 50 
 51 //实现顺序栈出栈,弹出栈顶元素
 52 template<class DataType>
 53 DataType SeqStack<DataType>::Pop()
 54 {
 55   //先判断是否是空栈
 56   if (top == -1)
 57   {
 58     throw "栈是空栈";
 59   }
 60   else
 61   {
 62     //若不是空栈,则取出栈顶元素,并删除栈顶元素
 63     DataType x = data[top];
 64     //栈顶指针向下移动一个单元素
 65     top--;
 66     //返回栈顶元素的值
 67     return x;
 68   }
 69 }
 70 
 71  
 72 
 73 //实现取出栈顶元素,但不删除取出的元素
 74 template<class DataType>
 75 DataType SeqStack<DataType>::GetTop()
 76 {
 77   //先判断是否是空栈
 78   if (top == -1)
 79   {
 80     throw "栈是空栈";
 81   }
 82   else
 83   {
 84     //若不是空栈,则取出栈顶元素的值,但不删除栈顶元素
 85     DataType x = data[top];
 86     //返回栈顶元素的值
 87     return x;
 88   }
 89 }
 90 
 91  
 92 
 93 //实现判断顺序栈是否是空栈:栈空返回 1,否则返回 0
 94 template<class DataType>
 95 int SeqStack<DataType>::IsEmpty()
 96 {
 97 
 98   if (top == -1)
 99   {
100     return 1;
101   }
102   else
103   {
104     return 0;
105   }
106 }

 

二、测试顺序栈的源文件:TestSeqStack.cpp

 1 //测试顺序栈
 2 #include<iostream>
 3 //引入顺序栈头文件
 4 #include"SeqStack.h"
 5 using namespace std;
 6 int main()
 7 {
 8   //创建一个顺序栈
 9   SeqStack<int> seqStack = SeqStack<int>();
10   //判断是否是空栈
11   cout << "此时栈是否是空栈:" << seqStack.IsEmpty() << endl;
12   //入栈
13   seqStack.Push(1);
14   cout << "1 入栈了" << endl;
15   //判断是否是空栈
16   cout << "此时栈是否是空栈:" << seqStack.IsEmpty() << endl;
17   //取出栈顶元素
18   cout << "栈顶元素是:" << seqStack.GetTop() << endl;
19   //出栈
20   seqStack.Push(3);
21   cout << "3 入栈了" << endl;
22   //取出栈顶元素
23   cout << "栈顶元素是:" << seqStack.GetTop() << endl;
24   //出栈
25   seqStack.Push(7);
26   cout << "7 入栈了" << endl;
27   //取出栈顶元素
28   cout << "栈顶元素是:" << seqStack.GetTop() << endl;
29   //出栈
30   seqStack.Push(5);
31   cout << "5 入栈了" << endl;
32   //取出栈顶元素
33   cout << "栈顶元素是:" << seqStack.GetTop() << endl;
34   //出栈
35   cout << "栈顶元素" << seqStack.Pop() << "出栈了" << endl;
36   //取出栈顶元素
37   cout << "栈顶元素是:" << seqStack.GetTop() << endl;
38   //出栈
39   return 0;
40 }

 

 三、运行示例结果:

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++实现的控制台-贪吃蛇

下一篇:1313 质因数分解