欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构学习一队列整理

程序员文章站 2024-03-18 11:34:34
...

队列

1.定义

  • 一种先进先出的数据结构,从队尾入队,队头出队。

2.实现

class MyQueue {
    // 队列
    private List<Integer> data;         
    // 头指针
    private int p_start;  
    //队列的初始化          
    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0;
    }
    /** 入队成功了,返回true */
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    };    
    /**出队,成功返回true */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        p_start++;
        return true;
    }
    /** 获取队首元素 */
    public int Front() {
        return data.get(p_start);
    }
    /** C判断队列是否为空 */
    public boolean isEmpty() {
        return p_start >= data.size();
    }     
};

public class Main {
    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.enQueue(5);
        q.enQueue(3);
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
    }
}

3.队列实现的步骤

  • 构造一个存放数据的队列
    • 队列的数据结构:存放数据的队列集合、指示队首坐标的“指针”
  • 队列的初始化
  • 入队操作
  • 判断队列是否满了
  • 出队操作
  • 判断队列是否空了
  • 查看队首元素(第一个出队的元素)

4.特点

  • 按顺序处理元素

循环队列

1.定义

  • 将队首和队尾相连,通过两个指向队首和队尾的“指针”完成首尾相连,可以高效的利用队列的空间。

2.实现

class CircleQueue {
  private int[] data;
  private int head;
  private int tail;
  private int size;

  //初始化队列
  CilcleQueue(int k) {
      data = new int[k];
      head = -1;
      tail = -1;
      size = k;
  }
  //判断队列为空
  public boolean isEmpty() {
      return tail == -1;
  }
  //判断队列是否为满
  public boolena isFull() {
      return (tail + 1) % size == head;
  }
  //入队
  public boolean enQueue(int value) {
      if(isFull() == true) {
        return false;
      }
      if(isEmpty() == true) {
        head += 1;
      }
      tail = (tail+1) % size;
      data[tail] = value;
      return true;
  }
  //出队
  public boolean deQueue() {
    if (isEmpty() == true) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
  }
  //获取队头元素
  public int Front() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[head];
  }
  //获取队尾元素
  public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[tail];
  }

}

3.实现步骤

  • 构造循环队列的数据结构
    • 存放队列数据的数组、指向队首和队尾的“指针”、队列长度
  • 队列的初始化
  • 入队
  • 判断队满;判断队空,则将指向队首元素的“指针”+1
  • 出队
  • 判断队空,则将指向队首和队尾的“指针”重新赋值为初始值
  • 查看队首元素
  • 查看队尾元素
队列的判空与判满的条件
  • 判空:根据队尾"指针"是否为初始值-1
  • 判满:根据队尾"指针"+1对队列长度取余是否等于队首"指针"

使用内置队列库

实现

public static void main(String[] args) {
//定义一个链队列
LinkedList<Integer> q = new LinkedList();
//入队
q.add(1);
q.add(2);
q.offer(3);
System.out.println(q);
//出队
q.remove();
System.out.println(q);
if(aQueue.isEmpty())
  System.out.println("true");
System.out.println("false");
  }
}