模板類 Stack C++ 實現（鏈表版） | 宁心勉学，慎思笃行

使用模板類實現 Stack 類型，內部採用單鏈表。注意：也可以使用變長數組實現，詳見這裡。

鏈表使用嵌入類型（子類型）的一個結構 Node 實現。C++ 中的嵌入類型是語法上的嵌入（這種說法可能不能算十分嚴謹），所以 Node 理論上和其它的類型並無區別，但是因為其訪問屬性為 private，就避免了外界接觸其實現細節。使用這種實現方式，主要是因為C++不存在直接的私有類。
對於每一個 node，其定義為一個代表項目的 val 和代表下一項的地址的指針 next。
因為是要實現棧，LIFO （後入先出）的規則，決定了我們只需要存儲一個 head 指針，每次的 push 和 pop 只需要針對頭部的第一個元素進行就可以了。

下面是代碼。

/*
 * A Stack Implement
 * With Linked List
 *
 * Copyright(C) Ceeji
 */
#include <iostream>
 
#ifndef _STACK_H_
#define _STACK_H_
 
/*
 * stack<T> : a stack implement template class
 */
template<typename T>
class stack {
public:
	stack();
	void push(const T& element); // push an element to this stack
	T pop(); // pop an element from this stack
	T peek(); // get the top element on this stack without poping it
	int size(); // get the size of this stack
	bool isEmpty(); // is the stack empty
 
private:
// a struct to present a linked list node.
struct node {
	const T * val; // the value of this node
	node *next;    // a ptr to the next node
};
 
	node* head;
	int n; // count
};
 
template<typename T>
stack<T>::stack() {
	// init the variable
	this->n = 0;
	this->head = NULL;
}
 
template<typename T>
void stack<T>::push(const T& element) {
	node *oldHead = this->head;
	this->head = new node();
	this->head->val = new T(element);
	this->head->next = oldHead;
	++n;
}
 
template<typename T>
T stack<T>::pop() {
	if (this->isEmpty()) {
		throw "empty stack";
	}
 
	const T *retPtr = this->head->val;
	node *newHead = this->head->next;
	delete this->head;
	this->head = newHead;
 
	--n;
	return *retPtr;
}
 
template<typename T>
T stack<T>::peek() {
	if (this->isEmpty()) {
		throw "empty stack";
	}
 
	const T *retPtr = this->head->val;
	return *retPtr;
}
 
template<typename T>
inline bool stack<T>::isEmpty() {
	return n == 0;
}
 
template<typename T>
inline int stack<T>::size() {
	return n;
}
 
#endif

其實這個類有很多可以擴充的地方，不過棧應該具有的基本功能已經比較完備了。

猜你喜歡