数据结构——队列及其Java实现
执键写春秋 10 3

队列及其Java实现

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

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 ```

预览图
评论区

索引目录