模板类 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

其实这个类有很多可以扩充的地方，不过栈应该具有的基本功能已经比较完备了。

本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。

猜你喜欢