线性表之顺序栈
栈是限定仅在表尾(栈顶)进行插入删除操作的线性表,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 }
三、运行示例结果:
原文链接: https://www.cnblogs.com/zfc-java/p/6664330.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/251982
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!