두 개의 큐를 사용하여 스택을 구현하는 C++ 프로그램

스택

LIFO로 구현된 스택으로, 삽입과 삭제가 같은 끝, 위쪽에서 수행됩니다. 마지막으로 입력한 요소가 먼저 삭제됩니다.

스택 작업은 -

• 푸시(int 데이터) − 상단 삽입
• int 팝() − 위에서 삭제

대기열

삽입이 한쪽 끝(뒤)에서 수행되고 삭제가 다른 끝(앞)에서 수행되는 FIFO로 구현되는 대기열입니다. 가장 먼저 입력된 요소가 먼저 삭제됩니다.

대기열 작업은 -

• EnQueue(int 데이터) − 후면 끝에 삽입
• int DeQueue() − 프런트 엔드에서 삭제

두 개의 큐를 사용하여 스택을 구현하는 C++ 프로그램입니다.

알고리즘

Begin
   function enqueue1 to insert item a at qu1:
   Set, np1 = new qu1
   np1->d1 = a
   np1->n1 = NULL
   if (f1 == NULL)
      Then set
      r1 = np1
      r1->n1 = NULL
      f1 = r1
   else
      r1->n1 = np1
      r1 = np1
      r1->n1 = NULL
End

Begin
   function dequeue1 to delete item from qu1.
   if queue is null
      Print no elements present in queue.
   Else
      q1 = f1
      f1 = f1->n1
      a = q1->d1
      delete(q1)
   return a
End

Begin
   function enqueue2 to insert item a at qu2.
   np2 = new qu2;
   np2->d2 = a;
   np2->n2 = NULL;
   if queue is null
      Set r2 = np2
      r2->n2 = NULL
      f2 = r2
   Else
      Set r2->n2 = np2
      r2 = np2
      r2->n2 = NULL
End

Begin
   function dequeue2 to delete item from qu2:
   if queue is null
      Print no elements present in queue.
   Else
      q2 = f2
      f2 = f2->n2
      a = q2->d2
      delete(q2)
   return a
End

예시 코드

#include<iostream>
using namespace std;

struct qu1// queue1 declaration {
   qu1 *n1;
   int d1;
}*f1 = NULL, *r1 = NULL, *q1 = NULL, *p1 = NULL, *np1 = NULL;

struct qu2// queue2 declaration {
   qu2 *n2;
   int d2;
}*f2 = NULL, *r2 = NULL, *q2 = NULL, *p2 = NULL, *np2 = NULL;

void enqueue1(int a) {
   np1 = new qu1;
   np1->d1 = a;
   np1->n1 = NULL;
   if (f1 == NULL) {
      r1 = np1;
      r1->n1 = NULL;
      f1 = r1;
   } else {
      r1->n1 = np1;
      r1 = np1;
      r1->n1 = NULL;
   }
}

int dequeue1() {
   int a;
   if (f1 == NULL) {
      cout<<"no elements present in queue\n";
   } else {
      q1 = f1;
      f1 = f1->n1;
      a = q1->d1;
      delete(q1);
      return a;
   }
}

void enqueue2(int a) {
   np2 = new qu2;
   np2->d2 = a;
   np2->n2 = NULL;
   if (f2 == NULL) {
      r2 = np2;
      r2->n2 = NULL;
      f2 = r2;
   } else {
      r2->n2 = np2;
      r2 = np2;
      r2->n2 = NULL;
   }
}

int dequeue2() {
   int a;
   if (f2 == NULL) {
      cout<<"no elements present in queue\n";
   } else {
      q2 = f2;
      f2 = f2->n2;
      a = q2->d2;
      delete(q2);
      return a;
   }
}

int main() {
   int n, a, i = 0;
   cout<<"Enter the number of elements to be entered into stack\n";
   cin>>n;
   while (i < n) {
      cout<<"enter the element to be entered\n";
      cin>>a;
      enqueue1(a);
      i++;
   }
   cout<<"\n\nElements popped\n\n";
   while (f1 != NULL || f2 != NULL)// if both queues are not null {
      if (f2 == NULL)// if queue 2 is null {
         while (f1->n1 != NULL) {
            enqueue2(dequeue1());
         }
         cout<<dequeue1()<<endl;
      } else if (f1 == NULL)//if queue 1 is null {
         while (f2->n2 != NULL) {
            enqueue1(dequeue2());
         }
         cout<<dequeue2()<<endl;
      }
   }
}

출력

Enter the number of elements to be entered into stack
5
enter the element to be entered
1
enter the element to be entered
2
enter the element to be entered
3
enter the element to be entered
4
enter the element to be entered
5

Elements popped
5
4
3
2
1