棧

棧的概念和結構

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行資料插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的資料元素遵守後進先出LIFO（Last In First Out）加粗樣式的原則。
入棧：從棧頂放入資料的操作。
出棧：從棧頂取出元素的操作。

棧的實現

棧用連結串列和順序表兩種資料結構都可以實現，我們要確定選擇哪一種更優，我們來分析一下。
連結串列棧：如果選擇單連結串列的話，我們應該選擇頭當棧頂，尾當棧底，不然的話，每次存取資料都要遍歷一遍連結串列。所以選雙連結串列會比較好一點。
陣列棧：存取棧頂的時間複雜度為O(1)，相比連結串列棧比較優。
所以下面我們用順序表來實現棧的這種資料結構。
結構如下：初始化棧的大小為5

#define InitSize  5
template <class DateType>
class Stack
{
public:
private:
	DateType* data;//棧空間指標
	int size;//棧容量
	int top;//棧頂，棧中元素個數
};

棧的介面

棧要實現的介面有以下幾個：

Stack();//初始化棧，初始化的大小是5
Stack(const Stack& stack);//拷貝建構函式
Stack& operator=(const Stack& stack);//等號運運算元的過載
~Stack();//銷燬棧
bool ifFull();//判斷棧是否滿了
bool isEmpty();//判斷棧是否為空
void Push(const DateType& val);//入棧
bool Pop(DateType &item);//出棧，並獲取出棧元素
void ExpandStack();//擴容
void PrintStack();//列印

棧的初始化

初始化棧就是把結構體中的成員都初始化一下，方便後續的擴容等操作。
具體實現如下：

//初始化棧，初始化的大小是5
Stack()
{
	data = new DateType[InitSize];
	if (data == NULL)
	{
		cout << "記憶體分配失敗" << endl;
		exit(-1);
	}
	size = InitSize;
	top = 0;
}

拷貝構造

//拷貝建構函式
Stack(const Stack& stack)
{
	this->data = new DateType[stack.size];
	if (data == NULL)
	{
		cout << "記憶體分配失敗" << endl;
		exit(-1);
	}
	for (int i = 0; i < stack.size; i++)
	{
		this->data[i] = stack.data[i];
	}
	this->size = stack.size;
	this->top = stack.top;
}

判斷棧滿

//判斷棧是否滿了
bool ifFull()
{
	if (top == size)
	{
		return true;
	}
	return false;
}

擴容

//擴容
void ExpandStack()
{
	this->size = this->size == 0 ? 4 : 2 * this->size;
	DateType* tmp = new DateType[this->size];
	if (tmp == NULL)
	{
		cout << "記憶體分配失敗" << endl;
		exit(-1);
	}
	for (int i = 0; i < top; i++)
	{
		tmp[i] = data[i];
	}
	delete[] data;
	data = tmp;
}

判斷棧空

//判斷棧是否為空
bool isEmpty()
{
	if (top == 0)
	{
		return true;
	}
	return false;
}

入棧

壓棧就是在棧頂插入元素，其中是肯定要考慮到擴容的問題，當this->top == this->size時，就要考慮到擴容了，擴容也是像之前順序表那樣每次擴一倍，這樣可以一定程度地減少擴容次數，但同時是會帶來一定的空間消耗的。

//入棧
void Push(const DateType& val)
{
	if (ifFull())
	{
		ExpandStack();
	}
	data[top++] = val;
}

出棧

出棧就是在棧頂pop掉一個元素，也就是top-1指向的位置，只需要將top進行一個減1的操作即可。
與此同時，我們要確保此次棧不為空，所以要進行判斷棧空的操作，防止程式崩潰。

//出棧，並獲取出棧元素
bool Pop(DateType &item)
{
	if (isEmpty())
	{
		cout << "棧為空，無法出棧" << endl;
		return false;
	}
	item = data[--top];
	return true;
}

賦值運運算元過載

運運算元過載的注意事項在前面的部落格我已經介紹過了，尤其是賦值運運算元，感興趣的小夥伴可以去看看，這裡要注意幾點

返回的是*this，物件本身
不要自己給自己賦值
要防止記憶體漏失
防止淺拷貝的發生

//等號運運算元的過載
Stack& operator=(const Stack& stack)
{
	//防止自賦值
	if (this == &stack)
	{
		return *this;
	}
	//防止記憶體漏失
	if (data != NULL)
	{
		delete[] data;
	}
	//防止淺拷貝
	this->data = new DateType[stack.size];
	if (data == NULL)
	{
		cout << "記憶體分配失敗" << endl;
		exit(-1);
	}
	for (int i = 0; i < stack.top; i++)
	{
		this->data[i] = stack.data[i];
	}
	this->size = stack.size;
	this->top = stack.top;
	return *this;
}

列印

//列印
void PrintStack()
{
	for (int i = 0; i < top; i++)
	{
		cout << data[i] << "  ";
	}
	cout << endl;
}

整體程式碼以及測試

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入標頭檔案
#include<string>//C++中的字串
using namespace std; //標準名稱空間
#define InitSize  5
/*
棧,利用順序表實現
*/
template <class DateType>
class Stack
{
public:
	//初始化棧，初始化的大小是5
	Stack()
	{
		data = new DateType[InitSize];
		if (data == NULL)
		{
			cout << "記憶體分配失敗" << endl;
			exit(-1);
		}
		size = InitSize;
		top = 0;
	}
	//拷貝建構函式
	Stack(const Stack& stack)
	{
		this->data = new DateType[stack.size];
		if (data == NULL)
		{
			cout << "記憶體分配失敗" << endl;
			exit(-1);
		}
		for (int i = 0; i < stack.size; i++)
		{
			this->data[i] = stack.data[i];

		}
		this->size = stack.size;
		this->top = stack.top;
	}
	//等號運運算元的過載
	Stack& operator=(const Stack& stack)
	{
		//防止自賦值
		if (this == &stack)
		{
			return *this;
		}
		//防止記憶體漏失
		if (data != NULL)
		{
			delete[] data;
		}
		//防止淺拷貝
		this->data = new DateType[stack.size];
		if (data == NULL)
		{
			cout << "記憶體分配失敗" << endl;
			exit(-1);
		}
		for (int i = 0; i < stack.top; i++)
		{
			this->data[i] = stack.data[i];

		}
		this->size = stack.size;
		this->top = stack.top;
		return *this;
	}
	//銷燬棧
	~Stack()
	{
		if (data != NULL)
		{
			delete[] data;
			data = NULL;
		}
	}
	//判斷棧是否滿了
	bool ifFull()
	{
		if (top == size)
		{
			return true;
		}
		return false;
	}
	//判斷棧是否為空
	bool isEmpty()
	{
		if (top == 0)
		{
			return true;
		}
		return false;
	}
	//入棧
	void Push(const DateType& val)
	{
		if (ifFull())
		{
			ExpandStack();
		}
		data[top++] = val;
	}
	//出棧，並獲取出棧元素
	bool Pop(DateType &item)
	{
		if (isEmpty())
		{
			cout << "棧為空，無法出棧" << endl;
			return false;
		}
		item = data[--top];
		return true;
	}
	//擴容
	void ExpandStack()
	{
		this->size = this->size == 0 ? 4 : 2 * this->size;
		DateType* tmp = new DateType[this->size];
		if (tmp == NULL)
		{
			cout << "記憶體分配失敗" << endl;
			exit(-1);
		}
		for (int i = 0; i < top; i++)
		{
			tmp[i] = data[i];
		}
		delete[] data;
		data = tmp;
	}
	//列印
	void PrintStack()
	{
		for (int i = 0; i < top; i++)
		{
			cout << data[i] << "  ";
		}
		cout << endl;
	}
private:
	DateType* data;//棧空間指標
	int size;//棧容量
	int top;//棧頂，棧中元素個數
};
int main()
{
	Stack<int> stack;
	stack.Push(1);
	stack.Push(2);
	stack.Push(3);
	stack.Push(4);
	stack.Push(5);
	stack.PrintStack();
	cout << "-------------------------" << endl;
	int b = 0;
	stack.Pop(b);
	cout << b << endl;
	stack.Pop(b);
	cout << b << endl;
	stack.PrintStack();
	cout << "-------------------------" << endl;
	Stack<int> stack2(stack);
	stack2.PrintStack();
	cout << "-------------------------" << endl;
	Stack<int> stack3;
	stack3 = stack2;
	stack3.PrintStack();
	cout << "-------------------------" << endl;
	system("pause");
	return EXIT_SUCCESS;
}

佇列

佇列的概念和結構

佇列：只允許在一端進行插入資料操作，在另一端進行刪除資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out) 入佇列：進行插入操作的一端稱為隊尾出佇列：進行刪除操作的一端稱為隊頭。

佇列的結構，我們選取單連結串列來實現，秩序進行頭刪和為插的不足即可。如果選陣列，那麼每一次刪頭我們都要挪動一遍資料，這種方式不優，所以我們還是選取用單連結串列來實現。
定義的結構如下：

template<class DateType>
//鏈隊的結點型別
struct Node
{
	DateType data;
	Node<DateType> *next;
	Node(Node<DateType>* p = NULL)
	{
		next = p;
	}
	//建構函式
	Node(DateType val, Node<DateType>* p = NULL)
	{
		data = val;
		next = p;
	}
};

template <class DateType>
class Queue
{
public:
private:
	//宣告，也是定義，只不過定義的是指標型別，儲存的應該是地址，未初始化
	//隊頭指標
	Node<DateType>* front;
	//隊尾指標
	Node<DateType>* rear;
};

佇列的實現

佇列的介面

Queue();//建構函式，初始化佇列
~Queue();//解構函式
bool QueuePush(const DateType& val);//隊尾入隊
bool QueuePop(DateType& val);//對頭出佇列
bool getFront(DateType& val) const;//獲取對頭元素的值
bool getRear(DateType& val);//獲取隊尾元素的值
void MakeEmpty();//將佇列清空
bool isEmpty() const;//判斷佇列是否為NULL
int getSize() const;//返回佇列元素的個數
void PrintQueue();//輸出佇列元素

佇列的初始化

初始化很簡單，只要將頭指標和尾指標都置空。

//建構函式
Queue()
{
	front = NULL;
	rear = NULL;
}

判斷佇列是否為空

//判斷佇列是否為NULL
bool isEmpty() const
{
	if (front == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

入隊

出隊就是進行單連結串列尾刪的操作，要考慮連結串列為空時不能進行刪除，還要注意的是隻有一個節點進行刪除是要改變尾指標的指向。

//隊尾入佇列
bool QueuePush(const DateType& val)
{
	if (front == NULL)
	{
		//如果佇列為空，直接用指標開闢結點
		front = rear = new Node<DateType>(val);
		if (front == NULL)
		{
			cout << "記憶體分配失敗" << endl;
			return false;
		}
	}
	else
	{
		Node<DateType>* p = new Node<DateType>(val);
		rear->next = p;
		if (rear->next == NULL)
		{
			cout << "記憶體分配失敗" << endl;
			return false;
		}
		//更新尾結點
		rear = rear->next;
	}
	return true;
}

出隊

出隊就是進行單連結串列尾刪的操作，要考慮連結串列為空時不能進行刪除，還要注意的是隻有一個節點進行刪除是要改變尾指標的指向。

bool QueuePop(DateType& val)
{
	//如果佇列為空，不允許出列
	if (isEmpty())
	{
		return false;
	}
	else
	{
		Node<DateType>* p = front;
		val = front->data;
		front = front->next;
		delete p;
		return true;
	}
}

獲取隊頭元素和隊尾元素

首先要確保連結串列不為空，對頭就是返回頭節點的大小，隊尾就是返回尾節點的大小。
具體實現如下：

//獲取對頭元素的值
bool getFront(DateType& val) const
{
	if (isEmpty())
	{
		return false;
	}
	val = front->data;
	return true;
}
//獲取隊尾元素的值
bool getRear(DateType& val) {
	if (isEmpty())
	{
		return false;
	}
	val = rear->data;
	return true;
}

獲取佇列元素個數

遍歷一遍連結串列，同時進行計數操作，最後返回計數結果即可。

//返回佇列元素的個數
int getSize() const
{
	//函數返回佇列元素的個數
	Node<DateType>* p = front;
	int count = 0;
	while (p != NULL)
	{
		++count;
		p = p->next;
	}
	return count;
}

佇列的銷燬

為了防止記憶體漏失，動態記憶體申請的空間一定要我們自己手動釋放，養成一個良好的習慣。所以要將連結串列的空間逐個釋放。

//將佇列清空
void MakeEmpty()
{
	//置空佇列，釋放連結串列中所有的結點
	Node<DateType>* current;
	if (front != NULL)
	{
		current = front;
		front = front->next;
		delete current;
	}
}

列印佇列

//輸出佇列元素
void PrintQueue()
{
	Node<DateType>* p = front;
	while (p != NULL)
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}

整體程式碼以及測試

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入標頭檔案
#include<string>//C++中的字串
using namespace std; //標準名稱空間
/*
佇列，單連結串列實現
*/
template<class DateType>
//鏈隊的結點型別
struct Node
{
	DateType data;
	Node<DateType> *next;
	Node(Node<DateType>* p = NULL)
	{
		next = p;
	}
	//建構函式
	Node(DateType val, Node<DateType>* p = NULL)
	{
		data = val;
		next = p;
	}
};
template <class DateType>
class Queue
{
public:
	//建構函式
	Queue()
	{
		front = NULL;
		rear = NULL;
	}
	//解構函式
	~Queue()
	{
		MakeEmpty();
	}
	//隊尾入佇列
	bool QueuePush(const DateType& val)
	{
		if (front == NULL)
		{
			//如果佇列為空，直接用指標開闢結點
			front = rear = new Node<DateType>(val);
			if (front == NULL)
			{
				cout << "記憶體分配失敗" << endl;
				return false;
			}
		}
		else
		{
			Node<DateType>* p = new Node<DateType>(val);
			rear->next = p;
			if (rear->next == NULL)
			{
				cout << "記憶體分配失敗" << endl;
				return false;
			}
			//更新尾結點
			rear = rear->next;
		}
		return true;
	}
	//對頭出佇列
	bool QueuePop(DateType& val)
	{
		//如果佇列為空，不允許出列
		if (isEmpty())
		{
			return false;
		}
		else
		{
			Node<DateType>* p = front;
			val = front->data;
			front = front->next;
			delete p;
			return true;

		}
	}
	//獲取對頭元素的值
	bool getFront(DateType& val) const
	{
		if (isEmpty())
		{
			return false;
		}
		val = front->data;
		return true;
	}
	//獲取隊尾元素的值
	bool getRear(DateType& val) {
		if (isEmpty())
		{
			return false;
		}
		val = rear->data;
		return true;
	}
	//將佇列清空
	void MakeEmpty()
	{
		//置空佇列，釋放連結串列中所有的結點
		Node<DateType>* current;
		if (front != NULL)
		{
			current = front;
			front = front->next;
			delete current;
		}
	}
	//判斷佇列是否為NULL
	bool isEmpty() const
	{
		if (front == NULL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//返回佇列元素的個數
	int getSize() const
	{
		//函數返回佇列元素的個數
		Node<DateType>* p = front;
		int count = 0;
		while (p != NULL)
		{
			++count;
			p = p->next;
		}
		return count;
	}
	//輸出佇列元素
	void PrintQueue()
	{
		Node<DateType>* p = front;
		while (p != NULL)
		{
			cout << p->data << "  ";
			p = p->next;
		}
		cout << endl;
	}
private:
	//宣告，也是定義，只不過定義的是指標型別，儲存的應該是地址，未初始化
	//隊頭指標
	Node<DateType>* front;
	//隊尾指標
	Node<DateType>* rear;
};
int main()
{
	Queue<int> que;
	que.QueuePush(1);
	que.QueuePush(2);
	que.QueuePush(3);
	que.QueuePush(4);
	que.PrintQueue();
	cout << "----------------------" << endl;
	int b = 0;
	que.QueuePop(b);
	cout << b << endl;
	que.QueuePop(b);
	cout << b << endl;
	que.PrintQueue();
	cout << "----------------------" << endl;
	int c = 0;
	que.getFront(c);
	cout << c << endl;
	que.PrintQueue();
	cout << que.getSize() << endl;
	cout << "----------------------" << endl;
	system("pause");
	return EXIT_SUCCESS;
}

資料結構初階--棧和佇列（講解+類別範本實現）

棧

棧的概念和結構

棧的實現

棧的介面

棧的初始化

拷貝構造

判斷棧滿

擴容

判斷棧空

入棧

出棧

賦值運運算元過載

列印

整體程式碼以及測試

佇列

佇列的概念和結構

佇列的實現

佇列的介面

佇列的初始化

判斷佇列是否為空

入隊

出隊

獲取隊頭元素和隊尾元素

獲取佇列元素個數

佇列的銷燬

列印佇列

整體程式碼以及測試