면접 문제 7:두 개의 스 택 으로 대기 열 을 실현 합 니 다.

제목 링크:http://ac.jobdu.com/problem.php?pid=1512
사고방식:제목 은 우리 가 두 개의'선진 후 출'창 고 를 이용 하여'선진 선 출'의 대열 을 실현 하도록 요구한다.
삽입 할 때 삽 입 된 요 소 를 stack 1 에 넣 습 니 다.현재 stack 1 에 몇 가지 요 소 를 삽입 했다 고 가정 하면,
삭제 작업 을 진행 하려 고 합 니 다.분명히 현재 스 택 꼭대기 의 요 소 는 나중에 삽입 한 것 이 고 스 택 밑 의 요소 가 있어 야 합 니 다.
삭 제 됩 니 다.stack 1 에 서 는 스 택 기본 요 소 를 직접 삭제 할 수 없습니다.이 럴 때 는 stack 2 를 빌려 야 합 니 다.
stack 2 를 조작 하지 않 았 습 니 다.stack 2 는 비어 있 습 니 다.stack 1 의 요 소 를 스 택 에서 하나씩 나 와 stack 2 에 누 르 고,
그러면 stack 2 의 스 택 상단 요 소 는 삭제 할 요소 입 니 다.그 다음 에 요 소 를 삽입 하려 면 stack 1 에 눌 러 주세요.
요 소 를 삭제 하려 면 stack 2 스 택 상단 요 소 를 삭제 합 니 다.stack 2 가 비어 있 으 면 stack 1 의 모든 요 소 를 삭제 합 니 다.
스 택 을 하나씩 나 와 stack 2 에 누 르 고 삭 제 를 완료 합 니 다.stack 1 과 stack 2 가 모두 비어 있 으 면 삭제 작업 을 완료 할 수 없습니다.
주의:
1.본 문 제 는 템 플 릿 으로 쓰 는 것 이 좋 고 더욱 통용 된다.
2.대기 열 이 비어 있 는 지 아 닌 지 를 판단 하 는 함 수 를 쓸 수 있 습 니 다.
code:

 1 #include <iostream>

 2 #include <stack>

 3 #include <string>

 4 using namespace std;

 5 

 6 template<typename T> class CQueue

 7 {

 8 public:

 9     CQueue(void);

10     ~CQueue(void);

11 

12     void appendTail(const T& node);

13     T deleteHead();

14     bool empty();

15 private:

16     stack<T> stack1;

17     stack<T> stack2;

18 };

19 

20 //    

21 template<typename T> CQueue<T>::CQueue(void)

22 {

23     ;

24 }

25 

26 //    

27 template<typename T> CQueue<T>::~CQueue(void)

28 {

29     ;

30 }

31 

32 template<typename T> void CQueue<T>::appendTail(const T& element)

33 {

34     stack1.push(element);

35 }

36 

37 template<typename T> T CQueue<T>::deleteHead()

38 {

39     if (stack2.size() <= 0)

40     {

41         while (stack1.size() > 0)

42         {

43             T& data = stack1.top();

44             stack1.pop();

45             stack2.push(data);

46         }

47     }

48 

49     T head = stack2.top();

50     stack2.pop();

51     return head;

52 }

53 

54 template<typename T> bool CQueue<T>::empty()

55 {

56     if (stack1.size() + stack2.size() <= 0) return true;

57     return false;

58 }

59 

60 

61 int main()

62 {

63     int n;

64     while (cin >> n)

65     {

66         CQueue<int> myQuence;

67         for (int i = 0; i < n; ++i)

68         {

69             string myStr;

70             cin >> myStr;

71             if (myStr == "PUSH")

72             {

73                 int k;

74                 cin >> k;

75                 myQuence.appendTail(k);

76             }

77             else

78             {

79                 if (myQuence.empty()) cout << -1 << endl;

80                 else cout << myQuence.deleteHead() << endl;

81             }

82         }

83     }

84     return 0;

85 }