1.栈的介绍
栈的实现方式分为3种
- 基于静态数组实现,内部预设一个很大的数组对象, 实现简单,缺点是空间受限。
- 基于动态数组实现,内部预设一个容量值,然后分配一段内存空间数组,如果入栈大于默认容量值时,则再次扩大分配新的内存数组,并将旧数组拷贝至新数组及释放旧数组.
- 基于双向循环链表实现
栈的函数需要实现如下所示:
-
T pop() :
出栈并返回栈顶元素 -
void push(const T &t) :
入栈 -
const T & top() const :
获取const类型栈顶元素 -
T &top() :
获取栈顶元素 -
int length() const:
获取数量(父类已经实现)void clear(): 清空栈(父类已经实现)
本章,我们实现的栈基于动态数组实现,它的父类是我们之前实现的Vector类:
所以代码实现会非常简单.
2.栈实现
代码如下所示:
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
|
#ifndef Stack_H #define Stack_H #include "throw.h" // throw.h里面定义了一个ThrowException抛异常的宏,如下所示: //#include <iostream> //using namespace std; //#define ThrowException(errMsg) {cout<<__FILE__<<" LINE"<<__LINE__<<": "<<errMsg<<endl; (throw errMsg);} #include "Vector.h" template < class T> class Stack : public Vector<T> { public : T pop() { if (Vector<T>::isEmpty()) { // 如果栈为空,则抛异常 ThrowException( "Stack is empty ..." ); } T t = Vector<T>::data()[Vector<T>::length() - 1]; Vector<T>::resize(Vector<T>::length() - 1); return t; } // 入栈,实际就是append尾部添加成员 void push( const T &t) { Vector<T>::append(t); } T &top() { if (Vector<T>::isEmpty()) { ThrowException( "Stack is empty ..." ); } return Vector<T>::data()[Vector<T>::length() - 1]; } const T &top() const { if (Vector<T>::isEmpty()) { ThrowException( "Stack is empty ..." ); } return Vector<T>::data()[Vector<T>::length() - 1]; } }; #endif // Stack_H |
3.代码测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int main( int argc, char *argv[]) { Stack< int > stack; cout<< "******* current length:" <<stack.length()<<endl; for ( int i = 0; i < 5; i++) { cout<< "stack.push:" <<i<<endl; stack.push(i); } cout<< "******* current length:" <<stack.length()<<endl; while (!stack.isEmpty()) { cout<< "stack.pop:" <<stack.pop()<<endl; } return 0; } |
运行打印:
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注服务器之家的更多内容!
原文链接:https://blog.csdn.net/qq_37997682/article/details/123123143