面试题7：用两个栈实现队列

 1 /*cqueue.h*/
 2 #ifndef _CQUEUE_
 3 #define _CQUEUE_
 4 
 5 #include "cstack.h"
 6 
 7 template<class T>
 8 class CQueue
 9 {
10 public:
11     CQueue(int queueSize);
12     bool queueEn(const T& key);
13     bool queueOut(T& key);
14     bool queueEmpty(void);
15     bool queueFull(void);
16     void queueClear(void);
17 private:
18     CStack<T> stackA;
19     CStack<T> stackB;
20 };
21 
22 #endif

 1 /*cqueue.c*/
 2 #include "stdafx.h"
 3 #include "cqueue.h"
 4 
 5 template<class T>
 6 CQueue<T>::CQueue(int queueSize):stackA(queueSize),stackB(queueSize)
 7 {
 8 }
 9 
10 template<class T>
11 bool CQueue<T>::queueEn(const T&key)
12 {
13     T tempKey;
14     bool result;
15 
16     if(stackA.stackFull())
17     {
18         return false;
19     }
20 
21     while(!stackA.stackEmpty())
22     {
23         result = stackA.stackPop(tempKey);
24         if(true != result)
25         {
26             return result;
27         }
28 
29         result = stackB.stackPush(tempKey);
30         if(true != result)
31         {
32             return result;
33         }
34     }
35 
36     result = stackB.stackPush(key);    
37     if(true != result)
38     {
39         return result;
40     }
41 
42     while(!stackB.stackEmpty())
43     {
44         result = stackB.stackPop(tempKey);
45         if(true != result)
46         {
47             return result;
48         }
49 
50         result = stackA.stackPush(tempKey);
51         if(true != result)
52         {
53             return result;
54         }
55     }
56 
57     return true;
58 }
59 
60 template<class T>
61 bool CQueue<T>::queueOut(T &key)
62 {
63     if(stackA.stackEmpty())
64     {
65         return false;
66     }
67     return stackA.stackPop(key);
68 }
69 
70 template<class T>
71 bool CQueue<T>::queueEmpty(void)
72 {
73     return stackA.stackEmpty();
74 }
75 
76 template<class T>
77 bool CQueue<T>::queueFull(void)
78 {
79     return stackA.stackFull();
80 }
81 
82 template<class T>
83 void CQueue<T>::queueClear(void)
84 {
85     stackA.stackClear();
86 }

附加一个stack的申明和实现：

 1 #ifndef _CSTACK_
 2 #define _CSTACK_
 3 
 4 template<class T> class CStack
 5 {
 6 public:
 7     CStack(int stackSize);
 8     ~CStack();
 9     bool stackPush(const T &key);
10     bool stackPop(T &key);
11     bool stackGetPop(T &key) const;    
12     void stackClear(void);
13     bool stackEmpty(void) const
14     {
15         return stackTop == 0;
16     };
17     bool stackFull(void) const
18     {
19         return stackTop == stackSize;
20     };
21 private:
22     T * stackArry;
23     int stackTop;
24     int stackSize;
25 };
26 
27 #endif

View Code

 1 #include "cstack.h"
 2 
 3 template<class T>  CStack<T>::CStack(int stackSize)
 4 {
 5     stackArry = new T[stackSize];
 6     this->stackSize = stackSize;
 7     this->stackTop  = 0;
 8 }
 9 
10 template<class T> CStack<T>::~CStack()
11 {
12     delete []stackArry;
13     stackSize = 0;
14     stackTop  = 0;
15 }
16 
17 template<class T> 
18 bool CStack<T>::stackPush(const T& key)
19 {
20     if(true == stackFull())
21     {
22         return false;
23     }
24     else
25     {
26         stackArry[stackTop++] = key;
27         return true;
28     }
29 }
30 
31 template<class T>
32 bool CStack<T>::stackPop(T &key)
33 {
34     if(true == stackEmpty())
35     {
36         return false;
37     }
38     else
39     {
40         key = stackArry[--stackTop];
41         return true;
42     }
43 }
44 
45 template<class T>
46 bool CStack<T>::stackGetPop(T &key) const
47 {
48     if(true == stackEmpty())
49     {
50         return false;
51     }
52     else
53     {
54         key = stackArry[top-1];
55         return true;
56     }
57 }
58 
59 template<class T>
60 void CStack<T>::stackClear(void)
61 {
62     stackTop = 0;
63 }

View Code