模板类 Stack C++ 实现(链表版)

使用模板类实现 Stack 类型,内部采用单链表。注意:也可以使用变长数组实现,详见这里

  1. 链表使用嵌入类型(子类型)的一个结构 Node 实现。C++ 中的嵌入类型是语法上的嵌入(这种说法可能不能算十分严谨),所以 Node 理论上和其它的类型并无区别,但是因为其访问属性为 private,就避免了外界接触其实现细节。使用这种实现方式,主要是因为C++不存在直接的私有类
  2. 对于每一个 node,其定义为一个代表项目的 val 和代表下一项的地址的指针 next。
  3. 因为是要实现栈,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

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

题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: