栈是先进后出的特殊线性表，只允许在表的末端进行插入和删除，后面将介绍两种实现栈的方式，分别是基于数组的实现、基于链表的实现。
栈的抽象定义
|
1
2
3
4
5
6
7
8
9
10
11
|
class Mystack{public: Mystack() {} virtual void push(int &x) = 0; virtual bool pop(int &x) = 0; virtual bool Top(int &x) const = 0; virtual bool IsEmpty()const = 0; virtual bool IsFull()const = 0; virtual int getSize()const = 0;}; |
顺序栈-----------使用数组表示栈空间
定义：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#pragma once#include "Mystack.h"#include <iostream>#include <assert.h>using namespace std;const int stackIncreament = 20;class SeqStack : public Mystack{public: SeqStack(int sz = 50); //建立一个空栈 ~SeqStack() { delete[]elements; } //析构函数 //如果栈满，则溢出程序处理，否则插入x void push(int &x); //如果栈空，则返回FALSE，否则使用x传递栈顶的值，top-1 bool pop(int &x); //如果栈空，则返回FALSE，否则使用x传递栈顶的值 bool Top(int &x); //判断栈是否为空 bool IsEmpty()const { return (top == -1) ? true : false; } //判断栈是都为满 bool IsFull()const { return (top == maxSize - 1) ? true : false; } //获取栈当前的size int getSize()const { return top + 1; } //将栈置空 void MakeEmpty() { top = -1; } //重载 操作 << friend ostream& operator<<(ostream& os, SeqStack& s);private: int *elements; //栈数组指针 int top; //栈顶指针 int maxSize; //栈的最大容量 void overflowProcess(); //溢出处理程序}; |
实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include "SeqStack.h"SeqStack::SeqStack(int sz):top(-1),maxSize(sz){ elements = new int[maxSize]; //创建栈的数组空间 assert(elements == NULL); //断言：动态分配是否成功}void SeqStack::push(int & x){ //首先判断栈是否已满，满则转入溢出处理 if(IsFull() == true){ overflowProcess(); } elements[++top] = x; //将top+1，再插入值x}bool SeqStack::pop(int & x){ //先判断是否为空，为空则返回FALSE if (IsEmpty() == true) { return false; } x = elements[top--]; //使用x返回top所指，再讲top-1 return true;}bool SeqStack::Top(int & x){ //空栈则为FALSE if (IsEmpty() == true) { return false; } //栈不为空，则返回栈顶元素的值 x = elements[top]; return true;}ostream& operator<<(ostream& os, SeqStack& s) { //输出栈中元素 os << "top = " << s.top << endl; for (int i = 0; i <= s.top; ++i) { os << i << ": " << s.elements[i] << endl; } return os;}void SeqStack::overflowProcess(){ //栈溢出时，扩充栈的存储空间 int *Newelement = new int[maxSize + stackIncreament]; if (Newelement == NULL) { cout << "分配内存失败"; exit(1); } for (int i = 0; i <= top; ++i) { Newelement[i] = elements[i]; } delete[] elements; elements = Newelement;} |
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/q793145253/article/details/120478986
