【恋上数据结构】队列 Queue

GItee持续更新

• • 六、队列(Queue)
  • • 1.接口设计
    • 2.练习-用栈来实现队列
    • 3.双端队列(Deque)
    • 4.循环队列(Circle Queue)

队列是一种特殊的线性表，只能在头尾两端进行操作。

先进先出

队列中的方法总结：

优先使用双向链表，因为动态数组在头操作复杂度较高。

package 栈和队列;


import java.util.linkedList;


public class Queue {
    private linkedList linkedList = new linkedList();

    
    public int size(){
       return linkedList.size();
    }

    
    public boolean isEmpty(){
        return linkedList.isEmpty();
    }

    
    public void offer(E element){
        linkedList.add(element);
    }

    
    public E poll(){
       return linkedList.poll();
    }

    
    public E peek(){
        return linkedList.get(0);
    }
}

public class QueueTest {
    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.offer(99);
        queue.offer(88);
        queue.offer(77);
        System.out.println(queue.peek());
        while (!queue.isEmpty()){
            System.out.println(queue.poll());
        }
    }
}

思路：

• 用两个栈来模拟队列、

• 入队时，push到 S1中

• 出队时

  如果S2为空，将S1中所有的元素弹出，push到S2中，S2弹出栈顶元素。

  如果S2不为空，S2弹出栈顶元素。

实现

class MyQueue {

   
    private Stack queueHead ;
    
    private Stack queueTail ;
    public MyQueue() {
        queueHead = new Stack<>();
        queueTail = new Stack<>();
    }

    public void push(int x) {
        queueTail.push(x);
    }

    public int pop() {
        if (queueHead.empty()) {
            while (!queueTail.empty()) {
                Integer e = queueTail.pop();
                queueHead.push(e);
            }
        }
        return queueHead.pop();
    }

    public int peek() {
        if (queueHead.empty()) {
            while (!queueTail.empty()) {
                Integer e = queueTail.pop();
                queueHead.push(e);
            }
        }
        return queueHead.peek();
    }

    public boolean empty() {
        return queueHead.isEmpty() && queueTail.isEmpty();
    }
}

接口设计

Queue与Deque比较

Stack与Deque比较

我们可以建立一个数组和两个指针来模拟循环队列。另外还设置了一个用来计数的变量，记录数组中元素的个数，使得我们能够更加容易的去判断队列当前的状态，已满或者为空。

class MyCircularQueue {
    		int[] queue;
    		int size;//对列的容量
    		int front;//头指针
    		int rear;//尾指针
    		int E_num;//当前队列中元素的个数
    	    public MyCircularQueue(int k) {//初始化
    	    	this.queue=new int[k];
    	    	this.size=k;
    	    	this.front=-1;
    	    	this.rear=0;
    	    	this.E_num=0;
    	    }
    	    public boolean enQueue(int value) {//入队
    	    	if(E_num>=size) return false;
    	    	front=(front+1)%size;
    	    	queue[front]=value;
    	    	E_num++;
    	    	return true;
    	    }
    	    public boolean deQueue() {//出队
    	    	if(E_num==0) return false;
    	    	rear=(rear+1)%size;
    	    	E_num--;
    	    	return true;
    	    }
    	    public int Front() {//获取队头元素（当前所有元素中最先进入的元素）
    	    	if(E_num==0) return -1;
    	    	return queue[rear];
    	    }
    	    
    	    public int Rear() {//获取队尾元素（当前所有元素中最后入队的元素）
    	    	if(E_num==0) return -1;
    	    	return queue[front];
    	    }
    	    public boolean isEmpty() {//判断队空
    	    	if(E_num==0) return true;
    	    	return false;
    	    }
    	    public boolean isFull() {//判断队是否已满
    	    	if(E_num==size) return true;
    	    	return false;
    	    }
}