Comment implémenter la pile et la file d'attente Java

1. Implémenter une file d'attente circulaire

[Lien JO]

Les files d'attente circulaires sont généralement implémentées via des tableaux. Nous devons résoudre plusieurs problèmes.

(1) L'indice Array implémente la boucle

a, l'indice est le dernier puis vers l'arrière (le décalage est inférieur à array.length) : index = (index + offset) % array.length. Pour le dire plus simplement, si la taille de notre tableau est de 8 et que l'indice atteint 7, alors comment revenir à 0, nous pouvons y parvenir par (index+1)%8.

b. Lorsque l'indice est le premier, puis en avant, nous effectuons un jugement spécial et le définissons sur la taille du tableau moins un.

(2) Distinguer les files d'attente pleines et vides

Nous pouvons réserver une position pour le tableau Si arrière+1=avant, cela signifie que la file d'attente est pleine ; si arrière=avant, cela signifie que la file d'attente est vide. Dans ce cas, nous devons prendre en compte la taille de la file d'attente lors de la définition de la taille du tableau, elle doit être supérieure d'un point à celle d'origine.

【Le code est le suivant】

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] array;
 
    //构造方法
    public MyCircularQueue(int k) {
       //因为预留位置的缘故，数组的大小要定义为k+1
       this.array=new int[k+1];
    }
    //入队
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.array[this.rear]=value;
        this.rear=(this.rear+1)%this.array.length;
        return true;
    }
    //出队
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.array.length;
        return true;
    }
    //获取队头
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.array[front];
    }
    //获取队尾
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index=-1;
        if(this.rear==0){
            index=this.array.length-1;
        }else{
            index=this.rear-1;
        }
        return this.array[index];
    }
    //判断是否为空
    public boolean isEmpty() {
        if(this.front==this.rear){
            return true;
        }
        return false;
    }
    //判断队列是否满
    public boolean isFull() {
        if((this.rear+1)%this.array.length==this.front){
            return true;
        }
        return false;
    }
}

2 Pile d'implémentation de la file d'attente

【Lien JO】

En raison du principe du premier entré, dernier sorti de la pile et du premier entré, premier-. principe de la file d'attente. Nous avons besoin de deux files d'attente pour implémenter la pile. Lorsque les deux files d'attente sont vides, la pile est vide.

• Push : peu importe si vous poussez vers la pile pour la première fois. Les deux files d'attente sont vides. Choisissez simplement n'importe quelle file d'attente. Lorsque vous pousserez vers la pile plus tard, il y aura certainement une file d'attente qui sera vide. pas vide. Si vous trouvez une file d'attente qui n'est pas vide, file d'attente vide, effectuez une opération de mise en file d'attente.

• Pop : Premièrement, lorsque la pile est vide, l'opération pop ne peut pas être effectuée ; lorsque la pile n'est pas vide, il doit y avoir une file d'attente vide (queue1) et une file d'attente qui n'est pas vide (queue2). Mettez la file d'attente 1 dans la taille 1, les éléments sont placés dans la file d'attente 2 (notez en particulier que la fonction permettant de trouver la taille de la file d'attente 1 ne peut pas être mise dans la boucle. Lorsque la file d'attente est retirée de la file d'attente, sa taille change), et enfin le dernier élément de la file d'attente 1 est retiré de la file d'attente. . La valeur la plus renvoyée.

• Obtenir l'élément supérieur de la pile (en haut) : C'est presque la même chose que faire éclater la pile, donc je n'entrerai pas dans les détails

[Le code est le suivant]

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
 
    //构造方法
    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }
    //入栈
    public void push(int x) {
        if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }
    //出栈
    public int pop() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int size=queue2.size();
            for(int i=0;i<size-1;++i){
                int x=queue2.poll();
                queue1.offer(x);
            }
            return queue2.poll();
        }else{
            int size=queue1.size();
            for(int i=0;i<size-1;++i){
                int x=queue1.poll();
                queue2.offer(x);
            }
            return queue1.poll();
        }
    }
    //获取栈顶元素
    public int top() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int x=-1;
            int size=queue2.size();
            for(int i=0;i<size;++i){
                x=queue2.poll();
                queue1.offer(x);
            }
           return x;
        }else{
            int size=queue1.size();
            int x=-1;
            for(int i=0;i<size;++i){
                x=queue1.poll();
                queue2.offer(x);
            }
            return x;
        }
    }
    //判断栈是否为空
    public boolean empty() {
        if(queue1.isEmpty()&&queue2.isEmpty()){
            return true;
        }
        return false;
    }
}

3. file d'attente

[Lien JO]

Toujours comme ci-dessus, deux piles (stack1, stack2) sont requises. Différent de l’implémentation de la file d’attente de pile, la mise en file d’attente ne peut fonctionner que sur la même pile. Si les deux piles sont vides, la file d'attente est vide.

• Entrer l'équipe (push) : Il est précisé que stack1 est utilisé pour rejoindre l'équipe. Chaque fois que vous rejoignez la file d'attente, poussez simplement stack1 dans la pile.

• Dequeue (pop) : nécessite stack2 pour effectuer l'opération de retrait de la file d'attente. Si la file d'attente est vide, l'opération de retrait de la file d'attente ne peut pas être effectuée. Lorsque stack2 est vide, nous devons placer tous les éléments de stack1 dans stack2, puis pop stack2. Si stack2 n'est pas vide, pop simplement stack2 directement.

• Obtenir l'élément de début de la file d'attente (peek) : c'est la même chose que l'opération pop. Au final, il vous suffit d'obtenir l'élément supérieur de stack2.

[Le code est le suivant]

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入队操作
    public void push(int x) {
        stack1.push(x);
    }
    //出队操作
    public int pop() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.pop();
 
    }
    //获取队列开头的元素
    public int peek() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.peek();
    }
    //判断队列是否为空
    public boolean empty() {
        if(stack1.empty()&&stack2.empty()){
            return true;
        }
        return false;
    }
}

4. Implémenter la pile minimale

[Lien OJ]

En fait, il s'agit de trouver l'élément minimum de la pile dans la complexité temporelle de O(1) . Deux piles sont nécessaires pour l'implémenter, et une pile est utilisée pour les opérations de popping et de push. Assurez-vous simplement que quelle que soit la façon dont vous opérez, l'élément supérieur de l'autre pile est le plus petit élément de la pile actuelle.

Il y a deux piles stack1 et stack2. Les opérations de la station sont toutes dans la stack1 :

• Pushing : si elle est poussée vers la pile pour la première fois, nous devons également la mettre dans la pile2. les éléments seront poussés vers la pile. Comparez-le avec l'élément supérieur de stack2, s'il est plus petit que l'élément supérieur de stack2, placez-le dans stack2.

• Pop : lorsque vous faites éclater stack1, comparez-le avec l'élément supérieur de stack2. S'il est égal à l'élément supérieur de stack2, pop stack2.

Cela garantit que l'élément supérieur de stack2 est toujours le plus petit élément de stack1. Remarque : Si deux éléments minimum identiques sont poussés dans la pile1, la pile2 doit être poussée dans la pile.

【Le code est le suivant】

class MinStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    public MinStack() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入栈
    public void push(int val) {
        stack1.push(val);
        if(stack2.empty()){
            stack2.push(val);
        }else{
            if(val<=stack2.peek()){
                stack2.push(val);
            }
        }
    }
    //出栈
    public void pop() {
        int x=stack1.pop();
        if(x==stack2.peek()){
            stack2.pop();
        }
    }
    //获取栈顶元素
    public int top() {
        return stack1.peek();
    }
    //获取栈的最小元素
    public int getMin() {
        return stack2.peek();
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!