2つのスタックを使用してキューを実装するC++プログラム

スタック

挿入と削除が同じ端、上から行われるLIFOとして実装されるスタック。最後に入力した要素が最初に削除されます。

スタック操作は-

• プッシュ（intデータ） −上部への挿入
• int pop（） −上からの削除

キュー

挿入が一方の端（後部）で行われ、削除がもう一方の端（前部）から行われるFIFOとして実装されるキュー。入力した最初の要素が最初に削除されます。

キュー操作は-

• EnQueue（intデータ） −後端への挿入
• int DeQueue（） −フロントエンドからの削除

これは、2つのスタックを使用してキューを実装するためのC++プログラムです。

機能の説明

• 関数enQueue（）を使用して、アイテムをキューに入れます：
  • mをs1にプッシュします。
• 関数deQueue（）を使用して、アイテムをキューからデキューします。
  • 両方のスタックが空の場合、印刷キューは空です。
  • s2が空の場合は、要素をs1からs2に移動します。
  • s2から要素をポップして返します。
• 関数push（）を使用して、スタック内のアイテムをプッシュします。
• 関数pop（）を使用して、スタックからアイテムをポップアウトします。

サンプルコード

#include<stdlib.h>
#include<iostream>
using namespace std;

struct nod//node declaration {
   int d;
   struct nod *n;
};

void push(struct nod** top_ref, int n_d);//functions prototypes.
int pop(struct nod** top_ref);

struct queue {
   struct nod *s1;
   struct nod *s2;
};

void enQueue(struct queue *q, int m) {
   push(&q->s1, m);
}

int deQueue(struct queue *q) {
   int m;
   if (q->s1 == NULL && q->s2 == NULL) {
      cout << "Queue is empty";
      exit(0);
   }
   if (q->s2 == NULL) {
      while (q->s1 != NULL) {
         m = pop(&q->s1);
         push(&q->s2, m);
      }
   }
   m = pop(&q->s2);
   return m;
}

void push(struct nod** top_ref, int n_d) {
   struct nod* new_node = (struct nod*) malloc(sizeof(struct nod));

   if (new_node == NULL) {
      cout << "Stack underflow \n";
      exit(0);
   }
   //put items on stack
   new_node->d= n_d;
   new_node->n= (*top_ref);
   (*top_ref) = new_node;
}

int pop(struct nod** top_ref) {
   int res;
   struct nod *top;
   if (*top_ref == NULL)//if stack is null {
      cout << "Stack overflow \n";
      exit(0);
   } else { //pop elements from stack
      top = *top_ref;
      res = top->d;
      *top_ref = top->n;
      free(top);
      return res;
   }
}

int main() {
   struct queue *q = (struct queue*) malloc(sizeof(struct queue));
   q->s1 = NULL;
   q->s2 = NULL;
   cout << "Enqueuing..7";
   cout << endl;
   enQueue(q, 7);
   cout << "Enqueuing..6";
   cout << endl;
   enQueue(q, 6);
   cout << "Enqueuing..2";
   cout << endl;
   enQueue(q, 2);
   cout << "Enqueuing..3";
   cout << endl;
   enQueue(q, 3);

   cout << "Dequeuing...";
   cout << deQueue(q) << " ";
   cout << endl;
   cout << "Dequeuing...";
   cout << deQueue(q) << " ";
   cout << endl;
   cout << "Dequeuing...";
   cout << deQueue(q) << " ";
   cout << endl;
}

出力

Enqueuing..7
Enqueuing..6
Enqueuing..2
Enqueuing..3
Dequeuing...7
Dequeuing...6
Dequeuing...2