注册

已有账号?请登录

登录

还没账号?请注册

基于数组实现的队列

队列是一种抽象的数据结构。队列的一端用于插入数据(入队),另一端用于删除数据(出队)。队列遵循先进先出的方法,即首先存储的数据项将首先被访问。

队列的基本操作:
1. enqueue() - 入队,将元素添加到队列中
2. dequeue() - 出队,将元素从队列中移除
3. peek() - 返回队头元素

1. 入队 enqueue()

算法

  1. 定义3个变量(queue/front/rear)和1个常量(MAXSIZE),queue表示队列数组,front表示队头位置,rear表示队尾位置,MAXSIZE表示队列最大长度
  2. 检查队列是否已满,如果队列已满(即rear==MAXSIZE-1)则退出
  3. 检查是否空队列,如果是空队列(即front==-1 && rear == -1)则将队头和队尾位置都设置成0
  4. 如果队列不为空,则队尾位置+1(即rear = rear + 1)
  5. 将元素加入到队列,即queue[rear] = data

时间复杂度:平均情况 θ(1) 最坏情况 O(1)

上述代码输出

入队前: 空队列

入队后: 队列: A B C

2. 出队 dequeue()

算法

  1. 定义3个变量(queue/front/rear)和1个常量(MAXSIZE),queue表示队列数组,front表示队头位置,rear表示队尾位置,MAXSIZE表示队列最大长度
  2. 检查是否空队列,如果是空队列(即front==-1 && rear == -1)则退出
  3. 如果队列不为空,并且队头位置等于队尾位置(即front==rear),则将front和rear都设成-1,并返回队头元素
  4. 如果队列不为空,并且队头位置不等于队尾位置(即front!=rear),则将队头位置递增1(即front=front+1),并返回队头元素

时间复杂度:平均情况 θ(1) 最坏情况 O(1)

上述代码输出

出队前: 队列: A B C D E F G H

A已出队

B已出队

C已出队

出队后: 队列: D E F G H

3. 返回队头 peek()

时间复杂度:平均情况 θ(1) 最坏情况 O(1)

上述代码输出

队头: A

本站所有文章均由阿坤原创,欢迎转载!

Copyright © 2020 luozk.com All Rights Reserved