Javaスタックとキューを実装する方法

1. 循環キューの実装

[OJ リンク]

循環キューは通常、配列を通じて実装されます。いくつかの問題を解決する必要があります。

(1) 配列の添字はループ

aを実装し、添字は最終的に戻ります(オフセットはarray.lengthより小さい):index = (index offset) % array.length。もっと簡単に言うと、配列のサイズが 8 で添字が 7 に達した場合、どうやって 0 に戻すかというと、(インデックス 1)%8 で実現できます。

b. 添字が最初でその後にある場合は、特別な判断を行って、配列サイズから 1 を引いた値に設定します。

(2) 満杯のキューと空のキューを区別する

配列の位置を予約できます。後部 1=前部の場合はキューが満杯であることを意味します。後部 =前部の場合はキューが満杯であることを意味しますキューは null です。この場合、キューのサイズを考慮する必要があり、配列のサイズを元のサイズより 1 つ大きく定義する必要があります。

[コードは次のとおりです]

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. キュー実装スタック

[OJ リンク]

キューのスタック先入れ後出し、先入れ先出しの原則のため。スタックを実装するには 2 つのキューが必要です。両方のキューが空の場合、スタックは空になります。

• プッシュ: スタックに初めてプッシュするときは問題ありません。両方のキューが空です。キューを選択してキューに入れるだけです。スタックにプッシュするときキューは空ではありません。空ではないキューを見つけて、エンキュー操作を実行してください。

• Pop (pop): まず、スタックが空の場合、pop 操作は実行できません。スタックが空でない場合、空のキューが 1 つ存在する必要があります (queue1) 、および空ではない 1 つのキュー (キュー 2) で、キュー 1 のサイズ 1 の要素をキュー 2 にポップします (キュー 1 のサイズを見つける関数をループに入れないように特に注意してください。キューがデキューされると、そのサイズは変わります)。 、そして最後に queue1 の最後の要素がデキューされ、戻り値になります。

• #スタックの最上位要素の取得 (top): スタックをポップするのとほぼ同じなので、詳細は説明しません

[コードは次のとおりです]

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. スタック実装キュー

#[OJ リンク]

上記と同じ、2 つのスタック (stack1、stack2)が必要です。スタック キューの実装とは異なり、エンキューは同じスタック上でのみ実行できます。両方のスタックが空の場合、キューは空になります。

チームに参加する (プッシュ): チームに参加するために stack1 が使用されることが指定されています。キューに参加するたびに、stack1 をスタックにプッシュするだけです。
デキュー (ポップ): デキュー操作を実行するにはスタック 2 が必要です。キューが空の場合、デキュー操作は実行できません。 stack2 が空の場合、stack1 のすべての要素を stack2 にポップしてから、stack2 をポップする必要があります。 stack2 が空でない場合は、stack2 を直接ポップしてください。
キューの先頭要素の取得 (ピーク): Pop 操作と同じで、最終的には stack2 の先頭要素を取得するだけで済みます。
[コードは次のとおりです]

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. 最小限のスタックを実装します

[OJ リンク]

実際には、それは O( 1) になります。時間計算量内でスタックの最小の要素を見つけます。これを実装するには 2 つのスタックが必要で、1 つのスタックはポップおよびプッシュ操作に使用されます。どのように操作しても、他のスタックの最上位要素が現在のスタックの最小要素であることを確認してください。

2 つのスタック stack1 と stack2、ステーションの操作はすべて stack1 にあります:

スタックへのプッシュ: 初めてスタックにプッシュされた場合stack2 では、スタックにプッシュされると、プッシュされた要素が stack2 の先頭要素と比較され、スタック 2 の先頭要素より小さければ、スタック 2 に置かれます。
Pop: stack1 をポップするときに、stack2 の先頭要素と比較し、stack2 の先頭要素と等しい場合、stack2 をポップします。
これにより、スタック 2 の最上位要素が常にスタック 1 の最小要素となることが保証されます。注: 2 つの同一の最小要素が stack1 にプッシュされる場合は、stack2 をスタックにプッシュする必要があります。

[コードは次のとおりです]

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();
    }
}

以上がJavaスタックとキューを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。