c - C で FIFO キューを作成する

Question

2 つのスタックを使用せずに C で FIFO 'スタック' を作成することは可能ですか?

ありがとう！

（前の方に回答してくださった方すみません。LIFOとFIFOの意味で考えていました。）

Answer 1

それは非常に簡単です。リストの最後の項目へのポインターを保持して、二重にリンクされたリストを実装するだけです。

キューに追加するには、先頭に新しいノードを作成し、前の先頭にリンクします。(通常のリスト挿入)

キューから削除するには、最後のアイテムへのポインターを逆参照し、ポインターを前のアイテム ポインターに変更し、最後のアイテムを返します... (これが二重リンク リストの理由です。もう 1 つのオプションは単一リンクです。リストを作成し、最後の 2 つの要素へのポインターを取得するためにリスト全体を反復します)。

Answer 2

一方の端に挿入し、もう一方の端から引っ張るキューを作成しようとしているようです。

これを行う 1 つの方法は、リンクされたリストを使用することです。ヘッドとテールへのポインターを格納できます。挿入するときは、新しいレコードをテールに追加し、キューから何かをポップするときは、ヘッド ポインターが指すノードを取得します。（またはその逆、大した問題ではありません）

Answer 3

これは、head 要素を取り出して tail 要素にプッシュする関数のみを定義することを除けば、単なる標準のリンク リストではありませんか? 完全に二重にリンクされたリストではなく、テールポインターを使用して単一にリンクされたリストでこれを行うこともできます。

Answer 4

これに 2 つのスタックを使用するのは面白い解決策ですが、遅い解決策です。通常のキューを使用できるのに、なぜスタックに言及しているのですか? あなたが望むのはFIFOですよね？配列を使用してキューを作成し、その長さをモジュロして循環させることができます。

Answer 5

You can also implement a queue with a circular array.

Answer 6

正しい解決策は既に提案されていますが、FIFO が実際にはスタックではないことを修正したいと思います。

この質問は、スタックを使用してアルゴリズムを構築し、挿入と削除の償却コストが O(1) であることを証明するように求められるアルゴリズムのクラスでよく見られます。

FIFO は、二重リンク リスト、開始ポインタと終了ポインタを持つ配列/ベクトル、循環配列などを使用して構築できます。

Answer 7

I think the OP wanted to know how to handle it if all he's got is stacks, for whatever arcane reason. The trick is to remember that pushing stuff onto a stack and then popping it off reverses the order of the items, so you can use two stacks to reverse it twice.

Incoming items get pushed onto stack1, and are all popped off onto stack2 when stack2 is empty. So the first item gets pushed onto stack1, the immediately popped off and pushed onto stack2, ready for output. Subsequent items stack up on stack1 until stack2 is popped, at which point the last item goes on stack2, then the next-to-last, and so on until stack1 is empty again. Now all of the items are restacked on stack2, with the newest at the bottom and the oldest at the top. New pushes continue to build up on stack1, waiting for stack2 to become empty again, and stack2 just produces the items in the original order until it's empty, at which point we repeat the unstack-restack process.

I won't comment about efficiency, etc.; it's just "you could do it that way". I was asked this in an interview and my immediate answer was "What kind of idiot would do that? Just implement an actual queue and be done with it" - I don't think that was the answer they were looking for though.