C++에서 큐를 사용하여 스택 구현

대기열을 사용하여 하나의 스택을 구현하려고 한다고 가정합니다. 스택에 대해 이러한 메서드를 정의해야 합니다.

• push(x) - x를 스택에 푸시합니다.

• pop() - 스택에서 맨 위 요소 삭제 및 반환

• top() - 스택에서 최상위 요소를 반환합니다.

• empty() - 스택이 비어 있는지 여부를 반환합니다.

따라서 push(10), push(20) 함수를 호출한 다음 pop(), pop()을 호출하면 출력은 20, 10이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 데크 q 정의

• push() 함수를 정의하면 x가 필요합니다.

• q 시작 부분에 x 삽입

• 함수 정의 pop()

• k :=q의 첫 번째 요소

• q에서 앞 요소 삭제

• k를 반환

• 함수 정의 top()

• q

  의 첫 번째 요소를 반환

• empty() 함수 정의

• q가 비어 있으면 -

  • true를 반환

• 그렇지 않으면

  • 거짓을 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class MyStack {
private:
   deque<int> q;
public:
   void push(int x){
      q.push_front(x);
   }
   int pop(){
      int k = q.front();
      q.pop_front();
      return k;
   }
   int top(){
      return q.front();
   }
   bool empty(){
      if (q.empty())
         return true;
      else
         return false;
   }
};
main(){
   MyStack ob;
   ob.push(10);
   ob.push(20);
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
}

입력

push(10),push(20),pop(),pop()

출력

20
10