如何理解队列？ -

LQJ2711

浏览: 5491 次
性别:

最近访客更多访客>>

娜娜TX

suifan繁

UMyeyes

yangnier

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

如何理解队列？

博客分类：

Java中级

我们在学习的阶段时,对一些数据结构的概念、用法，比如:队列。总是不那么熟悉，相信大部分初学者都感同身受，所以在此，我向大家分享一下自己如何将队列的概念、用法融汇贯通的。

对于数据结构中队列的学习，我认为可以分三个阶段:

1.字面理解阶段:

　队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

（1）允许删除的一端称为队头（head）。
　　（2）允许插入的一端称为队尾（last）。
　　（3）当队列中没有元素时称为空队列。
　　（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
　队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队[不能插队]），即当前"最老的"成员离队。
　【例】在队列中依次加入元素a₁，a₂，…，a_n之后，a₁是队头元素，a_n是队尾元素。退出队列的次序只能是a₁，a₂，…，a_n。

图例:

2、画图理解阶段与3、实现理解阶段

1）先确定存储数据的容器。

a、基于数组

//定义一个储存数据的数组，初始化长度为0
Object[] src = new Object[0];

b、基于链表

/**
 * 链式结构内部结点类，双链表
 * 
 * @author Administrator
 *
 */
class SNODE<E> {
	// 内容
	E data;
	// 对下一个结点的引用
	SNODE<E> netx = null;
	// 对下一个结点的引用
	SNODE<E> front = null;
	//空的构造函数,用于构造空值的结点
	public SNODE() {
	}
	//构造有值的结点
	public SNODE(E e) {
		data = e;
	}
}


	//定义一个储存数据的链表，头结点初始值为null
	public SNODE<E> head = null;
	//尾结点初始值为null
	private SNODE<E> last = null;
	//定义一个变量保存栈的长度
	private int num = 0;

2）增加操作

a、基于数组

图例:

图例解析:将数组src全部复制到数组dest中，再将新数据添到数组dest的最后一位，最后将数组dest赋予数组src，还原数组。

	/**
	 * 将数据压入队列
	 * @param e 压入数据
	 */
	public void put(E e){
		//新建一个临时数组dest，长度比数组src大1
		Object[] dest = new Object[src.length+1];
		//将增加的数据添到数组dest的末尾
		dest[src.length]=e;
		//将数组src的数据复制到数组dest中
		System.arraycopy(src, 0, dest, 0, src.length);
		//将临时数组dest赋予数组src，还原数组src
		src=dest;		
	}

b、基于链表

图例:

图例解析:先将尾节点last的next指向新结点node

再将新结点node的front指向尾节点last

再将尾节点last指向新结点node

	/**
	 * 将数据放入队列
	 * 
	 * @param e
	 *            放入数据
	 */
	public void put(E e) {
		//建立一个新结点node,值为e,默认无指向
		SNODE<E> node = new SNODE<E>(e);
		//如果栈内没有数据
		if (head == null) {
			//头结点指向新结点node
			head = node;
			//尾结点指向新结点node
			last = node;
			//node结点的front指向null
			node.front = null;
			//node结点的netx指向null
			node.netx = null;
		} else {
			//将尾节点last的netx指向新结点node
			last.netx=node;
			//新结点node的front指向last
			node.front = last;
			//新结点node的netx指向null
			node.netx=null;
			//尾节点last后移一位
			last = node;
		}
		//栈的长度+1
		num++;
	}

3）删除操作

a、基于数组

图例:

图例解析:将数组src从第二个全部复制到数组dest[下标从0开始]中，再将新数据赋予临时变量e，最后将数组dest赋予数组src，还原数组，返回输出e。

	/**
	 * 将队列底部数据弹出来
	 * @return 队列底部数据
	 */
	public E poll(){
		//新建一个临时数组dest，长度比数组src小1
		Object[] dest = new Object[src.length-1];
		//将数组src的数据复制到数组dest中，不包括数组src的第一个元素，其他的元素依次复制到数组dest对应位置
		System.arraycopy(src, 1, dest, 0, dest.length);
		//定义一个临时变量装数组src的第一个元素
		E e=(E)src[0];
		//将临时数组dest赋予数组src，还原数组src
		src=dest;
		//返回临时变量e
		return e;
	}

b、基于链表

图例:

图例解析:先将新结点node指向头结点head

再将头节点head指向新结点node的下一个结点

再将旧头结点的next置为空，新头结点的front置为空，最后返回输出旧头结点的值

	/**
	 * 将队列底部数据取出来
	 * 
	 * @return 队列底部数据
	 */
	public E poll() {
		//如果栈内有数据
		if (head.data!= null) {
			//建立一个新结点node,值为空,默认无指向
			SNODE<E> node = new SNODE<E>();
			// 将node指向头结点
			node = head;
			// 头结点head的指向移到下一个结点
			head = node.netx;
			// 旧头结点的指向关系为null
			node.netx = null;
   
			// 新头结点的指向关系为null

			head.front = null;
			//栈长度-1
			num--;
			//返回输出原队列顶部的数据
			return node.data;
		}
		//栈内没有数据就返回输出null
		return null;
	}

4）判断队列是否为空

	/**
	 * 获得队列长度,基于链表实现[基于数组实现:num改成src.length]
	 * 
	 * @return 队列长度
	 */
	public int size() {
		//返回栈的长度
		return num;
	}

5）获得队列长度

	/**
	 * 判断队列是否为空,基于链表实现[基于数组实现:num改成src.length]
	 * 
	 * @return true/false
	 */
	public boolean isEmpty() {
		//如果栈长度是0就返回false
		if (num == 0) {
			return true;
		} else {//否则就返回true
			return false;
		}
	}