模板类 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
其实这个类有很多可以扩充的地方,不过栈应该具有的基本功能已经比较完备了。
题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名。
© 转载需附带本文链接,依据 CC BY-NC-SA 4.0 发布。