7-22 堆栈模拟队列 (25分)

没注意看题，一开始把元素类型弄成char了，搞了好久都AC不了，换成int一次就AC了。

题意：

即用两个栈来模拟队列，使两个栈协作实现队列的功能。

思路：

1.第一个栈为输入栈，第二个栈为输出栈，输入栈比输出栈要小。

2.栈满条件：输入栈满了而输出栈不为空，说明栈满了，因为输出栈还有元素的话，输入栈的元素是不能搬到输出栈的，这样会造成顺序混乱（输出栈为空时连续多次将对个输入栈栈顶元素搬到输出栈这一情况除外）。

3.所以说，输入栈的元素要搬到栈顶只能在一种条件下：就是输出栈为空时，且输入栈元素必须一次性地全部搬到输出栈。

此外出栈入栈函数的传入参数要用指针型，刚开始没注意，就出错了。

  1 #include <iostream>
  2 #include <string>
  3 #include <cstring>
  4 using namespace std;
  6 typedef int ElementType;
  7 struct Stack
  8 {
  9     int* s;
 10     int max_;
 11     int r;
 12 };
 13 int IsFull(Stack* S)
 14 {
 15     if (S->r == S->max_ - 1)
 16     {
 17 
 18         return 1;
 19     }
 20     else return 0;
 21 }
 22 int IsEmpty(Stack* S)
 23 {
 24     if (S->r == -1)
 25     {
 26         return 1;
 27     }
 28     else return 0;
 29 }
 30 void Push(Stack* S, ElementType item)
 31 {
 32     if (!IsFull(S))
 33     {
 34         S->s[++(S->r)] = item;
 35     }
 36     else return;
 37 }
 38 ElementType Pop(Stack* S)
 39 {
 40     return S->s[(S->r)--];
 41 }
 42 int main()
 43 {
 44     int n1, n2;
 45     Stack* s1=new Stack, *s2=new Stack;
 46     s1->r = -1;
 47     s2->r = -1;
 48     cin >> n1 >> n2;
 49     if (n2 > n1)
 50     {
 51         s1->max_ = n1;
 52         s1->s = new int[n1];
 53         s2->max_ = n2;
 54         s2->s = new int[n2];
 55     }
 56     else
 57     {
 58         s1->max_ = n2;
 59         s1->s = new int[n2];
 60         s2->max_ = n1;
 61         s2->s = new int[n1];
 62     }
 63     while (1)
 64     {
 65         char ch;
 66         cin >> ch;
 67         if (ch == 'T')
 68             break;
 69         else if (ch == 'A')
 70         {
 71             int n;
 72             cin >> n;
 73             if (IsFull(s1))
 74             {
 75                 if (!IsEmpty(s2))
 76                     cout << "ERROR:Full" << endl;
 77                 else
 78                 {
 79                     while (!IsEmpty(s1) && !IsFull(s2))
 80                     {
 81                         Push(s2, Pop(s1));
 82                     }
 83                     Push(s1, n);
 84                 }
 85             }
 86             else
 87                 Push(s1, n);
 88         }
 89         else if (ch == 'D')
 90         {
 91             if (IsEmpty(s2) && IsEmpty(s1))
 92             {
 93                 cout << "ERROR:Empty" << endl;
 94             }
 95             else if (!IsEmpty(s2) && !IsEmpty(s1))
 96             {
 97                 cout << Pop(s2) << endl;
 98             }
 99             else if(IsEmpty(s1))
100             {
101                 cout << Pop(s2) << endl;
102             }        
103             else if (IsEmpty(s2))
104             {
105                 while(!IsEmpty(s1) && !IsFull(s2))
106                 {
107                     Push(s2, Pop(s1));
108                 }     
109                 cout << Pop(s2) << endl;
110               
111             }
112         }
113     }
114 
115     return 0;
116 }