栈和队列

2019-11-08 02:35:32

字体：大中小

来源：转载

供稿：网友

在这篇文章中，简单介绍一下栈和队列的原理及实现，后面会附上相应习题帮助进一步理解。一、简述栈1、概念栈是一种操作受限的线性表，它的限制在于只能在表尾进行插入或删除，其中表尾称为栈顶，表头称为栈底。2、特点栈的特点是“先进后出”3、实现（C++）在下述代码中简单实现了栈的“入栈、出栈、取栈顶元素、判栈空，求栈中有效元素的大小”等操作。具体实现代码如下:#include <iostream>#include <assert.h>using namespace std;#include <string>template <class T>class Stack{public: Stack()//构造函数 :_a(NULL) , _size(0) , _capacity(0) {} ~Stack()//析构函数 { if (_a) { delete[] _a; } _size = 0; _capacity = 0; } void Push(const T& x)//入栈 { _CheckCapacity(); _a[_size++] = x; } void Pop()//出栈 { assert(_size > 0); _size--; } T& Top()//取栈顶元素 { assert(_size > 0); return _a[_size - 1]; } bool empty() { return _size == 0; } size_t Size() { return _size; }PRotected: void _CheckCapacity() { if (_size == _capacity) { _capacity = _capacity * 2 + 3; T* tmp = new T[_capacity]; if (_a) { //memcpy(tmp, _a, sizeof(T)*_size); for (size_t i = 0; i < _size; ++i) { tmp[i] = _a[i]; } delete[] _a; } _a =tmp; } }protected: T* _a; size_t _size; size_t _capacity;};4、问题简析在上述代码中，对于检查容量函数_CheckCapacity()有以下两点说明：（1）、当空间不够用，需要开辟更大的空间时，为什么要用new，而不用realloc?原因就是realloc和new有本质上的区别：realloc只负责分配空间；而new除了分配空间之外，还要调自定义类型的构造函数进行初始化。如果对自定义类型不进行初始化，则会产生错误。因此使用new开辟空间。

（2）、向新开辟的空间拷贝数据时，为什么不能用memcpy? 先来看一段代码：

void _CheckCapacity() { if (_size == _capacity) { _capacity = _capacity * 2 + 3; T* tmp = new T[_capacity]; if (_a) { memcpy(tmp, _a, sizeof(T)*_size); /* for (size_t i = 0; i < _size; ++i) { tmp[i] = _a[i]; }*/ delete[] _a; } _a =tmp; } } 与之前的函数相比，这个_CheckCapacity()函数中用的是memcpy进行拷贝，而非for循环，做了这样的变化之后，我们给出两个测试用例，看看会出现什么样的结果？同样给出测试函数1： void TestStack1(){ Stack<int> s1; s1.Push(1); s1.Push(2); s1.Push(3); s1.Push(4); while (!s1.empty()) { cout << s1.Top() << endl; s1.Pop(); }}该函数的输出结果如下:

测试函数1输出结果由上图可知，输出正常，而当我们将数据类型换成string，会出现什么样的情况呢？

void TestStack2(){ Stack<string> s2; s2.Push("aaaaaaaa"); s2.Push("bbbbbbbbbbbbbbbbb"); s2.Push("cccccccc"); s2.Push("dddddddddd"); while (!s2.empty()) { cout << s2.Top() << endl; s2.Pop(); }}上面这段代码的输出结果如下图：

测试函数2输出结果对于以上的异常输出，有两点疑问：一是为什么程序会崩溃？二是为什么唯独第二个字符串输出的是随机值？先来看第一个问题：由上图可知，当旧空间中的string对象调用析构函数，将所指向的空间释放了之后，新开辟空间中的string对象的指针就会指向一段未知的空间，变成野指针，因此程序会崩溃。再来看第二个问题: 对比一下我们可以发现，只有第二个字符串超过了16个字节，而其他的字符串均没有超过16个字节，那为什么超过16个字节就会出现随机值呢？因为string比较常用，因此系统对它进行了优化，即string对象中除了指针以外，还有16个字节的buff，所以一旦string对象所指向的内存空间中存储的数据超过16个字节，就会产生随机值。二、简述队列 1、概念队列也是一种线性表结构，