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

单纯的用线性表或者单链表实现队列已经不足为奇，现在给大家介绍个有特色的，用两个栈实现队列。

 如图

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

l 创建队列

l 销毁队列

l 清空队列

l 入队

l 出队

l 返回队首元素

l 返回队的大小

代码总分为三个文件：

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

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

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

整体结构图为：

这里详细说下入队操作，出队操作和返回队首元素操作：

入队操作：

如图：

  

出队操作：

如图：

 

返回队首元素：

如图：

OK! 上代码：

SQueue.h ：

 

[cpp] view plain copy

1. #ifndef _SQUEUE_H_  
2. #define _SQUEUE_H_  
3.   
4. typedef void SQueue;  
5.   
6. SQueue* SQueue_Create();  
7.   
8. void SQueue_Destroy(SQueue* queue);  
9.   
10. void SQueue_Clear(SQueue* queue);  
11.   
12. int SQueue_Append(SQueue* queue, void* item);  
13.   
14. void* SQueue_Retrieve(SQueue* queue);  
15.   
16. void* SQueue_Header(SQueue* queue);  
17.   
18. int SQueue_Length(SQueue* queue);  
19.   
20. #endif  

 

SQueue.c ： 

[cpp] view plain copy

1. #include <stdio.h>  
2. #include <malloc.h>  
3. #include “LinkStack.h”  
4. #include “SQueue.h”  
5.   
6. typedef struct _tag_SQueue  
7. {  
8.     LinkStack* inStack;  
9.     LinkStack* outStack;  
10. }TSQueue;  
11.   
12. SQueue* SQueue_Create()  
13. {  
14.     TSQueue* ret = (TSQueue*)malloc(sizeof(TSQueue));  
15.       
16.     if(NULL != ret)  
17.     {  
18.         ret->inStack  = LinkStack_Create();  
19.         ret->outStack = LinkStack_Create();  
20.           
21.         if((NULL == ret->inStack) || (NULL == ret->outStack))  
22.         {  
23.             LinkStack_Destroy(ret->inStack);  
24.             LinkStack_Destroy(ret->outStack);  
25.               
26.             free(ret);  
27.             ret = NULL;  
28.         }  
29.     }  
30.       
31.     return ret;  
32. }  
33.   
34. void SQueue_Destroy(SQueue* queue)  
35. {  
36.     SQueue_Clear(queue);  
37.       
38.     free(queue);  
39. }  
40.   
41. void SQueue_Clear(SQueue* queue)  
42. {  
43.     TSQueue* sQueue = (TSQueue*)queue;  
44.       
45.     if(NULL != sQueue)  
46.     {  
47.         LinkStack_Clear(sQueue->inStack);  
48.         LinkStack_Clear(sQueue->outStack);  
49.     }  
50. }  
51.   
52. int SQueue_Append(SQueue* queue, void* item)  
53. {  
54.     TSQueue* sQueue = (TSQueue*)queue;  
55.       
56.     int ret = 0;  
57.       
58.     if(NULL != sQueue)  
59.     {  
60.         ret = LinkStack_Push(sQueue->inStack, item);  
61.     }  
62.       
63.     return ret;  
64. }  
65.   
66. void* SQueue_Retrieve(SQueue* queue)  
67. {  
68.     TSQueue* sQueue = (TSQueue*)queue;  
69.       
70.     void* ret = NULL;  
71.       
72.     if(NULL != sQueue)  
73.     {  
74.         if(0 == LinkStack_Size(sQueue->outStack))  
75.         {  
76.             while(0 < LinkStack_Size(sQueue->inStack))  
77.             {  
78.                 LinkStack_Push(sQueue->outStack, LinkStack_Pop(sQueue->inStack));  
79.             }  
80.         }  
81.           
82.         ret = LinkStack_Pop(sQueue->outStack);  
83.     }  
84.       
85.     return ret;  
86. }  
87.   
88. void* SQueue_Header(SQueue* queue)  
89. {  
90.     TSQueue* sQueue = (TSQueue*)queue;  
91.       
92.     void* ret = NULL;  
93.       
94.     if((NULL != sQueue) && (0 < SQueue_Length(queue)))  
95.     {  
96.         if(0 == LinkStack_Size(sQueue->outStack))  
97.         {  
98.             while(0 < LinkStack_Size(sQueue->inStack))  
99.             {  
100.                 LinkStack_Push(sQueue->outStack, LinkStack_Pop(sQueue->inStack));  
101.             }         
102.         }  
103.           
104.         ret = LinkStack_Top(sQueue->outStack);  
105.     }  
106.       
107.     return ret;  
108. }  
109.   
110. int SQueue_Length(SQueue* queue)  
111. {  
112.     TSQueue* sQueue = (TSQueue*)queue;  
113.       
114.     int ret = -1;  
115.       
116.     if(NULL != sQueue)  
117.     {  
118.         ret = LinkStack_Size(sQueue->inStack) +   
119.               LinkStack_Size(sQueue->outStack);  
120.     }  
121.       
122.     return ret;  
123. }  

 

Main.c     ：

[cpp] view plain copy

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include “SQueue.h”  
4.   
5. int main(void)  
6. {  
7.     SQueue* queue = SQueue_Create();  
8.       
9.     int a[10];  
10.     int i = 0;  
11.       
12.     for(i=0; i<10; i++)  
13.     {  
14.         a[i] = i+1;  
15.           
16.         SQueue_Append(queue, a+i);  
17.     }  
18.     printf(”Length:  %d\n”, SQueue_Length(queue));  
19.     printf(”Header:  %d\n”, *(int*)SQueue_Header(queue));  
20.   
21.       
22.     for(i=0; i<5; i++)  
23.     {  
24.         printf(”Retrieve:  %d\n”, *(int*)SQueue_Retrieve(queue));         
25.     }  
26.       
27.     printf(”Header:  %d\n”, *(int*)SQueue_Header(queue));  
28.     printf(”Length:  %d\n”, SQueue_Length(queue));  
29.       
30.     for(i=0; i<10; i++)  
31.     {  
32.         a[i] = i+1;  
33.           
34.         SQueue_Append(queue, a+i);  
35.     }  
36.       
37.     while(SQueue_Length(queue) > 0)  
38.     {  
39.         printf(”Retrieve:  %d\n”, *(int*)SQueue_Retrieve(queue));  
40.     }  
41.       
42.     SQueue_Destroy(queue);  
43.   
44.     return 0;  
45. }