当前位置：首页 > news >正文

「栈」实现LIFO栈（先进后出栈|堆栈|stack）的功能 / 手撕数据结构（C++）

news 来源：原创 2024/9/20 0:27:36

概述

栈，是一种基本的数据结构，也是一种数据适配器。它在底层上以链表方法或动态数组方法实现。

队列的显著特点是他的添加元素与删除元素操作：先加入的元素总是被先弹出。

一个队列应该应该是这样的：

          --------------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类queue，封装一个成员变量：custom_dynamic_array命名空间下的array<T>示例化val动态数组。

数组内部详见「数组」实现动态数组的功能 / 手撕数据结构（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;
}