棧和隊列

2019-11-08 02:35:32

字體：大中小

供稿：網(wǎng)友

在這篇文章中，簡單介紹一下棧和隊列的原理及實現(xiàn)，后面會附上相應(yīng)習題幫助進一步理解。一、簡述棧1、概念棧是一種操作受限的線性表，它的限制在于只能在表尾進行插入或刪除，其中表尾稱為棧頂，表頭稱為棧底。2、特點棧的特點是“先進后出”3、實現(xiàn)（C++）在下述代碼中簡單實現(xiàn)了棧的“入棧、出棧、取棧頂元素、判棧空，求棧中有效元素的大小”等操作。具體實現(xiàn)代碼如下:#include <iostream>#include <assert.h>using namespace std;#include <string>template <class T>class Stack{public: Stack()//構(gòu)造函數(shù) :_a(NULL) , _size(0) , _capacity(0) {} ~Stack()//析構(gòu)函數(shù) { 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、問題簡析在上述代碼中，對于檢查容量函數(shù)_CheckCapacity()有以下兩點說明：（1）、當空間不夠用，需要開辟更大的空間時，為什么要用new，而不用realloc?原因就是realloc和new有本質(zhì)上的區(qū)別：realloc只負責分配空間；而new除了分配空間之外，還要調(diào)自定義類型的構(gòu)造函數(shù)進行初始化。如果對自定義類型不進行初始化，則會產(chǎn)生錯誤。因此使用new開辟空間。

（2）、向新開辟的空間拷貝數(shù)據(jù)時，為什么不能用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; } } 與之前的函數(shù)相比，這個_CheckCapacity()函數(shù)中用的是memcpy進行拷貝，而非for循環(huán)，做了這樣的變化之后，我們給出兩個測試用例，看看會出現(xiàn)什么樣的結(jié)果？同樣給出測試函數(shù)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(); }}該函數(shù)的輸出結(jié)果如下:

測試函數(shù)1輸出結(jié)果由上圖可知，輸出正常，而當我們將數(shù)據(jù)類型換成string，會出現(xiàn)什么樣的情況呢？

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(); }}上面這段代碼的輸出結(jié)果如下圖：

測試函數(shù)2輸出結(jié)果對于以上的異常輸出，有兩點疑問：一是為什么程序會崩潰？二是為什么唯獨第二個字符串輸出的是隨機值？先來看第一個問題：由上圖可知，當舊空間中的string對象調(diào)用析構(gòu)函數(shù)，將所指向的空間釋放了之后，新開辟空間中的string對象的指針就會指向一段未知的空間，變成野指針，因此程序會崩潰。再來看第二個問題: 對比一下我們可以發(fā)現(xiàn)，只有第二個字符串超過了16個字節(jié)，而其他的字符串均沒有超過16個字節(jié)，那為什么超過16個字節(jié)就會出現(xiàn)隨機值呢？因為string比較常用，因此系統(tǒng)對它進行了優(yōu)化，即string對象中除了指針以外，還有16個字節(jié)的buff，所以一旦string對象所指向的內(nèi)存空間中存儲的數(shù)據(jù)超過16個字節(jié)，就會產(chǎn)生隨機值。二、簡述隊列 1、概念隊列也是一種線性表結(jié)構(gòu)，