[数据结构与算法]顺序队列，链式队列和利用栈实现队列

队列

1. 队列，又称为伫列（queue），计算机科学中的一种抽象资料型别，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

   队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

顺序队列

1. 用数组实现的队列叫作顺序队列

2. 代码实现

   class ArrayQueue{
   private Object[] objects;
   private int count = 0;
   
   //head表示队头下标，tail表示队尾下标
   private int head = 0;
   private int tail = 0;
   
   //初始化队列
   public ArrayQueue(int capacity){
       this.objects = new Object[capacity];
       this.count = capacity;
   }
   
   //判断队列是否为空
   public boolean isEmpty(){
       return head == tail;
   }
   
   //判断队列是否已满
   public boolean isFull(){
       return (tail + 1) % count == head;
   }
   
   //入队
   public void enqueue(Object object){
       //判断队列是否已满
       if (!isFull()){
           objects[tail] = object;
           tail++;
       }
   }
   
   //出队
   public Object dequeue(){
       Object res = null;
       //看到队列是否为空
       if (!isEmpty()){
           res = objects[head];
           head++;
       }
       return res;
   }
   }
   

链式队列

1. 用链表实现的队列叫作链式队列

2. 代码实现

   class LinkedQueue {
   private static class Node {
       private Object data;
       private Node next;
   
       public Node(Object data, Node next) {
           this.data = data;
           this.next = next;
       }
   
       public Object getData() {
           return data;
       }
   }
   
   //队列的队尾和队首
   private Node head = null;
   private Node tail = null;
   
   //判断队列是否为空
   public boolean isEmpty(){
       return head == null;
   }
   
   //入队
   public void enqueue(Object object){
       if (tail == null){
           Node newNode = new Node(object,null);
           head = newNode;
           tail = newNode;
       }else {
           tail.next = new Node(object,null);
           tail = tail.next;
       }
   }
   
   //出队
   public Object dequeue(){
       Object res = null;
       //判断队列是否为空
       if (!isEmpty()){
           res = head.data;
           head = head.next;
       }else {
           tail = null;
       }
       return res;
   }
   
   }
   

利用栈实现队列

1. 借助于栈来实现队列

2. 代码实现

   class BaseStackQueue{
   
   private Stack<Object> stack1;
   private Stack<Object> stack2;
   
   public BaseStackQueue(){
       this.stack1 = new Stack<>();
       this.stack2 = new Stack<>();
   }
   
   //判断队列是否为空
   public boolean isEmpty(){
       return stack1.isEmpty() && stack2.isEmpty();
   }
   
   //入队
   public void enqueue(Object object){
       stack1.push(object);
   }
   
   //出队
   public Object dequeue(){
       Object res = null;
       //判断队列是否为空
       if (!isEmpty()){
           while (!stack1.isEmpty()){
               stack2.push(stack1.pop());
           }
           res = stack2.pop();
       }
       return res;
   }
   }