＜习题集＞＜LeetCode＞＜队列＞＜225/232/387/622/641＞

目录

225. 用队列实现栈

232. 用栈实现队列

387. 字符串中的第一个唯一字符

622. 设计循环队列

641. 设计循环双端队列

---

225. 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

class MyStack{
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    //构造方法；
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    //压栈；
    public void push(int x){
        //两个队列为空，则选一个先入队列，这里选queue2；
        //之后哪个队列非空，则入哪个队列；
        if (!queue1.isEmpty()){
            queue1.offer(x);
        }else{
            queue2.offer(x);
        }
    }
    //出栈；
    public int pop(){
        //哪个队列非空，就将这个队列的元素转移到另一个队列；
        //转移过程中，记录每一个出队列的元素；
        //直到出元素的队列为空，不将该元素入队列，而是返回；
        if(!queue1.isEmpty()){
            int temp = queue1.poll();
            while (!queue1.isEmpty()){
                queue2.offer(temp);
                temp = queue1.poll();
            }
            return temp;
        }else if(!queue2.isEmpty()){
            int temp = queue2.poll();
            while (!queue2.isEmpty()){
                queue1.offer(temp);
                temp = queue2.poll();
            }
            return temp;
        }
        return -1;
    }
    //查看栈顶元素；
    public int top(){
        //哪个队列非空，就将这个队列的元素转移到另一个队列；
        //转移过程中，记录每一个出队列的元素，直到出元素的队列为空，返回记录的元素；
        int temp = -1;
        if(!queue1.isEmpty()){
            while(!queue1.isEmpty()){
                temp = queue1.poll();
                queue2.offer(temp);
            }
        }else if(!queue2.isEmpty()){
            while(!queue2.isEmpty()){
                temp = queue2.poll();
                queue1.offer(temp);
            }
        }
        return temp;
    }
    //判断栈是否为空；
    public boolean empty(){
        if(queue1.isEmpty() && queue2.isEmpty()){
            return true;
        }else {
            return false;
        }
    }
}

---

232. 用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

class MyQueue{
    //两个栈；
    private Stack<Integer> stack1 = null;
    private Stack<Integer> stack2 = null;
    //构造方法，初始化两个栈；
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    //压栈，stack1负责元素入队列；
    public void push(int x){
        stack1.push(x);
    }
    //stack2负责元素出队列；
    public int pop(){
        //如果stack2不为空，直接出；
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else {
            //如果stack2为空，看看stack1是否为空；
            //不为空将stack1元素转移到stack2，再将stack2栈顶元素出栈；
            if(!stack1.isEmpty()){
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        }
        return -1;
    }
    //stack2的栈顶元素就是队列的队首元素；
    public int peek(){
        //如果stack2不为空，返回栈顶元素；
        if(!stack2.isEmpty()){
            return stack2.peek();
        }else {
            //如果stack2为空，看看stack1是否为空；
            //不为空将stack1元素转移到stack2，再将stack2栈顶元素peek；
            if(!stack1.isEmpty()){
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.peek();
            }
        }
        return -1;
    }

    public boolean empty(){
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

---

387. 字符串中的第一个唯一字符

https://leetcode.cn/problems/first-unique-character-in-a-string/

    public int firstUniqChar1(String s) {
        //创建一个代表26个英文字母的数组；
        int[] arr = new int[26];
        //将字符串s转换为字符数组；(也可以不转，使用String的方法即可)
        char[] chs = s.toCharArray();
        //将每个字符转换成整数，这个整数代表下标，放入arr数组中；
        for(int i=0;i<chs.length;i++){
            int n = chs[i] - 'a';
            arr[n]++;
        }
        //遍历字符数组，查arr数组元素，找到第一个元素为1的，就返回这个字符；
        for(int i=0;i<chs.length;i++){
            int n = chs[i] - 'a';
            if(arr[n] == 1){
                return i;
            }
        }
        //找不到返回-1；
        return -1;
    }

---

622. 设计循环队列

https://leetcode.cn/problems/design-circular-queue/

class MyCircularQueue {
    //用于存放元素的数组elem，队首下标front，队尾下标rear，队列有效元素size；
    private int[] elem;
    private int front;
    private int rear;
    private int size;
    //构造方法，构造容量为k的数组；
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    //入队列方法；
    public boolean enQueue(int value) {
        if(this.isFull()){
            return false;
        }
        //赋值给队尾元素，rear++；
        elem[rear] = value;
        rear++;
        //超过最大容量，下标回到0；
        if(rear >= elem.length){
            rear = 0;
        }
        //有效元素++；
        size++;
        return true;
    }
    //出队列方法；
    public boolean deQueue() {
        if(this.isEmpty()){
            return false;
        }
        //队首下标直接向后移动；
        front++;
        //超过最大容量，下标回到0；
        if(front >= elem.length){
            front = 0;
        }
        //有效元素--；
        size--;
        return true;
    }
    //查看队首元素；
    public int Front() {
        if(this.isEmpty()){
            return -1;
        }
        return elem[front];
    }
    //查看队尾元素；
    public int Rear() {
        if(this.isEmpty()){
            return -1;
        }
        //应注意队尾在每一次入队列后都会向后移动；
        //因此想得到队尾元素需要查看队尾下标的前一个元素；
        int temp = rear-1;
        //处理循环队列中0下标的转换问题；
        if(rear == 0){
            temp = elem.length-1;
        }
        return elem[temp];
    }
    //有效元素为0，则队列为空；
    public boolean isEmpty() {
        return size == 0;
    }
    //有效元素等于数组容量，则队列满；
    public boolean isFull() {
        return size == elem.length;
    }
}

---

641. 设计循环双端队列

https://leetcode.cn/problems/design-circular-deque/

class MyCircularDeque {
    //用于存放元素的数组，队首元素下标，队尾元素下标，有效元素个数；
    private int[] elems;
    private int front;
    private int rear;
    private int size;
    //构造方法；
    public MyCircularDeque(int k) {
        elems = new int[k];
    }
    //头插法；
    public boolean insertFront(int value) {
        //判断是否已满；
        if(this.isFull()){
            return false;
        }
        //队首指针前移，注意转换最大下标和0下标；
        if(front == 0){
            front = elems.length-1;
        }else{
            front--;
        }
        //赋值和有效元素++；
        elems[front] = value;
        size++;
        return true;
    }
    //尾插法；
    public boolean insertLast(int value) {
        //判断是否已满；
        if(this.isFull()){
            return false;
        }
        //赋值和有效元素++；
        elems[rear] = value;
        size++;
        //队尾指针后移，注意转换最大下标和0下标；
        if(rear == elems.length-1){
            rear = 0;
        }else{
            rear++;
        }
        return true;
    }
    //头删法；
    public boolean deleteFront() {
        //判断是否为空；
        if(this.isEmpty()){
            return false;
        }
        //队首指针后移，注意转换最大下标和0下标；
        if(front == elems.length-1){
            front = 0;
        }else{
            front++;
        }
        //有效元素--；
        size--;
        return true;
    }
    //尾删法；
    public boolean deleteLast() {
        //判断是否为空；
        if(this.isEmpty()){
            return false;
        }
        //队尾指针前移，注意转换最大下标和0下标；
        if(rear == 0){
            rear = elems.length-1;
        }else{
            rear--;
        }
        //有效元素--；
        size--;
        return true;
    }
    //查看队首元素；
    public int getFront() {
        if(this.isEmpty()){
            return -1;
        }
        return elems[front];
    }
    //查看队尾元素；
    public int getRear() {
        if(this.isEmpty()){
            return -1;
        }
        //注意队尾元素应该是队尾指针的前一个，注意转换最大下标和0下标；
        int temp = rear-1;
        if(rear == 0){
            temp = elems.length-1;
        }
        return elems[temp];
    }
    //判断是否为空；
    public boolean isEmpty() {
        return size == 0;
    }
    //判断是否已满；
    public boolean isFull() {
        return size == elems.length;
    }
}

---