数据结构（栈--两个队列实现）

       当看到用两个栈实现队列以后，大家有没有兴趣用两个队列实现一个栈呢，呵呵！现在就来介绍用两个队列实现一个栈。

      

       如图

这里介绍队列的常用操作：

l 创建栈

l 销毁栈

l 清空栈

l 压栈

l 出栈

l 返回栈顶元素

l 返回栈的大小

代码总分为三个文件：

QStack.h ： 放置功能函数的声明，以及表的声明 

QStack.c ： 放置功能函数的定义，以及表的定义

Main.c   ： 主函数，使用功能函数完成各种需求，一般用作测试

整体结构图为：

 

这里详细说下压栈操作，出栈操作和返回栈顶元素操作：

 

压栈操作：

[cpp] view plain copy

1. int QStack_Push(QStack* stack, void* item)  
2. {  
3.     TQStack* aStack = (TQStack*)stack;  
4.       
5.     int ret = (NULL!=aStack) && (NULL!=item);  
6.       
7.     if(ret)  
8.     {  
9.         if(0 == LinkQueue_Length(aStack->queue_A))  
10.         {  
11.             ret = LinkQueue_Append(aStack->queue_B, item);     
12.         }  
13.         else  
14.         {  
15.             ret = LinkQueue_Append(aStack->queue_A, item);  
16.         }  
17.           
18.     }  
19.       
20.     return ret;  
21. }  

如图：

  

出栈操作：

[cpp] view plain copy

1. void* QStack_Pop(QStack* stack)  
2. {  
3.     TQStack* aStack = (TQStack*)stack;  
4.       
5.     void* ret = NULL;  
6.       
7.     if((NULL!=aStack) && (0<QStack_Length(aStack)))  
8.     {  
9.         if(0 == LinkQueue_Length(aStack->queue_B))  
10.         {  
11.             while(LinkQueue_Length(aStack->queue_A) > 1)  
12.             {  
13.                 LinkQueue_Append(aStack->queue_B, LinkQueue_Retrieve(aStack->queue_A));  
14.             }  
15.               
16.             ret = LinkQueue_Retrieve(aStack->queue_A);  
17.         }  
18.         else   
19.         {  
20.             while(LinkQueue_Length(aStack->queue_B) > 1)  
21.             {  
22.                 LinkQueue_Append(aStack->queue_A, LinkQueue_Retrieve(aStack->queue_B));  
23.             }  
24.               
25.             ret = LinkQueue_Retrieve(aStack->queue_B);  
26.         }  
27.     }  
28.       
29.     return ret;  
30. }  

如图：

返回栈顶元素：

[cpp] view plain copy

1. void* QStack_Top(QStack* stack)  
2. {  
3.     TQStack* aStack = (TQStack*)stack;  
4.       
5.     void* ret = NULL;  
6.       
7.     if((NULL!=aStack) && (0<QStack_Length(stack)))  
8.     {  
9.         if(0 == LinkQueue_Length(aStack->queue_B))  
10.         {  
11.             while(LinkQueue_Length(aStack->queue_A) > 1)  
12.             {  
13.                 LinkQueue_Append(aStack->queue_B, LinkQueue_Retrieve(aStack->queue_A));  
14.             }  
15.               
16.             ret = LinkQueue_Header(aStack->queue_A);  
17.             LinkQueue_Append(aStack->queue_B, LinkQueue_Retrieve(aStack->queue_A));  
18.         }  
19.         else  
20.         {  
21.             while(LinkQueue_Length(aStack->queue_B) > 1)  
22.             {  
23.                 LinkQueue_Append(aStack->queue_A, LinkQueue_Retrieve(aStack->queue_B));  
24.             }  
25.               
26.             ret = LinkQueue_Header(aStack->queue_B);  
27.             LinkQueue_Append(aStack->queue_A, LinkQueue_Retrieve(aStack->queue_B));  
28.         }  
29.     }  
30.       
31.     return ret;  
32. }  

如图：

            

OK! 上代码：

QStack.h ： 

[cpp] view plain copy

1. #ifndef _QSTACK_H_  
2. #define _QSTACK_H_  
3.   
4. typedef void QStack;  
5.   
6. QStack* QStack_Create();  
7.   
8. void QStack_Destroy(QStack* stack);  
9.   
10. void QStack_Clear(QStack* stack);  
11.   
12. int QStack_Push(QStack* stack, void* item);  
13.   
14. void* QStack_Pop(QStack* stack);  
15.   
16. void* QStack_Top(QStack* stack);  
17.   
18. int QStack_Length(QStack* stack);  
19.   
20. #endif  

 

QStack.c ：

 

[cpp] view plain copy

1. #include <malloc.h>  
2. #include "LinkQueue.h"  
3. #include "QStack.h"  
4.   
5. typedef struct _tag_QStack  
6. {  
7.     LinkQueue* queue_A;  
8.     LinkQueue* queue_B;  
9. }TQStack;  
10.   
11. QStack* QStack_Create()  
12. {  
13.     TQStack* ret = (TQStack*)malloc(sizeof(TQStack));  
14.       
15.     if(NULL != ret)  
16.     {  
17.         ret->queue_A = LinkQueue_Create();  
18.         ret->queue_B = LinkQueue_Create();  
19.           
20.         if((NULL==ret->queue_A) || (NULL==ret->queue_B))  
21.         {  
22.             LinkQueue_Destroy(ret->queue_A);  
23.             LinkQueue_Destroy(ret->queue_B);  
24.               
25.             free(ret);  
26.             ret = NULL;  
27.         }  
28.     }  
29.       
30.     return ret;  
31. }  
32.   
33. void QStack_Destroy(QStack* stack)  
34. {  
35.     QStack_Clear(stack);  
36.       
37.     free(stack);      
38. }  
39.   
40. void QStack_Clear(QStack* stack)  
41. {  
42.     while(QStack_Length(stack) > 0)  
43.     {  
44.         QStack_Pop(stack);  
45.     }  
46. }  
47.   
48. int QStack_Push(QStack* stack, void* item)  
49. {  
50.     TQStack* aStack = (TQStack*)stack;  
51.       
52.     int ret = (NULL!=aStack) && (NULL!=item);  
53.       
54.     if(ret)  
55.     {  
56.         if(0 == LinkQueue_Length(aStack->queue_A))  
57.         {  
58.             ret = LinkQueue_Append(aStack->queue_B, item);     
59.         }  
60.         else  
61.         {  
62.             ret = LinkQueue_Append(aStack->queue_A, item);  
63.         }  
64.           
65.     }  
66.       
67.     return ret;  
68. }  
69.   
70. void* QStack_Pop(QStack* stack)  
71. {  
72.     TQStack* aStack = (TQStack*)stack;  
73.       
74.     void* ret = NULL;  
75.       
76.     if((NULL!=aStack) && (0<QStack_Length(aStack)))  
77.     {  
78.         if(0 == LinkQueue_Length(aStack->queue_B))  
79.         {  
80.             while(LinkQueue_Length(aStack->queue_A) > 1)  
81.             {  
82.                 LinkQueue_Append(aStack->queue_B, LinkQueue_Retrieve(aStack->queue_A));  
83.             }  
84.               
85.             ret = LinkQueue_Retrieve(aStack->queue_A);  
86.         }  
87.         else   
88.         {  
89.             while(LinkQueue_Length(aStack->queue_B) > 1)  
90.             {  
91.                 LinkQueue_Append(aStack->queue_A, LinkQueue_Retrieve(aStack->queue_B));  
92.             }  
93.               
94.             ret = LinkQueue_Retrieve(aStack->queue_B);  
95.         }  
96.     }  
97.       
98.     return ret;  
99. }  
100.   
101. void* QStack_Top(QStack* stack)  
102. {  
103.     TQStack* aStack = (TQStack*)stack;  
104.       
105.     void* ret = NULL;  
106.       
107.     if((NULL!=aStack) && (0<QStack_Length(stack)))  
108.     {  
109.         if(0 == LinkQueue_Length(aStack->queue_B))  
110.         {  
111.             while(LinkQueue_Length(aStack->queue_A) > 1)  
112.             {  
113.                 LinkQueue_Append(aStack->queue_B, LinkQueue_Retrieve(aStack->queue_A));  
114.             }  
115.               
116.             ret = LinkQueue_Header(aStack->queue_A);  
117.             LinkQueue_Append(aStack->queue_B, LinkQueue_Retrieve(aStack->queue_A));  
118.         }  
119.         else  
120.         {  
121.             while(LinkQueue_Length(aStack->queue_B) > 1)  
122.             {  
123.                 LinkQueue_Append(aStack->queue_A, LinkQueue_Retrieve(aStack->queue_B));  
124.             }  
125.               
126.             ret = LinkQueue_Header(aStack->queue_B);  
127.             LinkQueue_Append(aStack->queue_A, LinkQueue_Retrieve(aStack->queue_B));  
128.         }  
129.     }  
130.       
131.     return ret;  
132. }  
133.   
134. int QStack_Length(QStack* stack)  
135. {  
136.     TQStack* aStack = (TQStack*)stack;  
137.       
138.     int ret = -1;  
139.       
140.     if(NULL != aStack)  
141.     {  
142.         ret = LinkQueue_Length(aStack->queue_B) +  
143.               LinkQueue_Length(aStack->queue_A);  
144.     }  
145.       
146.     return ret;  
147. }  

 

Main.c     ：