【C++/数据结构】栈

零.导言

        栈是一种数据结构，在后续的学习中可能经常使用，因此我们今天就来学习如何实现栈，以更好地使用它。

---

一.栈的实现

        栈的形式如下：

#include<iostream>
#include<cassert>using namespace std;typedef int StackDataType;class Stack
{
public:Stack(int capacity = 4){_arr = (StackDataType*)malloc(4 * sizeof(StackDataType));_capacity = capacity;_top = 0;}~Stack(){free(_arr);_capacity = _top = 0;}void Push(StackDataType n){if (_capacity == _top){int newcapacity = 2 * _capacity;StackDataType* tmp = (StackDataType*)realloc(_arr, newcapacity * sizeof(StackDataType));if (tmp == 0){perror("reralloc fail!");exit(1);}_arr = tmp;_capacity = newcapacity;}_arr[_top++] = n;}bool isEmpty(){return _top == 0;}void Pop(){assert(!isEmpty());_top--;}StackDataType Top(){assert(!isEmpty());return _arr[_top - 1];}private:StackDataType* _arr;int _capacity;int _top;
};

---

二.栈的相关解释

         在类（class）Stack 中，包含成员变量和成员函数；其中，_arr，_capacity，_top，都是私有的，不能在类外直接使用。而其成员函数，如Stack，~Stack，Push，Pop等等是公有的，可以在类外使用。

        Push的作用是在栈顶插入一个数据，Pop的作用是删除栈顶的一个数据，Top的作用是去除且不删除栈顶的数据。

        Stack 和 ~Stack 的作用是初始化和销毁栈。

---

三.栈的特性

        栈的特性是先进后出，即先存进的类容要等后存进的类容取出后才能取出。运用这个特性，我们可以便捷的解决很多问题。

---

四.相关链接

        【C++/数据结构】队列的模拟实现-CSDN博客

---

完