[OJ リンク]
循環キューは通常、配列を通じて実装されます。いくつかの問題を解決する必要があります。
aを実装し、添字は最終的に戻ります(オフセットはarray.lengthより小さい):index = (index offset) % array.length。もっと簡単に言うと、配列のサイズが 8 で添字が 7 に達した場合、どうやって 0 に戻すかというと、(インデックス 1)%8 で実現できます。
b. 添字が最初でその後にある場合は、特別な判断を行って、配列サイズから 1 を引いた値に設定します。
配列の位置を予約できます。後部 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; } }
[OJ リンク]
キューのスタック先入れ後出し、先入れ先出しの原則のため。スタックを実装するには 2 つのキューが必要です。両方のキューが空の場合、スタックは空になります。
プッシュ: スタックに初めてプッシュするときは問題ありません。両方のキューが空です。キューを選択してキューに入れるだけです。スタックにプッシュするときキューは空ではありません。空ではないキューを見つけて、エンキュー操作を実行してください。
Pop (pop): まず、スタックが空の場合、pop 操作は実行できません。スタックが空でない場合、空のキューが 1 つ存在する必要があります (queue1) 、および空ではない 1 つのキュー (キュー 2) で、キュー 1 のサイズ 1 の要素をキュー 2 にポップします (キュー 1 のサイズを見つける関数をループに入れないように特に注意してください。キューがデキューされると、そのサイズは変わります)。 、そして最後に queue1 の最後の要素がデキューされ、戻り値になります。
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; } }
上記と同じ、2 つのスタック (stack1、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. 最小限のスタックを実装します
実際には、それは O( 1) になります。時間計算量内でスタックの最小の要素を見つけます。これを実装するには 2 つのスタックが必要で、1 つのスタックはポップおよびプッシュ操作に使用されます。どのように操作しても、他のスタックの最上位要素が現在のスタックの最小要素であることを確認してください。
2 つのスタック stack1 と stack2、ステーションの操作はすべて stack1 にあります:
[コードは次のとおりです]
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 サイトの他の関連記事を参照してください。