首页 > > 程序设计 > C/C++ >

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

2018-06-17 22:54:30来源：未知阅读 ()

线性表之顺序栈

栈是限定仅在表尾（栈顶）进行插入删除操作的线性表，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 }