栈是我们常用的数据结构之一，在很多项目中都有所应用。也是练习c++指针、类与泛型编程的好demo。
首先看，什么是栈？（摘自c++官网)
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.
翻译
栈是一种容器适配器，专门设计用于在LIFO上下文中操作（后进先出），其中元素仅从容器的一端插入和提取。
呃......看起来好深奥......简单来说，栈就像一个弹夹:
你是从弹夹顶端塞入塞入子弹 (后来者居上)
当你取出元素时，是打出顶端的子弹 (后进先出)
那这个数据结构有哪些成员函数呢?
去除构造函数，总共有一下几个函数:
push(T v) 从栈顶塞入一个值
pop() 从栈顶取出一个值
top() 获取栈顶的值 (注意: 这个和上面的不一样，上面是删除栈顶元素，这个是获取栈顶元素的值)
size() 获取栈中元素的数量
以上便是栈的所有操作，那我们先编写一下main.cpp，理清一下思路吧:
empty() 查看栈是否为空
#include <iostream>
#include "stack/stack.h"
#include "stack/stack.cpp"
int main() {
std::cout << "Stack: " << std::endl;
test::stack<int> a(12); // 为了不和stl库的栈命名冲突，我们把stack写在test命令空间中
std::cout << a.top() << "," << a.size() << "," << a.empty() << std::endl;
a.pop();
std::cout << a.size() << "," << a.empty() << std::endl;
a.push(123);
std::cout << a.top() << "," << a.size() << "," << a.empty() << std::endl;
a.push(1);
std::cout << a.top() << "," << a.size() << "," << a.empty() << std::endl;
return 0;
}那现在我们就很清楚了，可以先从栈的构造函数入手，首先创建文件stack/stack.h stack/stack.cpp。然后编写以下代码:
#ifndef MYDS_STACK_H
#define MYDS_STACK_H
namespace test
{
template <class T>
class stack {
public:
stack();
stack(T v);
};
}
#endif //MYDS_STACK_H然后，我们该如何存储每一个节点呢?我们可以专门写一个节点类来存，并在栈中存放栈顶元素节点的指针。
那这个节点元素就应该有两个属性: 值和指向下一个的指针。
为了方便起见，我们直接将该类的所有属性设为public，代码如下:
template <class T>
class stack_node {
public:
stack_node<T>* next = nullptr;
T value;
};接下来，我们先为stack类添加一个私有属性root来存储栈顶元素的指针:
private: stack_node<T>* root;
那么，我们可以将两种构造函数就可以出来了:
stack() : root(nullptr) {}
stack(T v) : root(new test::stack_node<T>()) {
root->value = v;
}现在，我们就可以编写其他成员函数了。
让我们回顾下，栈有哪些成员函数?
有push();pop();top();size()以及empty();
那我们就可以重新编写这个类了:
template <class T>
class stack {
public:
stack() : root(nullptr) {}
stack(T v) : root(new test::stack_node<T>()) {
root->value = v;
}
bool empty();
int size();
T top();
void pop();
void push(T v);
private:
stack_node<T>* root;
};这下，我们就可以专心致志地编写stack的逻辑代码了。
首先挑软柿子捏，把empty函数编写完成。
我们来想一下，这个栈怎样才算空呢?就是其中没有一个元素?那么如何判断没有元素呢?先编写一个size函数，查看这个栈元素个数是否零?不行，后面我们会提到，这个size函数实现会十分麻烦，而且有一个方法可以快速得判断。
那我们想一下，代码底层可以怎么想呢?，我们先看一下两个构造函数: 如果没有默认参数，就那就是一个空栈，root为空指针，而如果是第二个构造函数，那就会创建非空栈，root为指向其第一个元素的指针！
那我们就知道了，当root为空指针时，该栈就是空的！
既然如此，我们转到stack/stack.cpp中，编写如下代码:
#include "stack.h"
template <class T>
bool test::stack<T>::empty() {
return root == nullptr;
}然后我们可以再挑一个简单的top函数来先实现。因为我们的root指针就是指向该栈的顶元素的，所以直接返回root的value属性即可。
template <class T>
T test::stack<T>::top() {
return root->value;
}现在简单的地方编写完成了，接下来几个都是硬茬，不好惹，那我们可以先编写pop函数。
我们想一下，root就是存储栈顶元素的，而栈是后进先出，所以pop时就是删除root,然后将root设为root的next元素，并且如果root的next是空指针的话，就将root赋值为nullptr。
虽然有点绕，但仍然可以很快实现。
template <class T>
void test::stack<T>::pop() {
if (!root->next) {
delete root;
root = nullptr;
return;
}
stack_node<T>* test = root->next;
delete root;
root = test;
}那我们再编写push函数。
在编前，我们思考一下，该如何push呢?push一个元素时，就是栈顶多了一个元素，而root就是存储栈顶元素的，我们只要把root设置为这个新元素，并让这个新元素的next设为我们的旧root好了。
template <class T>
void test::stack<T>::push(T v)
{
if (root == nullptr) {
root = new test::stack_node<T>;
root->value = v;
return;
}
stack_node<T>* tmp1 = root;
stack_node<T>* tmp2 = new test::stack_node<T>;
tmp2->value = v;
tmp2->next = tmp1;
root = tmp2;
}接着，我们就剩下最后一个硬骨头了: size函数。我们该如何计算其的个数呢?其实也不难。我们想一想，其实我们只要遍历一遍stack,然后就看循环了几次，就有几个元素了。
那如何遍历元素呢?我们可以取root的next，然后取root的next的next，再取root的next的next的next等等等。
那我们就可以编写了:
template <class T>
int test::stack<T>::size() {
stack_node<T>* i = root;
int size = 0;
while (i != nullptr) {// 如果i是空指针就结束循环
i = i->next;
size++;
}
return size;
}现在，我们就编写完成了栈的全部代码，最后，全部代码如下:
main.cpp
#include <iostream>
#include "stack/stack.h"
#include "stack/stack.cpp"
int main() {
std::cout << "Stack: " << std::endl;
test::stack<int> a(12);
std::cout << a.top() << "," << a.size() << "," << a.empty() << std::endl;
a.pop();
std::cout << a.size() << "," << a.empty() << std::endl;
a.push(123);
std::cout << a.top() << "," << a.size() << "," << a.empty() << std::endl;
a.push(1);
std::cout << a.top() << "," << a.size() << "," << a.empty() << std::endl;
return 0;
}stack/stack.h
#ifndef MYDS_STACK_H
#define MYDS_STACK_H
namespace test
{
template <class T>
class stack_node {
public:
stack_node<T>* next = nullptr;
T value;
};
template <class T>
class stack {
public:
stack() : root(nullptr) {}
stack(T v) : root(new test::stack_node<T>()) {
root->value = v;
}
bool empty();
int size();
T top();
void pop();
void push(T v);
private:
stack_node<T>* root;
};
}
#endif //MYDS_STACK_Hstack/stack.cpp
#include "stack.h"
template <class T>
void test::stack<T>::push(T v)
{
if (root == nullptr) {
root = new test::stack_node<T>;
root->value = v;
return;
}
stack_node<T>* tmp1 = root;
stack_node<T>* tmp2 = new test::stack_node<T>;
tmp2->value = v;
tmp2->next = tmp1;
root = tmp2;
}
template <class T>
int test::stack<T>::size() {
stack_node<T>* i = root;
int size = 0;
while (i != nullptr) {
i = i->next;
size++;
}
return size;
}
template <class T>
void test::stack<T>::pop() {
if (!root->next) {
delete root;
root = nullptr;
return;
}
stack_node<T>* test = root->next;
delete root;
root = test;
}
template <class T>
T test::stack<T>::top() {
return root->value;
}
template <class T>
bool test::stack<T>::empty() {
return root == nullptr;
}(现在我们实现了栈，一次类推，你也可以试着自己实现一个队列。)
[完]
共同學習，寫下你的評論
評論加載中...
作者其他優質文章
