码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


Java中队列的实现——菜鸟学数据结构(三)

上次文章说到Java中栈的实现,这次楠哥和大家一起学习Java中队列的实现。事实上,队列(Queue)这种数据结构其实和linklist十分的相似,只是在linklist当中可以直接的获取每一个结点的值,而queue只能从一端获取。严格意义上说,队列有很多种,如FIFO队列(先进先出)、LIFO队列(后进先出)和Priority队列(优先级队列)。通常所说的队列即为FIFO队列,而栈其实就是LIFO队列。对于Priority队列,因为涉及到排序算法,将在本系列文章的后面进行分析。(楠哥计算机学习网www.liubonan.com)

Java有已经写好的Queue类,通常编程当中可以直接使用,本文为了深入分析数据结构的细节,所以自己定义这样一个类。在Java中实现队列,和linklist方法基本一致。Queue类中需要定义两个成员属性header和tail,用于记录队首元素和队尾元素。事实上,可以不记录tail,但是这样的话,会耗费很多的时间用于寻找队尾,对于push操作十分的不合算。Pop,Push和Peek操作与栈的实现基本相似,因为前文中使用char作为数据类型,本次使用int型给出样例代码。(楠哥计算机学习网www.liubonan.com)

package ds;
//楠哥计算机学习网www.liubonan.com
public class Node {

	private char data;
	private Node next;

	public Node (char data)
	{
		this.setData(data);
		this.setNext(null);
	}

	public char getData() {
		return data;
	}
	public void setData(char data) {
		this.data = data;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}
//楠哥计算机学习网www.liubonan.com
public class Queue {

	private Node head,tail;

	public Queue (){}

	public void init(char data)
	{
		head = new Node(data);
		tail = head;
	}

	public void push(char data)
	{
		Node temp = new Node(data);
		tail.setNext(temp);
		tail = tail.getNext();
	}

	public char pop()
	{
		Node temp = head;
		head = head.getNext();
		return temp.getData();
	}
        //楠哥计算机学习网www.liubonan.com
	public char peek()
	{
		return head.getData();
	}

	public boolean empty()
	{
		if(head == null)
			return true;
		else
			return false;
	}

}
package ds;
//楠哥计算机学习网www.liubonan.com
public class Tester {

	public static void main(String[] args)
	{
		Queue q= new Queue();
		String test = "abcdefghijklmn";

		q.init(test.charAt(0));	

		for(int i = 1; i < test.length(); i++)
			q.push(test.charAt(i));

		while(!q.empty())
		{
			System.out.print(q.peek()+" ");
			System.out.print(q.pop() + " ");
		}
	}
}
最近的文章

Java中的二叉树——菜鸟学数据结构(四)

今天楠哥和大家一起来讨论一下Java当中二叉树的实现。 树是一种高级数据结构,但是却十分常用,稍微复杂的问题就会涉及到树的应用。本文先就树(Tree)的最简单形式——二叉树进行一些简单的分析。顾名思义…

Technical, Career继续阅读
更早的文章

用Lisp解决简单的模式匹配(Pattern Match)问题

Lisp是人工智能中比较常用的语言之一,本文以一个经典的模式匹配(Pattern Match)问题为例,简要分析一下Lisp的语言结构。(楠哥计算机学习网www.liubonan.info) Lisp…

Technical, Career继续阅读
comments powered by Disqus