【数据结构】用两个栈实现队列

用两个栈实现队列：

栈无法实现队列功能：栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。
双栈可实现列表倒序：设有含三个元素的栈 A = [1,2,3] 和空栈 B = []。若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A = [] , B = [3,2,1]，即栈 B 元素实现栈 A 元素倒序。
利用栈 B 删除队首元素：倒序后，B 执行出栈则相当于删除了 A 的栈底元素，即对应队首元素。

代码实现：

  1 typedef struct st_queue {
  2     T_Stack *s1;
  3     T_Stack *s2;
  4 }T_Queue; 
  5 
  6 int QueueInit( T_Queue *queue, T_Stack *s1, T_Stack *s2 )
  7 {
  8     queue->s1 = s1;
  9     queue->s2 = s2;
 10     return 0;
 11 }
 12 
 13 int QueueAppend( T_Queue *queue, int val )
 14 {
 15     int tmp;
 16 
 17 #if 0
 18     if( StackIsFull( queue->s1) ) // StackA满，如果StackB不是空的话，则不能把A转移到B，则认为队列已经满了；
 19     {
 20         if( !StackIsEmpty( queue->s2 ) )
 21         {
 22             return -1;
 23         }
 24 
 25         // B没满，A没空，则不断地把A转到B
 26         while( !StackIsFull( queue->s2 ) && !StackIsEmpty( queue->s1 ))
 27         {
 28             if( StackPop( queue->s1, &tmp ) != 0 )
 29             {
 30                 return -2;
 31             }
 32             StackPush( queue->s2, tmp );
 33         }
 34     }
 35 #endif
 36 
 37     if( StackIsFull( queue->s1) ) 
 38     {
 39         return -3;
 40     }
 41 
 42     if( StackPush( queue->s1, val ) != 0 )
 43     {
 44         return -4;
 45     }
 46 
 47     return 0;
 48 }
 49 
 50 int QueueDelete( T_Queue *queue, int *val )
 51 {
 52     int tmp;
 53 
 54     // 1.当B不为空，则B中仍有已完成倒叙的元素，因此直接返回B的栈顶元素
 55     if( !StackIsEmpty( queue->s2 ) )
 56     {
 57         if( StackPop( queue->s2, &tmp ) != 0)
 58         {
 59             return -1;
 60         }
 61         *val = tmp;
 62         return 0;
 63     }
 64 
 65     // 2.当A也为空，则两个栈都为空，无元素，因此返回-1
 66     if( StackIsEmpty( queue->s1 ) )
 67     {
 68         return -2;
 69     }
 70 
 71     // 3.将A元素全部转移至栈B中，实现元素倒叙，并返回栈B的栈顶元素
 72     while( !StackIsEmpty( queue->s1) && !StackIsFull( queue->s2 ) )
 73     {
 74         StackPop( queue->s1, &tmp );
 75         StackPush( queue->s2, tmp );
 76     }
 77 
 78     if( !StackIsEmpty( queue->s1) ) // 如果A没有完全转移，则还是错误的
 79     {
 80         return -3;
 81     }
 82 
 83     StackPop( queue->s2, &tmp );
 84 
 85     *val = tmp;
 86 
 87     return 0;
 88 }
 89 
 90 #define MAX_SIZE        ( 100 )
 91 
 92 int test_stack_02( void )
 93 {
 94     int *data1;
 95     int *data2;
 96     T_Stack *s1;
 97     T_Stack *s2;
 98     T_Queue *queue;
 99     int i;
100     int ret;
101     int val;
102 
103     data1 = (int *)malloc( sizeof(int) * MAX_SIZE );
104     data2 = (int *)malloc( sizeof(int) * MAX_SIZE );
105 
106     s1 = ( T_Stack * )malloc( sizeof(T_Stack));
107     s2 = ( T_Stack * )malloc( sizeof(T_Stack));
108 
109     queue = (T_Queue *)malloc( sizeof(T_Queue));
110 
111     StackInit( s1, data1, MAX_SIZE );
112     StackInit( s2, data2, MAX_SIZE );
113 
114     QueueInit( queue, s1, s2 );
115 
116     for( i = 0; i < MAX_SIZE; i++ )
117     {
118         ret = QueueAppend( queue, i );
119         printf("QueueAppend(%d), ret:%d
", i, ret);
120     }
121 
122     for( i = 0; i < MAX_SIZE; i++ )
123     {
124         ret = QueueDelete( queue, &val );
125         printf("QueueDelete(%d), ret:%d, val:%d
", i, ret, val);
126     }
127 
128     free( data1 );
129     free( data2 );
130     free( s1 );
131     free( s2 );
132     free( queue );
133 
134     return 0;
135 }

参考引用：

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/