学会数据结构

2. 队列

2021-05-04  本文已影响0人  Shimmer_

[TOC]

队列-Queue

又叫先进先出表;先进先出结构、只允许在一端进行插入操作、而在另一端进行删除操作的线性表。
插入数据的一端是队尾,取数据的一端则是队头

Queue接口主要方法

顺序存储队列

普通队列

数组实现,空队列时,队头、队尾下标均为0,添加元素时,队尾向后移动一位,移除元素时,队头向后移动一位。因为下标一直在往后移动,所以之前释放的元素位置无法再被利用,这样就导致了假溢出现象(无法添加,但队列并不是满的)

循环队列

队列的头尾相接的顺序存储结构。用于解决假溢出现象。

假设循环队列总容量为N,预留一个空的位置(rear永远指向为空的位置),front为头节点下标,rear为尾节点下标

  • 队列空:front==rear;
  • 队列满:(rear+1)%N==front;
  • 队列元素个数:(rear – front + N)%N 若rear能存放数据:rear>front时:(rear-front)%N+1 rear<front: (rear-front+N)%N+1
  • 移除:front = (front+1)%N
  • 增加:rear =(rear+1)%N

链式存储队列

其实就是线性表的单链表 ,只不过只能尾进头出

双端队列 Deque

Deque:是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行

优先级队列

优先级队列和通常的栈和队列一样,只不过里面的每一个元素都有一个”优先级”,在处理的时候,首先处理优先级最高的。如果两个元素具有相同的优先级,则按照他们插入到队列中的先后顺序处理。

相关算法题

上一篇 下一篇

猜你喜欢

热点阅读