【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博客

---

完