数据结构——栈与队列_栈pop和push的时间复杂度

一 栈

1.1 定义

1. 是指仅限在表尾进行插入删除操作的线性表。 特点是先进后出。

1.2 顺序栈

1. 数组的简化， 限制了插入删除只能在表尾进行。

1.3 链式栈

1.在单链表的基础上加一层限制， 只能在表尾做插入插入删除的操作。

1.4 时间复杂度

1.顺序栈和链式栈的出栈（pop）和进栈（push）时间复杂度都是O(1)。

1.5 顺序栈和链式栈的区别

1. 顺序栈需要提前确定一个固定长度， 可能会存在内存空间浪费的问题， 但是他的优势是存取时定位很方便。
2. 链式栈要求每个元素都有指针域， 这同时也增加了一些内存开销， 但是对于栈的长度无限制。
3. 如果栈的使用过程中元素变化不可预料， 可以考虑使用链式栈。 如果他的变化在可控范围内， 可以考虑使用顺序栈。

二 队列

2.1 定义

1. 是指只允许在队尾进行插入操作， 在队头进行删除操作得一种线性表。特点是先进先出。

2.2 顺序队列

1. 数组的简化， 限制了只允许在队尾进行插入操作， 在队头进行删除操作。

2.3 循环队列

1.把队列的头尾相接的顺序储存结构称为循环队列。

2.3 链式队列

1.在单链表的基础上加一层限制，只允许在队尾进行插入操作， 在队头进行删除操作。

2.4 时间复杂度

1. 顺序队列的出队操作的时间复杂度是O(n)，入队操作是O(1)。
2. 链式队列的出队操作的时间复杂度是O(1)，入队操作是O(1)。
3. 循环队列的出队操作的时间复杂度是O(1)，入队操作是O(1)。

2.5 循环队列和链式队列的区别

1. 循环队列是事先申请空间， 使用期间不释放。循环队列必须要有一个固定的长度， 存储的元素数量有限制，以及空间浪费的问题。
2. 链式队列不需要提前申请空间， 不存在元素数量限制问题， 但是他需要额外的指针域，需要占用一定的内存空间。
3. 如果队列长度可以确定的情况下可以使用循环队列， 如果无法估计长度， 可以使用链式队列。