队列(Queue)的数组和链表实现
Introduction of Queue
队列作为一种抽象数据结构,遵循First-In-First-Out(FIFO)
原则。
它的定义如下:
A list or collection with the restriction that insertion can be performed at one end (rear) and deletion can be performed at other end (front).
队列的操作有以下几种:
- Enqueue(x) 入队列
- Dequeue( ) 出队列(并返回删除队列的值)
- front( ) and rear( )
- IsEmpty( )
以上操作的时间复杂度均为O(1).
队列的实现
用数组实现
我们分别定义两个变量front
和rear
来储存队首和队尾,队列为空时令front = -1
rear = -1
。
但是我们发现随着不断地Enqueue和Dequeue,队列逐渐后移,前面数组空间无法重复利用。于是我们采用循环数组
,循环数组可以想象成是数组首尾相连,因此我们这样表示它的位置:
current position: i
next position: (i+1)%N
previous position: (i+N-1)%N (N表示开辟数组的长度)
代码实现
- IsEmpty( )
1 | bool IsEmpty(){ |
- Enqueue( x )
1 | void Enqueue(int x){ |
- Dequeue( )
1 | void Dequeue(){ |
- front( )和rear( )
1 | int front(){ |
用链表实现
Enqueue
和Dequeue
操作必然一个在链表头一个在链表尾,为了保证两个操作的时间复杂度都是O(1),要设置两个指针front
和rear
。
代码实现
1 | struct Node{ |
队列(Queue)的数组和链表实现
http://m1yan.github.io/2023/01/11/2023111-队列(Queue)的数组和链表实现/