精华内容
下载资源
问答
  • import java.util.Scanner;...// 先进先出队列public class MyQueue implements Iterable {private Node first;private Node last;private int N;private class Node{Item item;Node next;}public ...

    import java.util.Scanner;

    import java.util.Iterator;

    // 先进先出队列

    public class MyQueue implements Iterable {

    private Node first;

    private Node last;

    private int N;

    private class Node{

    Item item;

    Node next;

    }

    public boolean isEmpty(){

    return first==null;

    }

    public int size(){

    return N;

    }

    // 向表尾添加元素

    public void enqueue(Item item){

    Node oldlast=last;

    last=new Node();

    last.item=item;

    last.next=null;

    if(isEmpty()) first=last;

    else oldlast.next=last;

    N++;

    }

    // 从表头删除元素

    public Item dequeue(){

    Item item=first.item;

    first=first.next;

    if(isEmpty()) last=null;

    N--;

    return item;

    }

    public Iterator iterator(){

    return new ListIterator();

    }

    private class ListIterator implements Iterator{

    Node current=first;

    @Override

    public boolean hasNext() {

    return current!=null;

    }

    @Override

    public Item next() {

    Item item=current.item;

    current=current.next;

    return item;

    }

    @Override

    public void remove() {}

    }

    public static void main(String[] args) {

    MyQueue q=new MyQueue();

    Scanner cin=new Scanner(System.in);

    while(cin.hasNext()){

    String item=cin.next();

    if(item.equals("$")) break;

    if(!item.equals("-")){

    q.enqueue(item);

    System.out.print("enqueue "+item);

    }

    else if(!q.isEmpty()){

    System.out.print("dequeue "+q.dequeue());

    }

    System.out.println(" | "+q.size()+" left in queue");

    }

    // Test iterator

    for(String s : q){

    System.out.print(s+" ");

    }

    System.out.println();

    Iterator it=q.iterator();

    while(it.hasNext()){

    System.out.print(it.next()+" ");

    }

    }

    }

    // Test example

    to be or not to - be - - that - - - is $

    enqueue to | 1 left in queue

    enqueue be | 2 left in queue

    enqueue or | 3 left in queue

    enqueue not | 4 left in queue

    enqueue to | 5 left in queue

    dequeue to | 4 left in queue

    enqueue be | 5 left in queue

    dequeue be | 4 left in queue

    dequeue or | 3 left in queue

    enqueue that | 4 left in queue

    dequeue not | 3 left in queue

    dequeue to | 2 left in queue

    dequeue be | 1 left in queue

    enqueue is | 2 left in queue

    that is

    that is

    展开全文
  • 基于链表结构实现先进先出 队列 上文中讲到了如何基于链表结构实现一个栈的数据结构,参考:下压堆栈(链表实现),本篇介绍如何如何实现队列结构。 队列应用: 生活中各种排队场景:食堂排队,银行排队。。。排队...

    基于链表结构实现先进先出 队列

    上文中讲到了如何基于链表结构实现一个栈的数据结构,参考:下压堆栈(链表实现),本篇介绍如何如何实现队列结构。

    队列应用:

    • 生活中各种排队场景:食堂排队,银行排队。。。排队意味着公平。VIP除外
    • 常言道:先来后到,先到先得。都是一种队列思想

    实现思路:

    • 定义两个实例变量,first和last,分别指向链表的表头和表尾,同时代表队列的队头和队尾。
    • 队列规定,队尾只许插入元素,队头只许删除元素,也就是说,新来的结点元素放在表尾(入队),而要从队列中取出元素(出队),只许在表头取。
      在这里插入图片描述

    直接上代码:

    import java.util.Iterator;
    import java.util.Scanner;
    
    /**
     * @author zhangjinglong
     * @date 2019-06-11-20:21
     * 先进先出队列  链表实现
     */
    
    public class Queue<Item> implements Iterable<Item> {
        private Node first;//指向最早添加的结点的链接 表头
        private Node last;//指向最近添加的结点的链接 表尾
        private int N;//队列中的元素数量
        private class Node{
            //定义了链表结点的嵌套类
            Item item;//保存数据的值
            Node next;//指向链表的下个结点
        }
    
        public boolean isEmpty(){
            return first==null; //或者用  N==0
    
        }
    
        public int size(){return N;}
    
        public void enqueue(Item item){
           //向表尾添加元素
           Node oldlast=last;//定义变量暂时保存原来的表尾
           last=new Node();//创建一个新结点,引用赋给last
           last.item=item;
           last.next=null;
           if(isEmpty()) first=last;//如果队列中没有元素,则first和last都指向同一个结点
            else oldlast.next=last;//将队尾的next值指向新的结点
            N++;//队列元素+1
        }
    
        public Item dequeue(){
            //从表头删除元素
            Item item=first.item;//创建变量保存表头元素
            first=first.next;//移除表头结点
            if(isEmpty()) last=null;//如果队列为空,则last也赋值为null
            N--;
            return item;
    
    
        }
    
        public Iterator<Item> iterator(){//实现Iterable的接口方法
            return new ListIterator();
    
        }
        private class ListIterator implements Iterator<Item>{//定义返回的迭代器
            private Node current=first;//复制一份头结点引用,初始化current
            public boolean hasNext(){return current.next!=null;}
            public void remove(){}
            public Item next(){
                Item item=current.item;//保留当前指向结点的值,用以返回
                current=current.next;//指向下一结点
                return item;
            }
    
        }
    
        //测试用例
        public static void main(String[] args) {
            //创建一个队列并操作字符串入列或出列
            Queue<String> q=new Queue<>();
            Scanner scanner= new Scanner(System.in);
    
            while(true){
                if(scanner.hasNext()){
                    String item=scanner.next();
                    if(item.equals("!")){// !表示终止输入
                        break;
                    }else if( item.equals("-")){
                        if(q.isEmpty()){
                            System.out.println("the queue is empty!");
                        }else{
                            System.out.println(q.dequeue()+ " ");
                        }
                    }else{
                        q.enqueue(item);
                    }
    
                }
            }
    
            System.out.println("("+q.size()+ " left on queue)");
        }
    
    }
    
    
    展开全文
  • java通过链表实现队列,先进先出

    千次阅读 2017-05-24 11:40:56
    // 出队,先进先出 public String removeFirst () { if (size == 0 ) { System. out .println( "空队列,无法出队" ); return null ; } Node temp = first; first = first.getNextNode(); size--; ...

    节点类

    package queue.demo;
    
    public class Node {
    
        private Object data;
        private Node nextNode;
        private Node prevNode;
    
        public Node(Object data) {
            super();
            this.data = data;
        }
    
        public Node(Object data, Node prevNode, Node nextNode) {
            super();
            this.data = data;
            this.nextNode = nextNode;
            this.prevNode = prevNode;
        }
    
        public Node getNextNode() {
            return nextNode;
        }
    
        public void setNextNode(Node nextNode) {
            this.nextNode = nextNode;
        }
    
        public Object getData() {
            return data;
        }
    
        public void setData(Object data) {
            this.data = data;
        }
    
        public Node getPrevNode() {
            return prevNode;
        }
    
        public void setPrevNode(Node prevNode) {
            this.prevNode = prevNode;
        }
    
    }
    

    队列类

    package queue.demo;
    
    public class Queue {
    
        int length = 5;
        int size = 0;
    
        Node first;
        Node last;
    
        // 入队
        public void add(String value) {
            if (size == length) {
                System.out.println("队列以满,无法添加");
                return;
            }
            Node newNode = new Node(value, last, null);
            Node temp = last;
            last = newNode;
            if (temp == null) {
                first = newNode;
            } else {
                temp.setNextNode(newNode);
            }
            size++;
        }
    
        // 出队,先进先出
        public String removeFirst() {
            if (size == 0) {
                System.out.println("空队列,无法出队");
                return null;
            }
            Node temp = first;
            first = first.getNextNode();
            size--;
            return (String) temp.getData();
    
        }
    
    }
    

    执行测试类

    package queue.demo;
    
    public class Main {
    
        public static void main(String[] args) {
            Queue q = new Queue();
            q.add("a");
            System.out.println("进队a");
            q.add("b");
            System.out.println("进队b");
            q.add("c");
            System.out.println("进队c");
            q.add("d");
            System.out.println("进队d");
            q.add("e");
            System.out.println("进队e");
            q.add("f");
            System.out.println("进队f");
            System.out.println("出队: " + q.removeFirst());
            System.out.println("出队: " + q.removeFirst());
            System.out.println("出队: " + q.removeFirst());
            System.out.println("出队: " + q.removeFirst());
            System.out.println("出队: " + q.removeFirst());
            System.out.println("出队: " + q.removeFirst());
    
        }
    
    }
    

    执行结果

    进队a
    进队b
    进队c
    进队d
    进队e
    队列以满,无法添加
    进队f
    出队: a
    出队: b
    出队: c
    出队: d
    出队: e
    空队列,无法出队
    出队: null

    展开全文
  • 链表是一种递归的数据结构,它或者为空(null),或者是指向一个节点(node)的引用,该节点含有一个泛型的元素和一个指向另一条链表的引用; 2.嵌套类来定义抽象数据类型: private class Node { Item item...

    话不多说,直接进入正题吧,代码很详细:

    /*
     1.链表是一种递归的数据结构,它或者为空(null),或者是指向一个节点(node)的引用,该节点含有一个泛型的元素和一个指向另一条链表的引用;
     2.嵌套类来定义抽象数据类型:
       private class Node
       {
         Item item;
         Node next;
       }
      3.Node的初始化为null;
      4.
     */
    
    import java.util.Iterator;
    public class QueueNode<Item> implements Iterable<Item>//声明可迭代的接口类型
    {
    	private Node first;//队首
    	private Node last; //队尾
    	private int N;     //元素数量
    	private class Node//定义节点
    	{//定义节点的嵌套类
    		Item item;
    		Node next;
    	}
    	public boolean isEmpty() {return first==null;}//或:N==0  判断队列是否为空
    	public int size() {return N;}//队列长度
    	public void enqueue(Item item)//向队尾添加元素
    	{
    		Node oldlast=last;//好像叫起别名
    		last=new Node();//这步容易漏掉
    		last.item=item;
    		last.next=null;
    		if(isEmpty()) first=last;
    		else oldlast.next=last;
    		N++;
    	}
    	public Item dequeue()//删除队首的元素
    	{
    		Item item=first.item;
    		first=first.next;//first无法再访问原来的节点了,曾经的节点对象变成了一个孤儿,Java内存管理系统最终将回收它所占的内存
    		if(isEmpty()) last=null;
    		N--;
    		return item;
    	}
    	
    	public Iterator<Item> iterator() {return new ListIterator();}//这段代码保证了类必然会实现方法hasNext(),next()和remove()供用例foreach()使用
    	private class ListIterator implements Iterator<Item>
    	{
    		private Node current=first;
    		public boolean hasNext() {return current!=null;}
    		public void remove() {};//希望避免在迭代中穿插能够修改数据结构的操作;如果用例调用了remove()则抛出UnsupportedOperationException
    		public Item next()
    		{
    			Item item=current.item;
    			current=current.next;
    			return item;
    		}
    	}
    }
    
    
    
    
    
    	 //可以通过迭代语句对Node进行迭代,代码如下:
    	   Stack<String> collection=new Stack<String>();
    	   Iterator<String> i=collection.iterator();
    	   while(i.hasNext())
    	   {
    	     String s=i.next();
    	     StdOut.println(s);
    	  }
    	 // 或者:
    	  Stack<String> collection=new Stack<String>();
    	  for(String s:collection)
    	    StdOut.println(s); 
    //如果要进行链尾的删除,在缺少其他信息的情况下,唯一的解决办法就是遍历整个链表,找到倒数第二个结点,但是z这个方案所需的时间和链表的长度成正比;
    //最好的解决办法是使用双链表。
    //链表的遍历:
         for(Node x=first;x!=null;x=x.next)
         {
            //执行操作
         }
    
    

    参考:《算法第四版》 Robert Sedgewick、Kevin Wayne (谢路云译) P96

    展开全文
  • import java.util.Iterator; import java.util.NoSuchElementException; public class Queue&lt;Item&gt; implements Iterable&lt;Item&gt; { private Node&lt;Item&gt; first; // ...
  • java队列链表实现

    千次阅读 2018-11-15 10:30:50
    * 队列先进先出的线性表 * 只能在表的一端进行插入,另段进行删除 * 允许插入的一端叫队尾,允许删除的一端叫队头() * * * ps:还存在种 双端队列 即队头和队尾都可以进行插入和删除的操作,队头和...
  • Java用数组和链表实现队列

    热门讨论 2021-05-07 09:35:00
    下面我数组和链表实现队列的两种方式做一个总结。 队列介绍 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制...
  • Java用链表实现队列

    2019-07-25 11:42:20
    队列(queue):是种特殊的线性表,特殊之处在于它遵从先进先出原则,它只允许在表的前端进行删除操作,而在表的后端进行插入操作,队列和栈一样是种操作受限制的表,进行插入操作的端称之为队尾,进行删除操作...
  • 栈是种基于后进先出(LIFO)策略的集合类型。当邮件在桌上放成一叠时,使用的就是栈。新邮件会放在最上面,当你要看邮件时,会封从上到下阅读。栈的顶部称为栈顶,所有操作都在栈顶完成。前面提到的新邮件,...
  • java_阻塞队列(FIFO先进先出)ArrayBlockingQueue:由数组结构组成的有界阻塞队列;LinkedBlockingQueue:由链表结构组成的有界阻塞队列(但大小默认值为:Integer.MAX_VALUE);PriorityBlockingQueue:支持优先级排序...
  • 1、请使用LinkedList来模拟一个队列(先进先出的特性): 1.1 拥有放入对象的方法void put(Object o) 1.2 取出对象的方法Object get() 1.3 判断队列当中是否为空的方法boolean isEmpty();并且,编写测试代码,验证...
  • 1.前一篇介绍了链表是什么,怎么实现,今天肝一个小时,顺便把栈和队列的这种基础线性表介绍一下; 2.什么是栈? 栈是一种先进的线性结构(FILO),“fist In last out”我是这么理解这个单词缩写,就像你往一个...
  • 使用java自己实现一个队列

    千次阅读 2020-03-15 11:42:25
    大家好,今天和大家分享一个自定义队列的... 那么我们如何设计一个先进先出的数据结构呢,首先能够确定的是,它属于一个线性结构,那么线性结构的实现,其实我们可用的选择就比较多,比如数组, 比如链表。 在这两...
  • 队列--种具有先进先出特点的数据结构,在我们生活中非常常见。队列可采用数组、链表存储。
  • 队列定义先进先出(FIFO)——先进队列的元素先出队列。来源于我们生活中的队列(先排队的先办完事)。基本操作initQueue() ——初始化队列enqueue() ——进队列dequeue() ——出队列isEmpty() ——判断队列是否为空...
  • 队列先进先出,从头进,从尾出。 栈:先进后出,从头进,从头出。 所以现在要做的就是用链表实现:从头进,从头出,从尾进,从尾出这4种方法,即可组合出队列和栈的数据结构。 假设以此插入1、2、3、4、5。 1、...
  • 队列的概念:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端...
  • 1、结合之前实现链表这个数据结构,如果只对链表的头部进行增加和删除,时间复杂度是O(1)的,只对链表的头部进行查询的话...所以对于链表来说,可以将链表的头部当作栈顶,用链表做为栈的底层实现实现一个栈。 ...
  • * 队列是一种先进先出的数据结构 * 队列支持的操作: * 判断队列是否为空 * 判断队列是否已经满了 * 查看队列已经有多少元素 * 将一个元素入队 * 将一个元素出队 * 查看队头的元素,但不出队 * 队列在底层...
  • Java链表实现队列

    2021-01-27 11:32:17
    问题:用链表实现一个先进先出队列 分析: 1、链表实现,必须有一个节点能够装数据和下一个节点的指针(引用) 2、队列必须要有队首、队尾指针和记录当前队列大小的整型数 3、入队:往队尾加,队尾的下一个...
  • 问题:如何redis和Java设计一个高效的先进先出队列?分析: redis的list底层是多个ziplist结构组成的“双向”链表。中间部分还压缩了一下。 最外层是由两个哈希表构成的dict。 哈希表的get(key)时间复杂度为O(1...
  • 文章目录1、什么是队列2、Queue数据结构实现——基于动态数组2.1、基本函数实现2.2 进出队列函数2.3 查询操作3、Queue数据结构实现——基于链表函数3.1、基本函数实现3.2 进出队列函数3.3 查询操作4、LoopQueue循环...
  • 实现队列实现栈的会多一点复杂,需要两标记,first表示队头,last表示队尾。 链表结构 private class Node{ Item item; Node next; } 迭代器 与实现栈的迭代器一模一样 private class Iterator implements ...
  • 队列先进先出,只能访问头部数据 队列也可以数组来实现,不过这里有问题,当数组下标满了后就不能再添加了,但是数组前面由于已经删除队列头的数据了,导致空。所以队列我们可以循环数组来实现,见下面的...
  • 实现队列java代码实现

    千次阅读 2020-04-30 20:07:48
    队列的功能就是FIFO(先进先出)原则。不管是队列还是栈,他们的功能都是存储数据,底层实现可以数组也可以是链表,但是他们各自有他们的特点。既然队列也是存储数据的种数据结构,那么他就有增删改查等功能。队列...
  • 队列是一种先进先出(FIFO)的集合模型,而栈则是后进先出(LIFO)的集合模型,我们经常使用它们用来保存元素的相对顺序。Java中在java.util.LinkedList类中实现了关于队列和栈的实现,但是这是一个宽接口的例子,这里...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,605
精华内容 11,442
关键字:

java用一个链表实现先进先出队列

java 订阅