2 つのスタックがあり、他の一時変数はないとします。
2 つのスタックのみを使用してキュー データ構造を「構築」することは可能ですか?
350875 次
21 に答える
766
inbox2つのスタックを保持し、それらを呼び出しましょうoutbox。
エンキュー：
- 新しい要素を上にプッシュします
inbox
デキュー：
outbox空の場合は、から各要素をポップinboxして上にプッシュすることにより、それを補充しますoutboxから一番上の要素をポップして返します
outbox
この方法を使用すると、各要素は各スタックに1回だけ存在します。つまり、各要素は2回プッシュされ、2回ポップされ、償却された定数時間の操作が可能になります。
Javaでの実装は次のとおりです。
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}
于 2008-09-16T04:42:02.777 に答える
288
A - スタックを逆にする方法
2 つのスタックを使用してキューを構築する方法を理解するには、スタックを明確に逆にする方法を理解する必要があります。積み重ねがどのように機能するかを覚えておいてください。これは、キッチンの皿の積み重ねに非常に似ています。最後に洗浄された皿は、クリーン スタックの一番上に置かれます。これは、コンピューター サイエンスでは Last I n First Out ( LIFO )と呼ばれます。
以下のように、スタックをボトルのように想像してみましょう。
整数 1、2、3 をそれぞれプッシュすると、3 がスタックの一番上になります。1 が最初にプッシュされるため、2 が 1 の上に配置されます。最後に、3 がスタックの一番上に配置され、ボトルとして表されるスタックの最新の状態は次のようになります。
これで、スタックがボトルとして表され、値 3、2、1 が取り込まれました。そして、スタックの一番上の要素が 1 になり、スタックの一番下の要素が 3 になるように、スタックを反転させたいと思います。何ができますか? すべての値が順番に逆になるように、ボトルを逆さまに保持できますか?
はい、できますが、それはボトルです。同じプロセスを実行するには、最初のスタック要素を逆順に格納する 2 番目のスタックが必要です。移入されたスタックを左に置き、新しい空のスタックを右に置きましょう。要素の順序を逆にするために、左のスタックから各要素をポップし、それらを右のスタックにプッシュします。下の画像で、そうすると何が起こるかを見ることができます。
これで、スタックを逆にする方法がわかりました。
B - 2 つのスタックをキューとして使用する
前のパートでは、スタック要素の順序を逆にする方法について説明しました。要素をスタックにプッシュおよびポップすると、出力はキューとまったく逆の順序になるため、これは重要でした。例を考えて、整数の配列を{1, 2, 3, 4, 5}スタックにプッシュしてみましょう。要素をポップして、スタックが空になるまで出力すると、プッシュ順序の逆順で配列が取得されます。これは{5, 4, 3, 2, 1}、同じ入力に対して、キューが空になるまでキューをデキューすると、出力がとなります{1, 2, 3, 4, 5}。したがって、要素の入力順序が同じ場合、キューの出力はスタックの出力とまったく逆であることは明らかです。追加のスタックを使用してスタックを逆にする方法を知っているので、2 つのスタックを使用してキューを構築できます。
キュー モデルは 2 つのスタックで構成されます。1 つのスタックが操作に使用されenqueue(左側のスタック #1 は入力スタックと呼ばれます)、別のスタックがdequeue操作に使用されます (右側のスタック #2 は出力スタックと呼ばれます)。下の画像をご覧ください。
擬似コードは次のとおりです。
エンキュー操作
Push every input element to the Input Stack
デキュー操作
If ( Output Stack is Empty)
pop every element in the Input Stack
and push them to the Output Stack until Input Stack is Empty
pop from Output Stack
それぞれ整数をキューに入れましょう{1, 2, 3}。整数は、左側にある入力スタック(スタック #1 ) にプッシュされます。
では、デキュー操作を実行するとどうなるでしょうか。デキュー操作が実行されるたびに、キューは出力スタックが空かどうかをチェックします (上記の疑似コードを参照) 出力スタックが空の場合、入力スタックが出力で抽出されるため、要素の入力スタックが逆になります。値を返す前のキューの状態は次のようになります。
出力スタック (スタック #2) 内の要素の順序を確認してください。出力スタックから要素をポップして、出力がキューからデキューした場合と同じになることは明らかです。したがって、2 つのデキュー操作を実行すると、最初に{1, 2}それぞれ取得します。次に、要素 3 が出力スタックの唯一の要素になり、入力スタックは空になります。要素 4 と 5 をキューに入れると、キューの状態は次のようになります。
出力スタックは空ではありません。デキュー操作を実行すると、出力スタックからポップアウトされるのは 3 つだけです。次に、状態は次のように表示されます。
繰り返しますが、さらに 2 つのデキュー操作を実行すると、最初のデキュー操作で、キューは出力スタックが空であるかどうかを確認します。これは true です。次に、入力スタックの要素をポップアウトし、入力スタックが空になるまでそれらを出力スタックにプッシュすると、キューの状態は次のようになります。
見やすいように、2 つのデキュー操作の出力は次のようになります。{4, 5}
C - 2 つのスタックで構築されたキューの実装
これは Java での実装です。Stack の既存の実装を使用するつもりはないので、ここでの例では車輪を再発明します。
C - 1) MyStack クラス : シンプルなスタック実装
public class MyStack<T> {
// inner generic Node class
private class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
}
private Node<T> head;
private int size;
public void push(T e) {
Node<T> newElem = new Node(e);
if(head == null) {
head = newElem;
} else {
newElem.next = head;
head = newElem; // new elem on the top of the stack
}
size++;
}
public T pop() {
if(head == null)
return null;
T elem = head.data;
head = head.next; // top of the stack is head.next
size--;
return elem;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void printStack() {
System.out.print("Stack: ");
if(size == 0)
System.out.print("Empty !");
else
for(Node<T> temp = head; temp != null; temp = temp.next)
System.out.printf("%s ", temp.data);
System.out.printf("\n");
}
}
C - 2) MyQueue クラス : 2 つのスタックを使用したキューの実装
public class MyQueue<T> {
private MyStack<T> inputStack; // for enqueue
private MyStack<T> outputStack; // for dequeue
private int size;
public MyQueue() {
inputStack = new MyStack<>();
outputStack = new MyStack<>();
}
public void enqueue(T e) {
inputStack.push(e);
size++;
}
public T dequeue() {
// fill out all the Input if output stack is empty
if(outputStack.isEmpty())
while(!inputStack.isEmpty())
outputStack.push(inputStack.pop());
T temp = null;
if(!outputStack.isEmpty()) {
temp = outputStack.pop();
size--;
}
return temp;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
C - 3) デモコード
public class TestMyQueue {
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<>();
// enqueue integers 1..3
for(int i = 1; i <= 3; i++)
queue.enqueue(i);
// execute 2 dequeue operations
for(int i = 0; i < 2; i++)
System.out.println("Dequeued: " + queue.dequeue());
// enqueue integers 4..5
for(int i = 4; i <= 5; i++)
queue.enqueue(i);
// dequeue the rest
while(!queue.isEmpty())
System.out.println("Dequeued: " + queue.dequeue());
}
}
C - 4) サンプル出力
Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
于 2016-08-22T23:01:21.293 に答える
80
1つのスタックのみを使用してキューをシミュレートすることもできます。2番目の（一時的な）スタックは、insertメソッドへの再帰呼び出しの呼び出しスタックによってシミュレートできます。
新しい要素をキューに挿入するときの原則は同じです。
- 要素をあるスタックから別の一時スタックに転送して、順序を逆にする必要があります。
- 次に、挿入する新しい要素を一時スタックにプッシュします
- 次に、要素を元のスタックに戻します
- 新しい要素はスタックの一番下にあり、最も古い要素は一番上にあります（最初にポップされます）
1つのスタックのみを使用するQueueクラスは、次のようになります。
public class SimulatedQueue<E> {
private java.util.Stack<E> stack = new java.util.Stack<E>();
public void insert(E elem) {
if (!stack.empty()) {
E topElem = stack.pop();
insert(elem);
stack.push(topElem);
}
else
stack.push(elem);
}
public E remove() {
return stack.pop();
}
}
于 2008-09-16T20:58:59.807 に答える
14
ただし、時間の複雑さはさらに悪化します。優れたキューの実装では、一定時間内にすべてが実行されます。
編集
ここで私の答えが反対票を投じられた理由がわかりません。プログラミングする場合、時間の複雑さが気になり、キューを作成するために 2 つの標準スタックを使用するのは非効率的です。これは非常に有効で適切なポイントです。他の誰かがこれにもっと反対票を投じる必要があると感じたら、その理由を知りたい.
もう少し詳しく: 2 つのスタックを使用することが単なるキューよりも悪い理由について: 2 つのスタックを使用していて、送信ボックスが空のときに誰かがデキューを呼び出した場合、受信ボックスの一番下に到達するのに直線的な時間が必要です (ご覧のとおり)。デイブのコードで）。
プッシュのために最後に挿入された要素への追加のポインターを保持する (または循環リストにする) 単一リンク リスト (各要素は次に挿入される要素を指す) としてキューを実装できます。このデータ構造にキューとデキューを実装するのは非常に簡単で、一定の時間で実行できます。これは、償却されていない、最悪の場合の一定時間です。そして、コメントがこの明確化を求めているように見えるので、最悪の場合の一定時間は、償却された一定時間よりも厳密に優れています。
于 2008-09-16T03:40:44.967 に答える
8
実装するキューをq、qを実装するために使用するスタックをstack1とstack2とする。
q は次の2 つの方法で実装できます。
方法 1 (enQueue 操作を高コストにすることにより)
このメソッドは、新しく入力された要素が常にスタック 1 の一番上にあることを確認するため、deQueue 操作はスタック 1 からポップされます。要素を stack1 の一番上に配置するには、stack2 が使用されます。
enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.
方法 2 (deQueue 操作を高コストにすることにより)
このメソッドでは、エンキュー操作で、新しい要素が stack1 の先頭に入力されます。デキュー操作では、stack2 が空の場合、すべての要素が stack2 に移動され、最後に stack2 の先頭が返されます。
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
方法 2 は方法 1 よりも確実に優れています。方法 1 は enQueue 操作ですべての要素を 2 回移動しますが、方法 2 (deQueue 操作) は要素を 1 回移動し、stack2 が空の場合にのみ要素を移動します。
于 2014-03-30T22:34:40.437 に答える
2
一番下の要素を取得するには、最初のスタックからすべてをポップする必要があります。次に、「デキュー」操作ごとに、それらすべてを2番目のスタックに戻します。
于 2008-09-16T04:26:11.707 に答える
2
キュー内の 2 つのスタックは、stack1およびstack2として定義されています。
Enqueue: キューに入れられた要素は常にstack1にプッシュされます。
デキュー:スタック 2 が空でない場合、スタック 2の先頭がキューに挿入される最初の要素であるため、スタック 2 の先頭をポップアウトでき ます。stack2が空の場合、stack1 からすべての要素をポップし、それらを1 つずつstack2にプッシュします。キューの最初の要素は、stack1の一番下にプッシュされます。stack2の一番上にあるため、ポップおよびプッシュ操作の直後にポップアウトできます。
以下は、同じ C++ サンプル コードです。
template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T> void CQueue<T>::appendTail(const T& element) {
stack1.push(element);
}
template<typename T> T CQueue<T>::deleteHead() {
if(stack2.size()<= 0) {
while(stack1.size()>0) {
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size() == 0)
throw new exception("queue is empty");
T head = stack2.top();
stack2.pop();
return head;
}
このソリューションは私のブログから借りています。ステップバイステップの動作シミュレーションによるより詳細な分析は、私のブログの Web ページで入手できます。
于 2012-12-29T02:02:15.273 に答える
0
Go の標準ライブラリには多くの豊富なコレクションがないため、Go でこの質問に答えます。
スタックは非常に簡単に実装できるので、2 つのスタックを使用してダブルエンド キューを実現しようと考えました。答えにたどり着いた方法をよりよく理解するために、実装を 2 つの部分に分けました。最初の部分は理解しやすいと思いますが、不完全です。
type IntQueue struct {
front []int
back []int
}
func (q *IntQueue) PushFront(v int) {
q.front = append(q.front, v)
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[0]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
q.back = q.back[1:]
}
}
func (q *IntQueue) PushBack(v int) {
q.back = append(q.back, v)
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[0]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
q.front = q.front[1:]
}
}
これは基本的に 2 つのスタックであり、スタックの下部を相互に操作できるようにします。また、STL 命名規則も使用しました。スタックの従来のプッシュ、ポップ、ピーク操作には、キューの前または後ろを参照するかどうかにかかわらず、前/後接頭辞があります。
上記のコードの問題は、メモリをあまり効率的に使用しないことです。実際には、スペースがなくなるまで無限に成長します。それは本当に悪いです。これを修正するには、可能な限りスタック スペースの下部を単純に再利用します。これを追跡するためにオフセットを導入する必要があります。これは、Go のスライスは一度縮小すると前面に拡大できないためです。
type IntQueue struct {
front []int
frontOffset int
back []int
backOffset int
}
func (q *IntQueue) PushFront(v int) {
if q.backOffset > 0 {
i := q.backOffset - 1
q.back[i] = v
q.backOffset = i
} else {
q.front = append(q.front, v)
}
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[q.backOffset]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
if len(q.back) > 0 {
q.backOffset++
} else {
panic("Cannot pop front of empty queue.")
}
}
}
func (q *IntQueue) PushBack(v int) {
if q.frontOffset > 0 {
i := q.frontOffset - 1
q.front[i] = v
q.frontOffset = i
} else {
q.back = append(q.back, v)
}
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[q.frontOffset]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
if len(q.front) > 0 {
q.frontOffset++
} else {
panic("Cannot pop back of empty queue.")
}
}
}
小さな機能がたくさんありますが、6 つの機能のうち 3 つが他の機能の単なるミラーです。
于 2016-05-22T16:08:49.340 に答える
0
PHP を使用した私のソリューション
<?php
$_fp = fopen("php://stdin", "r");
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
$queue = array();
$count = 0;
while($line = fgets($_fp)) {
if($count == 0) {
$noOfElement = $line;
$count++;
continue;
}
$action = explode(" ",$line);
$case = $action[0];
switch($case) {
case 1:
$enqueueValue = $action[1];
array_push($queue, $enqueueValue);
break;
case 2:
array_shift($queue);
break;
case 3:
$show = reset($queue);
print_r($show);
break;
default:
break;
}
}
?>
于 2021-04-22T02:42:18.007 に答える
-1
public class QueueUsingStacks<T>
{
private LinkedListStack<T> stack1;
private LinkedListStack<T> stack2;
public QueueUsingStacks()
{
stack1=new LinkedListStack<T>();
stack2 = new LinkedListStack<T>();
}
public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
{
while(source.Head!=null)
{
dest.Push(source.Head.Data);
source.Head = source.Head.Next;
}
}
public void Enqueue(T entry)
{
stack1.Push(entry);
}
public T Dequeue()
{
T obj;
if (stack2 != null)
{
Copy(stack1, stack2);
obj = stack2.Pop();
Copy(stack2, stack1);
}
else
{
throw new Exception("Stack is empty");
}
return obj;
}
public void Display()
{
stack1.Display();
}
}
エンキュー操作ごとに、stack1の一番上に追加します。デキューするたびに、stack1のコンテンツをstack2に空にし、スタックの最上位にある要素を削除します。stack1をstack2にコピーする必要があるため、デキューの時間計算量はO（n）です。エンキューの時間計算量は通常のスタックと同じです
于 2012-04-11T17:54:14.877 に答える
-2
2 つの java.util.Stack オブジェクトを使用したキューの実装:
public final class QueueUsingStacks<E> {
private final Stack<E> iStack = new Stack<>();
private final Stack<E> oStack = new Stack<>();
public void enqueue(E e) {
iStack.push(e);
}
public E dequeue() {
if (oStack.isEmpty()) {
if (iStack.isEmpty()) {
throw new NoSuchElementException("No elements present in Queue");
}
while (!iStack.isEmpty()) {
oStack.push(iStack.pop());
}
}
return oStack.pop();
}
public boolean isEmpty() {
if (oStack.isEmpty() && iStack.isEmpty()) {
return true;
}
return false;
}
public int size() {
return iStack.size() + oStack.size();
}
}
于 2016-08-06T08:04:40.213 に答える