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

스택

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

스택 작업은 -

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

대기열

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

대기열 작업은 -

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

두 개의 스택을 사용하여 큐를 구현하는 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