数据结构与算法栈和队列

1.栈的基本概念
只允许在一端进行插入或删除操作的线性表，先进后出

结构：
栈顶（Top）：线性表允许进行插入和删除的那一端
栈低（Bottom）：固定的，不允许进行插入和删除的另一端

卡特兰数：n个不同元素进栈，出栈元素不同排列的个数为

2.栈的顺序存储结构
顺序栈：采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈低到栈顶的数据元素，同时附设一个指针(top）指示当前栈顶元素的位置

共享栈：让两个顺序栈共享一个一维数组空间，将两个栈的栈低分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

3.栈的链式存储结构
采用单链表实现，并规定所有操作都是在单链表的表头进行
优点：便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况

4.队列的基本概念
队列的定义：是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，先进先出

结构：
队头Front：允许删除的一端又称队首
队尾Rear：允许插入的一端
空队列：不含任何元素的空表

5.队列的顺序存储结构
队列的顺序存储：分配一端连续的存储单元存放队列中的元素，并附设两个指针

循环队列：把存储队列元素的表从逻辑上视为一个环

6.队列的链式存储结构
队列的链式表示称为链队列，是一个同时带有队头和队尾的单链表

优点：适合于数据元素变动比较大的情形，不存在队列满且产生溢出的问题

7.双端队列
概述：双端队列是指允许两端都可以进行入队和出对操作的队列，逻辑结构仍是线性结构，将队列的两端分别称为前端和后端，两端都可以入队和出对

分类：
输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列