Leetcode stack and queue questions

Write it at the front ： Review the basic knowledge of stack and queue , And then through leetcode To deepen our understanding of several topics , More is the use of stacks and queues , There is no specific implementation of stack and queue operations

Topic 1

622. Design loop queue

 Design your loop queue implementation .  Circular queue is a linear data structure , Its operation performance is based on  FIFO（ fifo ） Principle and the end of the team is connected behind the head of the team to form a loop . It's also called “ Ring buffer ”.

 One of the benefits of circular queues is that we can take advantage of the previously used space in this queue . In a normal queue , Once a queue is full , We can't insert the next element , There's room even in front of the queue . But with circular queues , We can use this space to store new values .

 Your implementation should support the following operations ：

MyCircularQueue(k):  Constructors , Set queue length to  k .
Front:  Get elements from team leader . If the queue is empty , return  -1 .
Rear:  Get team end element . If the queue is empty , return  -1 .
enQueue(value):  Insert an element into the loop queue . True if successfully inserted .
deQueue():  Remove an element from the loop queue . True if deleted successfully .
isEmpty():  Check if the loop queue is empty .
isFull():  Check if the loop queue is full .

Question answer

matters needing attention ：

• ArrayList It's a variable length array , There is no need to set the length , Usage method

ArrayList<Integer> arrayList = new ArrayList<>();

The problem can be realized by array

• Queue is tail in , Head out
  In the title headIndex It represents the index of the header , So there is no need to change when joining the team headIndex Of

class MyCircularQueue {
    
    Integer[] Q; 
    int headIndex;
    int count;
    int length;
    public MyCircularQueue(int k) {
    
        Q = new Integer[k];
        headIndex = 0;
        count = 0;
        length = k;
    }
    
    public boolean enQueue(int value) {
    
        if(count == length){
    
            return false;
        }
        else{
    
            Q[(headIndex + count) % length] = value;
            count++;
            return true;
        }
    }
    
    public boolean deQueue() {
    
        if(count == 0){
    
            return false;
        }
        else{
    
            count--;
            headIndex = (headIndex +1 ) % length;
            return true;
        }
    }
    
    public int Front() {
    
        if(count == 0){
    
            return -1;
        }
        return Q[headIndex];

    }
    
    public int Rear() {
      
        if(count == 0){
    
            return -1;
        }
        //System.out.println((headIndex + count)%length);
        return Q[(headIndex + count - 1) % length];
    }
    
    public boolean isEmpty() {
    
        return (count == 0);
    }
    
    public boolean isFull() {
    
        return (count == length);
    }
}

/** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue obj = new MyCircularQueue(k); * boolean param_1 = obj.enQueue(value); * boolean param_2 = obj.deQueue(); * int param_3 = obj.Front(); * int param_4 = obj.Rear(); * boolean param_5 = obj.isEmpty(); * boolean param_6 = obj.isFull(); */

Topic two

232. Using stack to realize queue

 Please use only two stacks to implement the FIFO queue . The queue should support all operations supported by the general queue （push、pop、peek、empty）：

 Realization  MyQueue  class ：

void push(int x)  Put the element  x  Push to the end of the queue 
int pop()  Remove from the beginning of the queue and return the element 
int peek()  Returns the element at the beginning of the queue 
boolean empty()  If the queue is empty , return  true ; otherwise , return  false
 explain ：

 you   Can only   Use standard stack operations  ——  It's just  push to top, peek/pop from top, size,  and  is empty  Operation is legal .
 The language you use may not support stacks . You can use  list  perhaps  deque（ deque ） To simulate a stack , As long as it's a standard stack operation .

Question answer

class MyQueue {
    
    Stack<Integer> a;
    Stack<Integer> b;
    public MyQueue() {
    
        a = new Stack<Integer>();
        b = new Stack<Integer>();
    }
    
    public void push(int x) {
    
        a.push(x);
    }
    
    public int pop() {
    
        if(!b.isEmpty()){
    
            return b.pop();
        }
        else{
    
            while(!a.isEmpty()){
    
                b.push(a.pop());
            }
            return b.pop();
        }
    }
    
    public int peek() {
    
        if(!b.isEmpty()){
    
            return b.peek();
        }
        else{
    
            while(!a.isEmpty()){
    
                b.push(a.pop());
            }
            return b.peek();
        }
    }
    
    public boolean empty() {
    
        return a.isEmpty() && b.isEmpty();
    }
}

/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */

Topic three

225. Using queue to implement stack

 Please use only two queues to implement one LIFO （LIFO） The stack , And supports all four operations of ordinary stack （push、top、pop  and  empty）.

 Realization  MyStack  class ：

void push(int x)  Put the element  x  Press into the top of the stack .
int pop()  Remove and return the top element of the stack .
int top()  Back to top of stack element .
boolean empty()  If the stack is empty , return  true ; otherwise , return  false .
 

 Be careful ：

 You can only use the basic operations of the queue  ——  That is to say  push to back、peek/pop from front、size  and  is empty  These operations .
 The language you use may not support queues .  You can use  list （ list ） perhaps  deque（ deque ） To simulate a queue  ,  As long as it's a standard queue operation .
 

Question answer

class MyStack {
    
    Queue<Integer> Q1;
    Queue<Integer> Q2;
    public MyStack() {
    
        Q1 = new LinkedList<Integer>();
        Q2 = new LinkedList<Integer>();

    }
    
    public void push(int x) {
    
        Q2.offer(x);
        while(!Q1.isEmpty()){
    
            Q2.offer(Q1.poll());
        }
        Queue<Integer> temp = new LinkedList<Integer>();
        temp = Q1;
        Q1 = Q2;
        Q2 = temp;
    }
    
    public int pop() {
    
        return Q1.poll();
    }
    
    public int top() {
    
        return Q1.peek();
    }
    
    public boolean empty() {
    
        return Q1.isEmpty();
    }
}

/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */