java集合LinkedList模拟队列 - JAVA

前言

下午写LeetCode期间需要使用广度优先搜索算法，配合队列这种数据结构，队列数据结构的特性可以参考我之前的文章：队列的学习
在java里使用队列可以用LinkedList集合进行模拟

方法

使用LinkedList集合，并使用其中的addLast、removeFirst、isEmpty等API集体模拟队列操作

入队列

void addLast(E e); // 将元素插入此列表的结尾

出队列

E removeFirst(); // 移除并返回列表的第一个元素

判空

boolean isEmpty(); // 判断队列是否为空

示例代码

package coreJavaOne;

import java.util.LinkedList;
import java.util.NoSuchElementException;

public class SimulateQueue {
    private LinkedList
  
    queue = new LinkedList
   
    (); public boolean isEmpty() { return this.queue.isEmpty(); } public void enQueue(int data) { this.queue.addLast(data); } public int deQueue() throws NoSuchElementException { return this.queue.removeFirst(); } public static void main(String[] args) { SimulateQueue q = new SimulateQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); while (! q.isEmpty()) { int data = q.deQueue(); System.out.println(data); } } }

层次遍历二叉树

对应到LeetCode上的一道题目，很容易看出是广度优先搜索，需要队列的辅助

题目

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

AC代码

import java.util.ArrayList;
import java.util.LinkedList;


public class BinaryTreeLevelOrderTraversal {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int x) {
            this.val = x;
        }
    }

    public ArrayList
  
   > levelOrder(TreeNode root) {
        ArrayList
   
    > list = new ArrayList
    
     >(); LinkedList
     
       queue = new LinkedList
      
       (); TreeNode p; int data; if (root == null) { return list; } else { queue.addLast(root); } while (!queue.isEmpty()) { ArrayList
       
         sublist = new ArrayList
        
         (); LinkedList
         
           subQueue = new LinkedList
          
           (); while (!queue.isEmpty()) { p = queue.removeFirst(); sublist.add(p.val); if (p.left != null) { subQueue.addLast(p.left); } if (p.right != null) { subQueue.addLast(p.right); } } list.add(sublist); queue.addAll(subQueue); } return list; } }