栈 c++

《格式有时间修一下》
栈：
基本概念：
1.特点：仅操作表尾，后入先出（Last In First Out,LIFO）。
2.相关概念
栈顶与栈底：允许操作一端为栈顶（数据的后一个空位置），另一端为栈底。
压栈与弹栈：插入删除操作。
3.栈操作：
1.弹栈
2.压栈
3.栈大小
4.栈是否为空
5.栈顶元素值
4.实现方式：线性表
1.顺序表，数组头为栈底，数组尾为栈顶
2.链表，头节点为栈顶。
5.编程实现（c++）
1.对于标准库栈,定义及相关函数：

> #include`  //头文件
> `stack s;`  //定义
> s.empty(); //是否为空，空 = true
> s.size(); //栈元素个数
> s.top(); //访问栈顶
> s.pop(); //弹栈不返回值
> s.push(1);//将1压栈

2.顺序表实现
数据结构顺序栈C++实现

#include 
#include 
using namespace std;
#include 
template

class ArrayStack : public stack {
	public:
		ArrayStack(int s = 10): count(0), capacity(s) {
			array = new T[capacity];  //有new要清除内存
			assert(array != nullptr);
		}
		~ArrayStack() { //析构函数
			delete[]array;
			cout << "delete arraystack" << endl;
		};

	public:
		T top() {             //获取栈顶元素
			if (count != 0) {
				return array[count - 1];
			}
		}

		void push(T t) {      //压栈操作,先压后加
			if (count != capacity) {
				array[count++] = t;
			}
		}
		T pop() {           //弹栈操作，先减后弹
			if (count != 0) {
				return array[--count];
			}
		}
		bool isEmpty() {      //判空操作
			return count == 0;
		}
		int size() {           //求栈的大小
			return count;
		}
	private:
		int count;            //栈的元素数量
		int capacity;        //栈的容量
		T *array;             //底层为数组
};

int main() {
	ArrayStack mystack;
	for (int i = 0; i < 5; i++) {
		mystack.push(i);
	}
	cout << mystack.size() << endl;
	cout << mystack.isEmpty() << endl;
	cout << mystack.top() << endl;
	cout << "Out";
	while (!mystack.isEmpty()) {
		cout << mystack.pop() << ">>";
	}
	cout << endl;
	return 0;

}

3.链表实现
数据结构单向链表的C++实现

#include 
using namespace std;

template 
class LinkedList; //在Node前声明，防止报错
template 
class Node {
	public:
		Node *d_next;
		T d_data;
	public:
		Node(): d_next(nullptr), d_data( ) {
		}
		Node(T t): d_data(t), d_next(nullptr) {
		}
		Node(T t, Node *next): d_data(t), d_next(next) {
		}
		//~Node() {}  //析构函数，待补充
		//lianbiaodayin
};
template 

class LinkedList {
	public:
		Node *d_head;
		int d_size;
	public:
		LinkedList() { //构造链表栈
			d_head = new Node();
			d_size = 0;
		}
		//	~LinkedList();//析构
		int size() {
			return d_size;
		}
		void push_stack(T t) { //入栈
			Node *q = new Node(t, d_head);
			d_head = q;
			d_size++;
		}
		T delete_stack() { //出栈
			if (d_size <= 0)
				abort();
			Node *q = d_head;
			d_head = q->d_next;
			T data = q->d_data;
			delete (q);
			d_size--;
			return data;
		}
		void deleteall() { //清空栈
			while (d_size > 0) {
				delete_stack();
			}
		}

		bool isEmpty() { //是否为空
			return (d_size == 0);
		}
		T GetStackTop() { //获取栈顶元素
			return d_head->d_data;
		}
};

int main() {
	LinkedList nhead;
	for (int i = 0; i < 5; i++) {
		nhead.push_stack(i);
		cout << nhead.GetStackTop();
	}
	cout << endl;

	cout << "out" << nhead.delete_stack() << endl;
	cout << "isempty?" << nhead.isEmpty() << endl;
	cout << "top" << nhead.GetStackTop() << endl;
	nhead.deleteall();
	cout << nhead.d_head->d_data << endl;
	return 0;
};

6.应用
1.后入先出链表
2.括号题
3.单调栈（构造）
解一：使用差值或下标
解二：辅助栈
解三：单调递增栈（）
解四：最大值问题（接水滴）