2.1 栈和队列的基本概念

2.1.1 栈的基本概念

1、栈的定义

栈是一种只能在一端进行插入或者删除操作的线性表。其中允许进行插入和删除的一段被称为栈顶（Top）。表的另一端称为栈底。栈底是固定不变的，元素插入栈称为压栈（push），删除元素称为出栈（pop）。

2、栈的特点

栈的主要特点是先入后出（FILO)(FRIST IN LAST OUT)，就好像将东西压进一个箱子里，只有当上面的东西取出以后才能将最里面的东西取出。

3、栈的存储结构

栈的本质仍是线性表，所以也分为顺序栈和链式栈。

4、栈的数学性质

当n个元素以某种顺序进栈，并且可以在任意时刻出栈（满足先入先出的前提下）时，所获得的元素排列的数目N恰好为Catalan数，即
$$N=\frac{1}{n+1}{C}_{2n}^n$$

3.1.2 队列的基本概念

1、队列的定义

队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入，在表的另一端进行删除。可进行插入的一端称为队尾（rear），可进行删除的一端称为队头（front）。向队列中插入新元素称为进队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队，元素出队以后，其后继元素就成为新的队头元素。

2、队的特点

队列的特点就是先进先出（FIFO)(FIRST IN FIRST OUT)。就像现实中的排队，先来排队的人就能先去办理业务。

3、队列的存储结构

队列按存储结构可以分为顺序队与链队