【C++】简易栈的实现

• 程序说明
• • 一、博客日期
  • 二、引言
• 版权声明
• 开发环境
• • 一、开发配置
  • 二、开发工具
• 效果演示
• 核心代码
• • 一、构造类
  • • （一）默认长度构造
    • （二）带自扩容构造
    • （三）带初始长度构造
    • （四）析构
  • 二、重载运算符
  • • （一）加法重载运算符
    • （二）复合加法重载运算符
  • 三、基本操作
  • • （一）入栈
    • （二）出栈
    • （三）读栈
    • （四）获长
    • （五）打印
    • （六）允扩
  • 四、测试
  • • （一）测试代码
    • （二）应示效果
• 全部代码
• 结语
• 参考文献

程序说明

一、博客日期

本文第一次发布

2023年03月19日22点30分

Authors

THDMI

二、引言

简单记录下，模板的使用，目前尚且还有一个问题就是，在重载加法运算符的过程中，使用malloc产生的类要怎么手动释放，目前在主函数好像不能直接free了，不确定它会不会自动析构。

代码主要描述了一个简单的栈，实现的过程，太久没用C++了，算是复习一下，另外模板也是第二次用，重载运算符是第一次用，嗯，之前都完全没用到，虽然看过教程，这次算是动手实践，但是内存泄露还是存在。

实际上想加入根据传入的数组初始化栈的，但是想了很久没想出要怎么在未知数组长度情况下，计算一个数组类型的一级指针参数的长度。

版权声明

本工程作品均为本文作者撰写，无其他参考，允许使用在任何场景，作品遵循GPLv3.0开源协议。转载本文请标注出处。

开发环境

一、开发配置

操作系统

Microsoft Windows10 家庭版 20H2

二、开发工具

效果演示

具体测试理论效果参考测试部分。

核心代码

一、构造类

（一）默认长度构造

template  Stack::Stack() {this->stack_array = (T*)malloc(sizeof(T) * this->default_stack_len);this->len_max = this->default_stack_len;this->len = 0;
}

（二）带自扩容构造

template  Stack::Stack(bool is_auto_expand) {this->stack_array = (T*)malloc(sizeof(T) * this->default_stack_len);this->len_max = this->default_stack_len;this->len = 0;this->is_auto_expand = true;
}

（三）带初始长度构造

template  Stack::Stack(int stack_len) {this->stack_array = (T*)malloc(sizeof(T) * stack_len);this->len_max = stack_len;this->len = 0;
}

（四）析构

template  Stack::~Stack() {if (nullptr == this->stack_array) {return;}free(this->stack_array);this->stack_array = nullptr;
}

二、重载运算符

（一）加法重载运算符

template  Stack& Stack::operator+(Stack& stack_add) {Stack* new_stack = (Stack*)malloc(sizeof(Stack));new_stack->len = 0;new_stack->len_max = this->len + stack_add.get_len();if (nullptr != new_stack->stack_array) {free(new_stack->stack_array);}new_stack->stack_array = (T*)malloc(sizeof(T) * new_stack->len_max);for (int i = 0; i < this->len; i++) {new_stack->push(this->stack_array[i]);}for (int i = 0; i < stack_add.get_len(); i++) {new_stack->push(stack_add.stack_array[i]);}return *new_stack;
}

（二）复合加法重载运算符

template  Stack& Stack::operator+=(Stack& st) {if (nullptr == this->stack_array) {return *this;}if (this->len_max < this->len + st.len) {this->len_max += st.len;}T* temp = (T*)malloc(sizeof(T) * this->len_max);for (int i = 0; i < this->len; i++) {temp[i] = this->stack_array[i];}free(this->stack_array);this->stack_array = temp;temp = nullptr;for (int i = 0; i < st.len; i++) {this->push(st.stack_array[i]);}return *this;
}

三、基本操作

（一）入栈

template  Rt Stack::push(T ele) {Rt rt;if (this->len_max <= this->len) {if (this->is_auto_expand) {T *tmp = (T*)malloc(sizeof(T) * (this->len_max + this->default_stack_len));this->len_max += this->default_stack_len;memcpy(tmp, this->stack_array, this->len * sizeof(T));free(this->stack_array);this->stack_array = tmp;} else {rt.flag = false;return rt;}}++this->len;this->stack_array[this->len - 1] = ele;rt.flag = true;return rt;
}

（二）出栈

template  Rt Stack::pull() {Rt rt;if (this->len <= 0) {rt.flag = false;return rt;}rt.data = this->stack_array[this->len - 1];--this->len;rt.flag = true;return rt;
}

（三）读栈

template  Rt Stack::read() {Rt rt;if (this->len <= 0) {rt.flag = false;return rt;}rt.data = this->stack_array[len - 1];rt.flag = true;return rt;
}

（四）获长

template  int Stack::get_len() {return this->len; 
}

（五）打印

template  void Stack::print() {for (int i = 0; i < this->len; i++) {std::cout << this->stack_array[i] << "\t";}std::cout << std::endl;
}

（六）允扩

template  void Stack::auto_expand_set(bool option) {this->is_auto_expand = option;
}

四、测试

（一）测试代码

    Stack st1 = Stack();Stack st2 = Stack();Stack st3;for (int i = 0; i < 8; i++) {st1.push("abc");}for (int i = 0; i < 12; i++) {st2.push("bcd");}std::cout << "Stack 01: ";st1.print();std::cout << "\nStack 02: ";st2.print();st1 += st2;std::cout << "\nStack 01: ";st1.print();st3 = st1 + st2;std::cout << "\nStack 03: ";st3.print();

（二）应示效果

1. st1会入栈8个元素，st2会入栈8个元素
2. 因为st2允许自动扩容，所以还会再入4个元素
3. st1和st2组合，st1会扩容，st2全部元素会追加在st1末尾
4. st3将拥有实例，装载有组合后的st1，再次与st2组合

全部代码

#include 
#include 
#include 
#include class None {};template  class Rt {public:bool flag;T data;
};template  class Stack {private:int default_stack_len = 8;bool is_auto_expand = false;T* stack_array;int len;int len_max;public:Stack();Stack(bool is_auto_expand);Stack(int stack_len);~Stack();Stack& operator+(Stack& stack_add);Stack& operator+=(Stack& st);void auto_expand_set(bool option);int get_len();void print();Rt push(T ele);Rt pull();Rt read();
};template  Stack& Stack::operator+(Stack& stack_add) {Stack* new_stack = (Stack*)malloc(sizeof(Stack));new_stack->len = 0;new_stack->len_max = this->len + stack_add.get_len();if (nullptr != new_stack->stack_array) {free(new_stack->stack_array);}new_stack->stack_array = (T*)malloc(sizeof(T) * new_stack->len_max);for (int i = 0; i < this->len; i++) {new_stack->push(this->stack_array[i]);}for (int i = 0; i < stack_add.get_len(); i++) {new_stack->push(stack_add.stack_array[i]);}return *new_stack;
}template  Stack& Stack::operator+=(Stack& st) {if (nullptr == this->stack_array) {return *this;}if (this->len_max < this->len + st.len) {this->len_max += st.len;}T* temp = (T*)malloc(sizeof(T) * this->len_max);for (int i = 0; i < this->len; i++) {temp[i] = this->stack_array[i];}free(this->stack_array);this->stack_array = temp;temp = nullptr;for (int i = 0; i < st.len; i++) {this->push(st.stack_array[i]);}return *this;
}template  Stack::Stack() {this->stack_array = (T*)malloc(sizeof(T) * this->default_stack_len);this->len_max = this->default_stack_len;this->len = 0;
}template  Stack::Stack(bool is_auto_expand) {this->stack_array = (T*)malloc(sizeof(T) * this->default_stack_len);this->len_max = this->default_stack_len;this->len = 0;this->is_auto_expand = true;
}template  Stack::Stack(int stack_len) {this->stack_array = (T*)malloc(sizeof(T) * stack_len);this->len_max = stack_len;this->len = 0;
}template  Stack::~Stack() {if (nullptr == this->stack_array) {return;}free(this->stack_array);this->stack_array = nullptr;
}template  void Stack::auto_expand_set(bool option) {this->is_auto_expand = option;
}template  int Stack::get_len() {return this->len;
}template  void Stack::print() {for (int i = 0; i < this->len; i++) {std::cout << this->stack_array[i] << "\t";}std::cout << std::endl;
}template  Rt Stack::push(T ele) {Rt rt;if (this->len_max <= this->len) {if (this->is_auto_expand) {T* tmp = (T*)malloc(sizeof(T) *(this->len_max + this->default_stack_len));this->len_max += this->default_stack_len;memcpy(tmp, this->stack_array, this->len * sizeof(T));// for (int i = 0; i < this->len; i ++) {//     tmp[i] = this->stack_array[i];// }free(this->stack_array);this->stack_array = tmp;} else {rt.flag = false;return rt;}}++this->len;this->stack_array[this->len - 1] = ele;rt.flag = true;return rt;
}template  Rt Stack::pull() {Rt rt;if (this->len <= 0) {rt.flag = false;return rt;}rt.data = this->stack_array[this->len - 1];--this->len;rt.flag = true;return rt;
}template  Rt Stack::read() {Rt rt;if (this->len <= 0) {rt.flag = false;return rt;}rt.data = this->stack_array[len - 1];rt.flag = true;return rt;
}int main() {Stack st1 = Stack();Stack st2 = Stack(true);Stack st3;for (int i = 0; i < 8; i++) {st1.push("abc");}for (int i = 0; i < 12; i++) {st2.push("bcd");}std::cout << "Stack 01: ";st1.print();std::cout << "\nStack 02: ";st2.print();st1 += st2;std::cout << "\nStack 01: ";st1.print();st3 = st1 + st2;std::cout << "\nStack 03: ";st3.print();
}

结语

多看、多查、多练

参考文献

[1] C++ Primer 第5版 中文版 (Stanley B. Lippman等著，王刚等译)

END