Java DataStructure-Queue,Stack

发表于 更新于 分类于 阅读次数： Valine： 

        

        
          


Queue
Queue 是一个 FIFO（先进先出）的数据结构，并发中使用较多，可以安全地将对象从一个任务传给另一个任务。其形式类似于日常生活中的排队。




  Java 集合中的 Queue 继承自 Collection 接口 ，Deque, LinkedList, PriorityQueue,  BlockingQueue 等类都实现了它。
Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问。
除了继承 Collection 接口的一些方法，Queue 还添加了额外的 添加、删除、查询操作。




Queue Method Introduction
queue.png




优先考虑右侧方法




add(E), offer(E) 在尾部添加:


区别：一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。




remove(), poll() 删除并返回头部：


区别：remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。




peek， element 获取但不删除


区别：element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。




代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package DataStructure;

import java.util.LinkedList;
import java.util.Queue;

public class QueueType {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<String>();
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        for(String x:queue)
            System.out.print(x + " ");
        System.out.print("\n*********************\n");
        System.out.println("pull=" + queue.poll() +"    remove=" +queue.remove()); // 返回头俩个元素，并在队列中删除
        for(String x:queue)
            System.out.print(x + " ");
        System.out.print("\n*********************\n");
        System.out.println("element=" + queue.element());   // 返回当前队列中的第一个元素
        for(String x:queue)
            System.out.print(x + " ");
        System.out.println("\npeek=" + queue.peek());         // 返回当前队列中的第一个元素
        for(String x:queue)
            System.out.print(x + " ");
    }
}



演示结果： 


1
2
3
4
5
6
7
8
9
a b c d e 
*********************
pull=a    remove=b
c d e 
*********************
element=c
c d e 
peek=c
c d e



Deque
双端队列（deque，全名double-ended queue）可以让你在任何一端添加或者移除元素，因此它是一种具有队列和栈性质的数据结构。
Deque.png


Deque方法详解


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package DataStructure;

import java.util.Deque;
import java.util.LinkedList;

public class DequeType {
    public static void main(String[] args) {
        Deque<String> dq = new LinkedList<String>();
        dq.offerFirst("a");
        dq.offerFirst("b");
        dq.offerLast("c");
        dq.offerLast("d");
        for(String x:dq)
            System.out.print(x + " ");
        System.out.print("\n*********************\n");
        System.out.println(dq.removeFirst());       // 读取头部的一个元素，并将其移除
        for(String x:dq)
            System.out.print(x + " ");
        System.out.print("\n*********************\n");
        System.out.println(dq.pollLast());            // 读取尾部的一个元素，并将其移除
        for(String x:dq)
            System.out.print(x + " ");
        System.out.print("\n*********************\n");
        System.out.print(dq.peekLast());            // 获取尾部的一个元素

        System.out.print("\n*********************\n");
        dq.addLast("a");
        dq.addLast("c");
        dq.addLast("a");
        System.out.println("当前队列:" + dq);
        dq.removeFirstOccurrence("a");          // 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表）
        System.out.println("第一次删除后的队列:" + dq);
        dq.removeLastOccurrence("a");           // 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表）
        System.out.println("第二次删除后的队列:" + dq);
    }
}



演示结果： 


1
2
3
4
5
6
7
8
9
10
11
12
13
b a c d 
*********************
b
a c d 
*********************
d
a c 
*********************
c
*********************
当前队列:[a, c, a, c, a]
第一次删除后的队列:[c, a, c, a]
第二次删除后的队列:[c, a, c]



Stack
栈是Vector的一个子类，它实现了一个标准的（LIFO）后进先出的栈。


堆栈只定义了默认构造函数，用来创建一个空栈。 堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法:


StackMethod.png




还有些遗传至Vector， Object 与 Collection的方法




代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package DataStructure;

import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        StackDemo sd = new StackDemo();
        Stack<Integer> st = new Stack<Integer>();
        sd.showPush(st,45);
        sd.showPush(st, 65);
        sd.showPush(st, 85);
        System.out.println("peek the top Element:" + st.peek());  // 查看栈顶元素
        System.out.println("search Element position:" + st.search(65)); // 查找元素位置
        sd.showPop(st);
        sd.showPop(st);
        sd.showPop(st);
        System.out.println("Judge isEmpty:" + st.empty());
    }

    void showPush(Stack st, int num){
        st.push(num);       // 入栈
        System.out.println("push(" + num + ")");
        System.out.println("stack: " + st);
    }

    void showPop(Stack st) {
        System.out.print("pop -> ");
        Integer a = (Integer) st.pop();    // 出栈
        System.out.println(a);
        System.out.println("stack: " + st);
    }
}



演示结果： 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
push(45)
stack: [45]
push(65)
stack: [45, 65]
push(85)
stack: [45, 65, 85]
peek the top Element:85
search Element position:2
pop -> 85
stack: [45, 65]
pop -> 65
stack: [45]
pop -> 45
stack: []
Judge isEmpty:true





参考文档




    


    
    
    
	  
---------------- The End ----------------

    
        
      
	  
	  

	  

	   本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布

	    
	    本文地址：https://philxin.top/2019/09/26/Java-DataStructure-Queue/
转载请注明出处，谢谢！
	    
	  

	  


      
    
  

  
  
  
  


  



          

          
    
    

  

        

          
  
  

    

      
      
      
    

  


  
  


      

    


    

    
  

    
    0%