队列的使用和实现

文章目录

• • @[TOC](文章目录)
• 一、什么是队列？
• 二、队列的使用
• • 1.java中的基本使用
  • 2.链表实现队列
  • 3、用数组实现队列，循环队列。
  • 判断队列是空是满，即rear和front的关系。
  • • 一、使用UsedSizde与数组长度比较。
    • 二、设置标志位
    • 三、检查下一个元素是不是front。
  • 3、两个队列实现栈
  • 4、用栈来实现队列

一、什么是队列？

队列：只允许在一端进行插入数据 *** 作，在另一端进行删除数据 *** 作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)
入队列：进行插入 *** 作的一端称为队尾（Tail/Rear）
出队列：进行删除 *** 作的一端称为队头（Head/Front）

二、队列的使用 1.java中的基本使用

代码如下（示例）：

public static void main(String[] args) {
        System.out.println("普通队列的使用:");
        Queue<Integer> queue=new LinkedList<>();
        //添加元素
        queue.add(2);
        queue.add(4);
        queue.add(5);
        queue.offer(4);
        queue.offer(9);
        queue.offer(23);
        System.out.print("队列的大小:");
        System.out.println(queue.size());
        System.out.print("获取队头元素:");
        System.out.print(queue.peek()+" ");
        System.out.println(queue.element());
        System.out.print("d出队列:");
        System.out.print(queue.poll()+" ");
        System.out.println(queue.remove());
        System.out.print("队列的大小:");
        System.out.println(queue.size());
        System.out.println("======================");
        System.out.print("双端队列的使用:");
        Deque<Integer> deque=new LinkedList<>();
        //添加元素，队头入队
        deque.addFirst(4);
        deque.addFirst(5);
        deque.addFirst(87);
        deque.offerFirst(23);
        //队尾入队
        deque.addLast(56);
        deque.add(7);//add也可以使用
        deque.offerLast(12);
        deque.offer(66);//也可以
        System.out.print("双端队列的大小"+" ");
        System.out.println(deque.size());

        System.out.print("获取队头元素:");
        System.out.print(deque.getFirst()+" ");
        System.out.print(deque.peekFirst()+" ");
        System.out.println(deque.peek());
        System.out.print("获取队尾元素:");
        System.out.print(deque.getLast()+" ");
        System.out.println(deque.peekLast());
        System.out.print("出队列(队头):");
        System.out.print(deque.remove()+ " ");
        System.out.println(deque.poll()+" ");
        System.out.print(deque.removeFirst()+" ");
        System.out.println(deque.pollFirst());
        System.out.print("出队列(队尾):");
        System.out.print(deque.removeLast()+" ");
        System.out.println(deque.pollLast());
        System.out.print("双端队列的大小"+" ");
        System.out.println(deque.size());
    }

2.链表实现队列

代码如下（示例）：

//用链表实现队列
class Node{
    int val;
    Node next;
    public Node(int val,Node next){
        this.val=val;
        this.next=next;
    }
    public Node(int val){
        this(val,null);
    }

}
 class MyQueue{
    private Node head=null;
    private Node tail=null;
    private int size=0;
    //入队：类似于尾插法。
    public void offer(int v){
        Node node=new Node(v);
        if(tail==null){
            this.head=node;
        }else {
            tail.next=node;
        }
        this.tail=node;
        size++;
    }
    //出队：类似删除头节点
     public int poll(){
        if(size==0){
            throw new RuntimeException("队列为空");
        }
        Node oldHead=head;
        head=head.next;
        if(head==null){
            tail=null;
        }
        size--;
        return oldHead.val;
     }
     //出队不删除队列元素。
     public int peek(){
        if (size==0){
            throw new RuntimeException("队列为空");
        }
        return head.val;
     }
     //判断是否为空
     public boolean isEmpty(){
        //size为0，返回为true,否则falase
        return size==0;
     }
     //队列长度
     public int size(){
        return size;
     }
}
public class Demo2 {
    public static void main(String[] args) {
        MyQueue myQueue=new MyQueue();
        //入队
        myQueue.offer(4);
        myQueue.offer(5);
        myQueue.offer(23);
        //长度
        System.out.println(myQueue.size());
        //出队不删除
        System.out.println(myQueue.peek());
        //出队
        System.out.println(myQueue.poll());
        System.out.println(myQueue.peek());
        //长度
        System.out.println(myQueue.size());
        //是否为空
        System.out.println(myQueue.isEmpty());
    }
}

注：实现双端队列只需使用双向链表即可

3、用数组实现队列，循环队列。

判断队列是空是满，即rear和front的关系。 一、使用UsedSizde与数组长度比较。

• usedsize记录添加元素和删除元素是的长度，如usedsize和数组长度相同就是满的，否则为空。
  

二、设置标志位

三、检查下一个元素是不是front。

• 检查下一个元素是不是front，若是则满，否则未满。
  

class MyCircularQueue{
    public int[] elem;
    public int front;//头下标
    public int rear;//尾下标
    public MyCircularQueue(int k){
        this.elem=new int[k+1];
    }
    //入队
    public boolean enQueue(int value){
        if(isFull()){
            return false;
        } else {
            this.elem[rear] = value;
            rear=(rear+1)%elem.length;
        }
        return true;
    }
    //出队
    public boolean deQueue(){
        if(isEmpty()){
            return false;
        }
        front=(front+1)%elem.length;
        return true;
    }
    //得到队头元素
    public int Front(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }else {
            return elem[front];
        }
    }
    public int Rear(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int index=-1;//初始化index
        if (rear==0){
            index=elem.length-1;//单独判断若rear为0时队尾下标。
        }else {
            index=rear-1;
        }
        return elem[index];
    }
    //使用的是第三种方法判断满没满
    public boolean isFull(){
        if((this.rear+1)%elem.length==front){
            return true;
        }
        return false;
    }
    public boolean isEmpty(){
        return front==rear;
    }
}

3、两个队列实现栈

//用两个队列实现栈
class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }

    public void push(int x) {
        if(!queue1.isEmpty()){
            queue1.offer(x);
        }else if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }

    public int pop() {
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            int size=queue1.size();
            for(int i=0;i<size-1;i++){
                int val=queue1.poll();
                queue2.offer(val);
            }
            return queue1.poll();
        }
        if(!queue2.isEmpty()){
            int size=queue2.size();
            for(int i=0;i<size-1;i++){
                int val=queue2.poll();
                queue1.offer(val);
            }
            return queue2.poll();
        }
        return -1;

    }

    public int top() {
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            int val=-1;
            int size=queue1.size();
            for(int i=0;i<size;i++){
                val=queue1.poll();
                queue2.offer(val);
            }
            return val;
        }
        if(!queue2.isEmpty()){
            int val=-1;
            int size=queue2.size();
            for(int i=0;i<size;i++){
                val=queue2.poll();
                queue1.offer(val);
            }
            return val;
        }
        return -1;
    }
    public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();
    }
}
public class Demo4 {
    public static void main(String[] args) {
        MyStack myStack=new MyStack();
        myStack.push(5);
        myStack.push(7);
        System.out.println(myStack.pop());
        System.out.println(myStack.top());
        System.out.println(myStack.empty());
    }

}

4、用栈来实现队列

class MyQueue1 {
    public Stack<Integer> stack1;
    public Stack<Integer> stack2;

    public MyQueue1() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

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

    public int pop() {
        if(empty()){
            return -1;
        }
        if(stack2.isEmpty()){
            int size=stack1.size();
            while(!stack1.isEmpty()){
                for(int i=0;i<size;i++){
                    int val=stack1.pop();
                    stack2.push(val);
                }
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if(empty()){
            return -1;
        }
        if(stack2.isEmpty()){
            int size=stack1.size();
            while(!stack1.isEmpty()){
                for(int i=0;i<size;i++){
                    int val=stack1.pop();
                    stack2.push(val);
                }
            }
        }
        return stack2.peek();

    }

    public boolean empty() {
        return stack1.isEmpty()&&stack2.isEmpty();
    }
}
public class Demo5 {
    public static void main(String[] args) {
        MyQueue1 myQueue1=new MyQueue1();
        myQueue1.empty();
        myQueue1.push(6);
        myQueue1.push(8);
        myQueue1.push(3);
        myQueue1.push(23);
        System.out.println(myQueue1.peek());
        System.out.println(myQueue1.pop());
        System.out.println(myQueue1.empty());
    }
}