<算法编程> 两个栈实现一个队列

 1 #include<iostream>
 2 using namespace std;
 3 
 4 typedef struct Node
 5 {
 6     int num;
 7     Node* pNext;
 8 }Stack,Queue;
 9 
10 //栈的入栈相当于 链表的头插
11 Stack* stack_push(Stack** pTop,int num)
12 {
13     Stack* pNode = (Stack*)malloc(sizeof(Stack));
14     pNode->num = num;
15     pNode->pNext = NULL;
16 
17     pNode->pNext = *pTop;
18     *pTop = pNode;
19     
20     return *pTop;
21 }
22 
23 int stack_pop(Stack** pTop)
24 {
25     if((*pTop) == NULL) return -1;
26 
27     Stack* pPop = *pTop;
28     int num = pPop->num;
29     
30     *pTop = (*pTop)->pNext;
31     free(pPop);
32     pPop = NULL;
33     
34     return num;
35 }
36 
37 void PrintStack(Stack* pTop)
38 {
39     cout << "当前栈顶元素为：" << pTop->num << endl;
40 }
41 
42 //队列的进栈
43 Queue* queue_push(Stack** pTop1,Stack** pTop2,int num)
44 {
45     //首先判断 栈2中有没有元素 如果有 全部压回栈1中
46     if((*pTop2) != NULL)
47     {
48         while((*pTop2) != NULL)
49         {
50             stack_push(pTop1,stack_pop(pTop2));
51         }
52     }
53 
54     //现有元素已经全部在栈1中 或栈1为空
55     //直接压栈
56     stack_push(pTop1,num);
57 
58     return (Queue*)pTop1;
59 }
60 
61 int queue_pop(Stack** pTop1,Stack** pTop2)
62 {
63     //判断栈1中有没有元素 如果有 就把栈1中的所有元素都压入栈2后弹出
64     if((*pTop1) != NULL)
65     {
66         while((*pTop1) != NULL)
67         {
68             stack_push(pTop2,stack_pop(pTop1));
69         }
70     }
71 
72     return stack_pop(pTop2);
73 }
74 
75 int main()
76 {
77     Stack* pTop1 = NULL; //用来进栈的
78     Stack* pTop2 = NULL; //用来出栈的
79     /*stack_push(&pTop,1);
80     stack_push(&pTop,2);
81     stack_push(&pTop,3);
82     stack_push(&pTop,4);
83     PrintStack(pTop);
84     cout << "弹出栈顶元素：" << stack_pop(&pTop) << endl;
85     cout << "弹出栈顶元素：" << stack_pop(&pTop) << endl;
86     cout << "弹出栈顶元素：" << stack_pop(&pTop) << endl;
87     cout << "弹出栈顶元素：" << stack_pop(&pTop) << endl;
88     cout << "弹出栈顶元素：" << stack_pop(&pTop) << endl;*/
89     queue_push(&pTop1,&pTop2,1);
90     queue_push(&pTop1,&pTop2,2);
91     queue_push(&pTop1,&pTop2,3);
92     queue_push(&pTop1,&pTop2,4);
93     queue_pop(&pTop1,&pTop2);
94     queue_pop(&pTop1,&pTop2);
95 
96     system("pause");
97     return 0;
98 }