Java教程

数据结构与算法——队列

本文主要是介绍数据结构与算法——队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

栈和队列是两种在运算时要受到某些特殊限制的线性表,故也称为限定性的数据结构。

1.概念

  定义:队列是指限定只能在表的一端(队尾rear)进行插入,在表的另一端(队头front)进行删除的线性表。 

  修改原则:先进先出或后进后出(Frist In Frist Out,FIFO) 

 

 2.队列的操作

  空队列时:rear=front=-1

  元素个数:rear-front

  元素入队:rear+1

  元素出队:front+1

  非空队列时:rear始终指向队头元素的前一个位置,而front始终指向队尾元素的位置。

3.队列的典型应用

  打印队列和时间排队等。

4.队列的存储结构  

  队列的存储结构有顺序存储和链式存储。

  ①队列的顺序存储:指用一组地址连续的存储单元存放队列中的元素,由于队列中的元素的插入和删除限定在队列的两端进行,因此设置队头指针和队尾指针,分别指示当前的队首元素和队尾元素。

  ②栈的链式存储(链队列):用链表表示的队列。

  ③为了方便操作,给链队列添加一个头结点,并令头指针指向头结点。队列为空的判定条件是:头指针和尾指针的值相同,且均指向头结点。

5.循环队列

  循环队列是指首尾相接的队列,逻辑上形成一个环状。

  MAXSIAZE:循环队列最大容量 

  n:当前队列中元素的个数

  入队:rear=(rear+1)mod MAXSIZE

  出队:rear=(front+1)mod MAXSIZE

  空队列判断条件:front=rear,且n=0

  满队列判断条件:front=rear,且n=MAXSIZE

  循环队列元素个数:n=(rear-front+MAXSIZE)mod MAXSIZE

  循环队列中,rear可以大于front,front也可以大于rear 

 

 

 

 

 

 

 

 

 

 

这篇关于数据结构与算法——队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!