队列及其Java实现

队列（Queue）是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，与栈一样，队列是一种操作受限制的线性表（先进先出，FIFO-first in first out）。队列有两个末端，其中，执行插入操作的端叫作队尾，执行删除操作的端叫作队头。若队列中没有元素，称为空队列，在队列中插入一个队列元素叫作入队，从队列中删除一个队列元素叫作出队。 具体的数据结构如图： 数据结构——队列及其Java实现

1.实现队列核心方法

boolean add(E e)//向队列的尾部添加一个元素，先入队列的元素在最前面。如果队列已满，则抛出一个IIIegaISlabEepeplian异常。
boolean offer(E e)//添加一个元素并返回true 如果队列已满，则返回false。
E remove()//删除队列的头。如果队列为空，则抛出一个NoSuchElementException异常。
E poll()//移除并返问队列头部的元素，如果队列为空，则返回null。
Eelement()//返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常。

E peek()//返回队列头部的元素，如果队列为空，则返回null。

2.队列的具体实现过程

package person.xsc.datamanage;
public class QueueDemo1<E> {
      private Object[] data=null;//队列数据存储
      private int maxSize;//队列的容量
      private int front;//队列头，允许删除
      private int rear;//队列尾，允许插入
      public QueueDemo1 (int initialSize) {
          if(initialSize>=0) {
              this.maxSize = initialSize;
              data = new Object[initialSize];
              front=rear=0;
          }else {
              throw new RuntimeException("初始化大小不能小于0："+initialSize);
          }
      }    
      /**
       * 入队
       * @param value
       */
      public void in(Object value) throws Exception {
          if(rear == maxSize){
              throw  new RuntimeException("队列已满，无法插入新元素");
          }
          data[rear ++] = value;
      }
      /**
       * 出队
       */
      public E poll(){
          if(isEmpty()){
              throw  new RuntimeException("空队列异常");
          }else {
              E value = (E) data[front];
              data[front++] = null;
              return value;
          }
      }
      /**
       * 是否为空队列
       * @return
       */
      public boolean isEmpty(){
          return  front == rear;
      }
      /**
       *队列数据查询
       */
      public E peek(){
          if(isEmpty()){
              throw  new RuntimeException("空队列异常");
          }else {
              return  (E) data[front];
          }
      }
  }

3.链表用作FIFO队列

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

package person.xsc.datamanage;

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

public class QueueDemo2 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    //前面说了add()和remove()方法在失败的时候会抛出异常，所以这里不推荐使用
    Queue<String> queue = new LinkedList<String>();
    //添加元素
    queue.offer("H");
    queue.offer("e");
    queue.offer("l");
    queue.offer("l");
    queue.offer("o");
    System.out.println("----------------“遍历队列，元素不被移除”------------------------");
    for(String q : queue){
        System.out.print(q+"  ");
    }
    System.out.println("");
    System.out.println("----------------“遍历队列，元素逐个被移除”------------------------");
    while (queue.peek() != null) {
        System.out.print(queue.poll()+"  ");
    }
    System.out.println("");
    System.out.println("----------------“判断是否为空队列”------------------------");
    if(queue.isEmpty()) {
        System.out.println("空队列！");
    }else {
        System.out.println("队列不空！");
    }
    System.out.println("----------------“向队列插入新数据，并遍历队列”------------------------");
    queue.offer("W");
    queue.offer("o");
    queue.offer("r");
    queue.offer("l");
    queue.offer("d");
    for(String q : queue){
        System.out.print(q+"  ");
    }
    System.out.println("");
    System.out.println("----------------“返回第一个元素 ，元素不移除”------------------------");
    System.out.println("队头="+queue.peek());
}

}

输出： ----------------“遍历队列，元素不被移除”------------------------ H e l l o
----------------“遍历队列，元素逐个被移除”------------------------ H e l l o
----------------“判断是否为空队列”------------------------ 空队列！ ----------------“向队列插入新数据，并遍历队列”------------------------ W o r l d
----------------“返回第一个元素，元素不移除”------------------------ 队头=W

## 4.关于队列的面试问题
- **求队列最大值（有入队、出队操作）**

package person.xsc.datamanage; import java.util.LinkedList; import java.util.Queue; class MaxQueue { Queue mainQueue=new LinkedList();//主 LinkedList maxQueue=new LinkedList();//辅助 public void push(int value) { mainQueue.offer(value); while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) { //peekLast()尾部元素 maxQueue.pollLast();//删除尾部元素 } maxQueue.offerLast(value);//将指定元素加入辅助 } public int max_value() { return maxQueue.isEmpty()?-1:maxQueue.peekFirst(); } public void pop() { if (mainQueue.isEmpty()) { throw new RuntimeException("空队列异常"); } if (mainQueue.poll()== maxQueue.peekFirst()) { maxQueue.pollFirst(); } } } public class QueueDemo4 { public static void main(String[] args) { // TODO Auto-generated method stub MaxQueue qu = new MaxQueue(); qu.push(6); qu.push(1); qu.push(2); qu.pop(); System.out.println(qu.max_value()); } } 输出：2

- **栈和队列的共同特点**
只允许在端点处插入和删除元素。
- **用两个栈实现一个队列**

package person.xsc.datamanage; import java.util.Stack; public class QueueDemo5 { private Stack stack1 = new Stack<>();//执行入队操作的栈 private Stack stack2 = new Stack<>();//执行出队操作的栈 //方法：给队列增加一个入队的操作 public void push(int data) { stack1.push(data);//向执行入队操作的栈中压入一个数据 } //方法：给队列正价一个出队的操作 public int pop() throws Exception { ////stack1中的数据放到stack2之前，先要保证stack2里面是空的 if (stack2.empty()) { while (!stack1.empty()) { stack2.push(stack1.pop());//把stack1栈顶数据出栈，放到stack2中，直至stack1为空 } } if (stack2.empty()) { //stack2为空时，有两种可能：1、一开始，两个栈的数据都是空的；2、stack2中的数据出完了 throw new Exception("队列为空"); } return stack2.pop(); } public static void main(String[] args) throws Exception { // TODO Auto-generated method stub QueueDemo5 queue = new QueueDemo5(); System.out.println("-----------“元素1入队”--------------"); queue.push(1); System.out.println("-----------“元素11入队”--------------"); queue.push(11); System.out.println("-----------“取出队头并删除”--------------"); System.out.println(queue.pop()); System.out.println("-----------“元素4入队”--------------"); queue.push(4); System.out.println("-----------“取出队头并删除”--------------"); System.out.println(queue.pop()); System.out.println("-----------“元素2入队”--------------"); queue.push(2); System.out.println("-----------“取出队头并删除”--------------"); System.out.println(queue.pop()); }

} 输出： -----------“元素1入队”-------------- -----------“元素11入队”-------------- -----------“取出队头并删除”-------------- 1 -----------“元素4入队”-------------- -----------“取出队头并删除”-------------- 11 -----------“元素2入队”-------------- -----------“取出队头并删除”-------------- 4 ```

队列及其Java实现

1.实现队列核心方法

2.队列的具体实现过程

3.链表用作FIFO队列

热门文章