概述
栈，是一种基本的数据结构，也是一种数据适配器。它在底层上以链表方法或动态数组方法实现。
队列的显著特点是他的添加元素与删除元素操作：先加入的元素总是被先弹出。
一个队列应该应该是这样的：
--------------STACK-------------———— ←-- ———— ←-- ———— ←-- ———— ←-- push()T1 T2 T3 T4 ———— --→ ———— --→ ———— --→ ———— --→ pop() --------------------------------bottom top()
Tn代表该元素被加入到队列的次序。
一个队列有以下三种基本行为：
top()表示对队列头元素的访问操作。如得到元素T4。
pop()表示对队列头元素的弹出操作。我们弹出T4
--------------STACK-------------———— ←-- ———— ←-- ———— ←-- push()T1 T2 T3 ———— --→ ———— --→ ———— --→ pop() --------------------------------bottom top()现在T3成为栈顶元素。
push()表示对队列尾部压入新元素。我们压入T5
--------------STACK-------------———— ←-- ———— ←-- ———— ←-- ———— ←-- push()T2 T3 T4 T5 ———— --→ ———— --→ ———— --→ ———— --→ pop() --------------------------------bottom top()现在T5成为栈顶元素。
接下来我们通过封装stack类,实现栈的一些基本功能 。（Code和测试案例附后）
考虑到在实现队列功能的文章中我们已经使用了链表，这次我们使用动态数组来实现栈。队列详见：「队列」实现FIFO队列（先进先出队列|queue）的功能 / 手撕数据结构（C++）
由于我们的动态数组实现的很完整，这使得本文章在代码部分基本不怎么需要讲解了。数组详见：「数组」实现动态数组的功能 / 手撕数据结构（C++）
命名空间
C++有自己的std命名空间下的stack，为了进行区分，封装一个自己的动态数组命名空间custom_stack。
使用namespace关键字封装，使用时可以声明using namespace custom_stack;在作用域内声明，或custom_stack::局部声明。
namespace custom_stack{...
}//作用域内声明
using namespace custom_stack;//局部声明
custom_stack::...成员变量
template <typename T>是泛型，作为数据适配器，他的数据单位应该是任意一种类型，此时暂用T表示，至于T为何物将在实例化时以<>告知。
定义class类val，封装一个成员变量：custom_dynamic_array命名空间下的array<T>示例化val动态数组。
*注意*：文末附有不封装array数组的实现方案。
数组内部详见「数组」实现动态数组的功能 / 手撕数据结构（C++）
我们使用数组来模拟栈：
栈顶是数组的最后一个元素，入栈即是在数组尾部加入新元素，出栈即是将放弃最后一个元素然后前移。
namespace custom_stack {template<typename T>class stack {private:custom_dynamic_array::array<T> val;public:...
}创建销毁
默认构造：stack(int num = 5)，接收一个num，num默认是5。为数组开为5个元素的空间。
复制构造：stack(const stack& another)，传入val执行复制构造。
移动构造：stack(stack&& another)，移动构造详见：「数组」实现动态数组的功能 / 手撕数据结构（C++）
复制赋值运算符：stack& operator=(const stack& another)，类似复制构造。
移动赋值运算符：stack& operator=(stack&& another)，类似移动构造。
由编译器给出析构函数。析构函数的内部会调用底层动态数组array的析构函数。
stack(int num = 5) :val(num) {};stack(const stack& another): val(another.val) {};stack(stack&& another) :val(std::move(another.val)) {};stack& operator=(const stack& another) {val = another.val;}stack& operator=(stack&& another) {if (this == &another)return *this;val = std::move(another.val);}数据控制
获取长度：size_t size()，返回array类型的val内部的val_size。
判断为空：bool empty()，返回array类型的val内部的val_size ? false : true。
队顶压入：void push(T&& elem)，在数组尾加入新元素。（T&&作为万能引用，此处不表）
队顶弹出：void pop()，数组尾前移。（数组的接口函数内部使用assert断言数组不能为空）
内部交换：void swap(stack& another)，直接交换底层数组。
bool empty()const{return val.empty();}size_t size()const{return val.size();}void push(T&& elem) {val.push_back(std::forward<T>(elem));}void pop() {val.pop_back();}void swap(stack& another) {val.swap(another.val);}
数据访问
访问栈顶：const T& top()，断言数组长度大于0后，返回数组的尾元素。
const T& top()const {assert(val.size() > 0);return val[val.size() - 1];}Code
*注意*：笔者包含了位于其他位置的array头文件。
#pragma once
#include <custom\array.h>
namespace custom_stack {template<typename T>class stack {private:custom_dynamic_array::array<T> val;public:stack(int num = 5) :val(num) {};stack(const stack& another): val(another.val) {};stack(stack&& another) :val(std::move(another.val)) {};stack& operator=(const stack& another) {val = another.val;}stack& operator=(stack&& another) {if (this == &another)return *this;val = std::move(another.val);}bool empty(){return val.empty();}size_t size(){return val.size();}void push(T &&elem) {val.push_back(std::forward<T>(elem));}void pop() {val.pop_back();}void swap(stack& another) {val.swap(another.val);}const T& top() {assert(val.size() > 0);return val[val.size() - 1];}};
}测试
#include <iostream>
#include "stack.h"
using namespace std;
int main() {custom_stack::stack<char>stk1;std::cout << "---------------test1---------------" << std::endl;for (int i = 0; i < 10; i++) {stk1.push(i + 'a');cout << char(i + 'a');}cout << endl;std::cout << "-----------------------------------" << std::endl;std::cout << "---------------test2---------------" << std::endl;custom_stack::stack<char>stk2(stk1);for (int i = 0; i < 10; i++) {cout << stk2.top();stk2.pop();}std::cout << endl;std::cout << "-----------------------------------" << std::endl;return 0;
}
另附
不嵌套底层array类的栈结构。
#include <cassert>
#ifndef CUSTOM_STACK
#define CSUTOM_STACK
namespace custom_stack {template<typename T>class stack {private:T* val;size_t val_size;size_t val_capacity;public:stack(int num = 1) :val_size(0),val_capacity(num) {val = new T[num];};stack(const stack& another) : val_size(another.val_size), val_capacity(another.val_capacity) {//拷贝构造val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);}stack(stack&& another) noexcept : val_size(another.val_size), val_capacity(another.val_capacity) {//移动构造val = another.val;another.val = nullptr;}stack& operator=(const stack& another) {delete[]val;val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);val_size = another.val_size;val_capacity = another.val_capacity;return *this;}stack& operator=(stack&& another) {if (this == &another)return *this;delete[]val;val = another.val;val_size = another.val_size;val_capacity = another.val_capacity;another.val = nullptr;return *this;}bool empty()const {return val_size?false:true;}size_t size()const {return val_size;}void reserve(const int num) {if (num > val_capacity) {T* temp = new T[num];memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_capacity = num;}}template<typename V>void push(V&& elem) {if (val_capacity - val_size <= 1)reserve(val_capacity * 2);val[val_size++] = elem;}void pop() {assert(val_size > 0);val_size--;}const T& top()const {assert(val_size > 0);return val[val_size - 1];}};
}
#endif
