PTA - 堆栈模拟队列

设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。

所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:

int IsFull(Stack S)：判断堆栈S是否已满，返回1或0；
int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0；
void Push(Stack S, ElementType item )：将元素item压入堆栈S；
ElementType Pop(Stack S )：删除并返回S的栈顶元素。

实现队列的操作，即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。

输入格式:

输入首先给出两个正整数N1和N2，表示堆栈S1和S2的最大容量。随后给出一系列的队列操作：A item表示将item入列（这里假设item为整型数字）；D表示出队操作；T表示输入结束。

输出格式:

对输入中的每个D操作，输出相应出队的数字，或者错误信息ERROR:Empty。如果入队操作无法执行，也需要输出ERROR:Full。每个输出占1行。

输入样例:

3 2

A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T

输出样例:

ERROR:Full

1

ERROR:Full

2

3

4

7

8

ERROR:Empty

　　题目：给你两个有长度限制的栈，去模拟一个队列

　　思路分析：对于有长度限制的，栈中所能存放的数的个数最多是短的栈的个数的二倍，模拟下就好了

　　代码示例：

#define ll long long

const int maxn = 1e6+5;

const double pi = acos(-1.0);

const int inf = 0x3f3f3f3f;

stack<int>a,b;

int cnt = 0;

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    int n, m, num;

    char s[5]; 

    cin >> n >> m;

    if (n < m) swap(n, m);

    int pt = 0;

    while(1){

        scanf("%s", s);

        if (s[0] == 'T') break;

        else if (s[0] == 'A') {

            scanf("%d", &num);

            if (a.size() == m) {printf("ERROR:Full\n"); continue;}

            a.push(num);

        }

        else {

            if (b.empty() && a.empty()) {printf("ERROR:Empty\n"); continue;}

            if (!b.empty()) {printf("%d\n", b.top()); b.pop();}

            else {

                while(!a.empty()){

                    int v = a.top();

                    a.pop();

                    b.push(v);

                }

                printf("%d\n", b.top());

                b.pop();

                while(!b.empty()){

                    int v = b.top();

                    b.pop();

                    a.push(v);

                }

            }

        }

        if (a.size() == m) {

            if (b.empty()) {

                while(!a.empty()){

                    int v = a.top();

                    a.pop();

                    b.push(v);

                }

            }

        }

    }

    return 0;

}

巴特西

PTA - 堆栈模拟队列

输入格式:

输出格式:

输入样例:

输出样例:

最新文章

热门文章