(Java)数据结构之队列(Queue),含有三个OJ题(用队列实现栈,用栈实现队列,实现一个最小栈)

目录

1. 队列的概念

2. 队列的使用     

3. 队列的模拟实现

4. 循环队列

5. 双端队列 

6. OJ题 


1. 队列的概念

队列只允许在一端进行插入操作,在另一端进行删除操作的特殊线性表,队列具有先进先出(FIFO)的特性,进行插入操作的一端为队尾,进行删除操作的一端为队头

2. 队列的使用     

在Java中,Queue是一个接口,底层是通过链表来实现的

方法 功能说明
boolean offer(E e)  入队列
E poll() 出队列
E peek() 获取对头元素
int size() 获取队列中有效元素的个数
boolean isEmpty() 检测队列是否为空

注意:队列Queue是一个接口,在实例化对象时必须实例化LinkedList对象,因为LinkedList实现了Queue接口 

import java.util.LinkedList;
import java.util.Queue;

public class TestQueue {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5);
        System.out.println(q);
        System.out.println(q.size());
        q.poll();
        q.poll();
        System.out.println(q);
        System.out.println(q.isEmpty());
    }
}
//执行结果:[1, 2, 3, 4, 5]
//         5
//         [3, 4, 5]
//         false

3. 队列的模拟实现

public class Queue<E> {
    public static class ListNode<E>{
        E val;
        ListNode<E> next;
        ListNode<E> pre;
        ListNode(E val){
            this.val = val;
        }
    }
    ListNode<E> first;    //队头
    ListNode<E> last;     //队尾
    int size = 0;
    //入队列---插新节点
    public void offer(E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(first==null){
            first = newNode;
            last = newNode;
        }else{
            last.next = newNode;
            newNode.pre = last;
            last = newNode;
        }
        size++;
    }
    //出队列---删除头
    public E poll(){
        E val = null;
        if(first==null){
            return null;
        }else if(first == last){
            first = null;
            last = null;
        }else{
            val = first.val;
            first = first.next;
            first.pre.next = null;
            first.pre = null;
        }
        size--;
        return val;
    }
    //获取队头元素
    public E peek(){
        if(first == null){
            return null;
        }
        return first.val;
    }
    //获取长度
    public int size(){
        return size;
    }
    //判空
    public boolean isEmpty(){
        return first==null;
    }
    //栈和队列一般不进行遍历操作
    public static void main(String[] args) {
        Queue<Integer> q = new Queue<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        System.out.println(q.size());
        System.out.println(q.peek());
        q.poll();
        System.out.println(q.size());


    }
}

4. 循环队列

循环队列使用的是循环数组,为什么不使用普通的数组呢? 

如果使用一段连续的空间则会造成空间假溢出,造成空间的浪费,因为队列是在尾端进行插入,在头部进行删除,这样会造成数组中的元素偏后,如下面的情形:

所以使用的循环数组,循环队列就是解决空间的假溢出。

当对头与队尾重合时如何区分循环队列的空与满呢?我们可以通过添加size来记录队列元素的个数,当size为0时队列为空,当size不为0时,队列为满。

下面是循环队列的实现:

//循环队列
public class CircularQueue {
    int array[];
    int rear = 0;  //队尾下标
    int front = 0;  //队头下标
    int count = 0;   //队列的有效元素的个数
    int N;          
    public CircularQueue(int k) {
        array = new int[k];             //创建一个数组
        N = array.length;         //用N标记数组的长度
    }

    public boolean enQueue(int value) {     //入队列
        if(isFull()){
            return false;     //如果队列已经满了,则返回false
        }
        array[rear] = value;
        rear++;
        if(rear==N){        //rear返回起始位置
            rear = 0;
        }
        count++;
        return true;
    }

    public boolean deQueue() {     //出队列
        if(isEmpty()){           //如果队列为空,则返回false
            return false; 
        }
        front++;
        front%=N;       //front返回起始位置
        count--;
        return true;
    }

    public int Front() {    //获取队头元素
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }

    public int Rear() {      //获取队尾元素
        if(isEmpty()){
            return -1;
        }
        return array[(rear-1+N)%N];      //队尾元素的下标为rear-1,如果rear为0,则下标就为-1了,所以需要(rear-1+n)% n
    }

    public boolean isEmpty() {     //检测队列是否为空
        return count==0;
    }

    public boolean isFull() {      //检测队列是否已满
        return count==N;
    }
}

5. 双端队列 

双端队列是指允许两端都可以进行入队列和出队列操作的队列,deque(double ended queue的简称)。

6. OJ题 

1. 用队列实现栈 (LeetCode225)用队列实现栈

可以点开上面链接来查看题目

方法:

1. 先创建两个队列

2. 判空:如果两个队列都为空,则返回true,否则返回false

3. 插入元素:当两个队列都为空的时候,随便选一个队列往里插入元素,当有一个队列不为空的时候,往这个不为空的队列里插入元素

4. 删除栈顶元素:哪一个队列不为空,就将这个队列的元素往另一个为空的队列里放,直到不为空的队列剩余一个元素,最后再将这个元素出队列,用一个变量接收并返回

5. 获取栈顶元素:这个操作和前面删除栈顶元素大概相同,只是在返回元素之前,将这个元素插入另一个不为空的队列中

参考代码:

class MyStack {
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
    public MyStack() {
    }
    
    public void push(int x) {
        if(q2.isEmpty()){
            q1.offer(x);
        }else{
            q2.offer(x);
        }
    }
    
    public int pop() {
        int ret = 0;
        if(!q1.isEmpty()){
            while(q1.size()>1){
                q2.offer(q1.poll());
            }
            ret = q1.poll();
        }else{
            while(q2.size()>1){
                q1.offer(q2.poll());
            }
            ret = q2.poll();
        }
        return ret;
    }
    
    public int top() {
        int ret = 0;
        if(!q1.isEmpty()){
            while(q1.size()>1){
                q2.offer(q1.poll());
            }
            ret = q1.poll();
            q2.offer(ret);
        }else{
            while(q2.size()>1){
                q1.offer(q2.poll());
            }
            ret = q2.poll();
            q1.offer(ret);
        }
        return ret;
    }
    
    public boolean empty() {
        if(q1.isEmpty()&&q2.isEmpty()){
            return true;
        }
        return false;
    }
}

2. 实现一个最小栈(LeetCode155)最小栈 

点上述链接查看题目

方法:

1. 先构造两个栈,栈s1储存所有元素,栈s2储存最小元素

2. 入栈:第一个元素给两个栈都添加,下来的元素如果小于等于s2的栈顶元素,则将元素入栈s2,所有元素都入栈s1

3. 获取栈顶元素:直接获取栈s1的栈顶元素

4. 删除栈顶元素:对于s2:如果s1栈顶元素与s2栈顶元素相等,则出栈;对于s1:依次出栈

5. 获取栈里的最小元素:直接返回栈s2的栈顶元素

参考代码:

class MinStack {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
   public MinStack() {

    }
    
    public void push(int val) {
        if(s1.empty()||val<=s2.peek()){
            s2.push(val);
        }
        s1.push(val);
    }
    
    public void pop() {
        if(s1.peek().equals(s2.peek())){
            s2.pop();
        }
        s1.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }
}

3. 用栈实现队列(LeetCode232)用栈实现队列

查看上面链接查看题目

方法:

1. 构造两个栈,一个输入栈s1,一个输出栈s2

2. 判空:当两个栈都为空时,返回true,否则返回false

3. 入队列:直接往栈s1插入元素

4. 出队列:当s2为空时,将s1的所有元素入s2,然后将s2的元素出栈

5. 获取队头元素:当s2为空时,将s1的所有元素入s2,直接获取s2栈顶元素并返回

参考代码:

class MyQueue {
    Stack<Integer> s1 = new Stack<>();   //输入
    Stack<Integer> s2 = new Stack<>();   //输出
    public MyQueue() {

    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
         if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        if(s1.empty()&&s2.empty()){
            return true;
        }
        return false;
    }
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>