通俗易懂解释 栈

1 什么是栈？栈有哪些优点

1.1 栈的相关概念

1. 栈（stack）是一种线性存储结构，它具有如下的特点：
   1.1 栈中的数据元素 遵守这先进后去的原则
   1.2 限定只能在栈顶进行插入和删除操作

2. 栈的相关概念：
   2.1 栈顶于栈底：允许元素插入与删除的一端称为栈顶。另一端称为栈底
   2.2 压栈：栈的插入朝左，叫做进栈，也称压栈、入栈
   2.3 弹栈：栈的删除操作，也叫做出栈

1.2 栈的操作

栈的常规操作为：
1.出栈，通常命名为pop
2.进栈，通常命名为push
3.求栈的大小
4.判断栈是否为空
5.获取栈顶元素的值

2 栈的实现

栈既然是一种线性结构，就能够以数组或者链表（单向链表、双向链表、循环链表）作为底层数据结构。
本文我们以数组、单向链表为底层数据结构 构建栈

2.1 基于数组的栈实现

当以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向：

s.empty(); //如果栈为空则返回true, 否则返回false;
s.size(); //返回栈中元素的个数
s.top(); //返回栈顶元素, 但不删除该元素
s.pop(); //弹出栈顶元素, 但不返回其值
s.push(); //将元素压入栈顶

#include <stack>
#include <iostream>
using namespace std;
 
int main()
{
	stack<int> mystack;
	int sum = 0;
	for (int i = 0; i <= 10; i++){
		mystack.push(i);
	}
	cout << "size is " << mystack.size() << endl;
	while (!mystack.empty()){
		cout << " " << mystack.top();
		mystack.pop();
	}
	cout << endl;
	system("pause");
	return 0;
}
//size is 11
// 10 9 8 7 6 5 4 3 2 1 0

2.2 基于单链表的栈

#include <iostream>
using namespace std;
template<class T>class Stack
{
private:
	struct Node
	{
		T data;
		Node *next;
	};
	Node *head;
	Node *p;
	int length;
 
public:
	Stack()
	{
		head = NULL;
		length = 0;
	}
	void push(T n)//入栈
	{
		Node *q = new Node;
		q->data = n;
		if (head == NULL)
		{
			q->next = head;
			head = q;
			p = q;
		}
		else
		{
			q->next = p;
			p = q;
		}
		length++;
	}
 
	T pop()//出栈并且将出栈的元素返回
	{
		if (length <= 0)
		{
			abort();
		}
		Node *q;
		T data;
		q = p;
		data = p->data;
		p = p->next;
		delete(q);
		length--;
		return data;
	}
	int size()//返回元素个数
	{
		return length;
	}
	T top()//返回栈顶元素
	{
		return p->data;
	}
	bool isEmpty()//判断栈是不是空的
	{
		if (length == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	void clear()//清空栈中的所有元素
	{
		while (length > 0)
		{
			pop();
		}
	}
};
int main()
{
	Stack<char> s;
	s.push('a');
	s.push('b');
	s.push('c');
	while (!s.isEmpty())
	{
		cout << s.pop() << endl;
	}
	system("pause");
	return 0;
}

参考：
https://blog.csdn.net/zichen_ziqi/article/details/80807989