精华内容
下载资源
问答
  • 堆栈模拟队列

    2020-11-12 16:08:06
    3-9 堆栈模拟队列 (20分) 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int ...

    3-9 堆栈模拟队列 (20分)

    设已知有两个堆栈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

    思路

    栈的特点是先进后出,而队列的特点是先进先出,所以两个栈可以一个做输入,另一个做输出:S1做输入,当S1不满就可以输入,如果满了就可以将其按序放入S2(前提是S2为空,如果不空,那么应该先输出的就被压在了栈底,那就是满了);S2做输出,当S2不为空就可以输出,如果空就要看一看S1中是否有元素,如果有就将其按序放入S2,否则为空。

    代码

    #include<iostream>
    #include<algorithm>
    #include<stack>
    using namespace std;
    int main(){
    	int N1,N2;
    	stack<int> s1,s2;
    	char op;
        int x;
    	cin>>N1>>N2;
        if(N1>N2){
            int n=N1;
            N1=N2;
            N2=n;
        }
    	cin>>op;
    	while(op!='T'){
    		if(op=='A'){
    			cin>>x;
                if(s1.size()!=N1){
                    s1.push(x);
                }else if(s1.size()==N1&&s2.size()==0){
                    while(!s1.empty()){
                        s2.push(s1.top());
                        s1.pop();
                    }
                    s1.push(x);
                }else if(s1.size()==N1&&s2.size()!=0){
                    printf("ERROR:Full\n");
                }
    		}else if(op=='D'){
    			if(!s2.size()==0){
                    printf("%d\n",s2.top());
                    s2.pop();
                }else if(s2.size()==0&&s1.size()!=0){
                    while(!s1.empty()){
                        s2.push(s1.top());
                        s1.pop();
                    }
                    printf("%d\n",s2.top());
                    s2.pop();
                }else if(s2.size()==0&&s1.size()==0){
                    printf("ERROR:Empty\n");
                }
    		}
    		cin>>op;
    	}
        return 0;
    } 
    
    展开全文
  • PTA 堆栈模拟队列

    2020-10-15 17:21:11
    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType item ...

    设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。
    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数:

    1. int IsFull(Stack S):判断堆栈S是否已满,返回1或0;
    2. int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0;
    3. void Push(Stack S, ElementType item ):将元素item压入堆栈S;
    4. ElementType Pop(Stack S ):删除并返回S的栈顶元素。
      实现队列的操作,即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。
      我偷懒直接用的stack IsFull用了size代替。

    输入格式:
    输入首先给出两个正整数N1和N2,表示堆栈S1和S2的最大容量。随后给出一系列的队列操作:A item表示将item入列(这里假设item为整型数字);D表示出队操作;T表示输入结束。
    输入案例

    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
    

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

    ERROR:Full
    1
    ERROR:Full
    2
    3
    4
    7
    8
    ERROR:Empty
    

    算法描述:
    首先选择**小的栈用于入队
    大的栈用于出队
    **
    在这里插入图片描述

    #include<bits/stdc++.h>
    using namespace std;
    stack <int> a,b;
    int main()
    {
        int maxa,maxb,x;
        string s;
        scanf("%d %d",&maxa,&maxb);
        if(maxa>maxb)
        {
            maxa=maxb;
        }
        while(cin>>s,s!="T")
        {
            if(s=="A")
            {
                cin>>x;
                if(a.empty() || (int)a.size()<maxa)
                {
                    a.push(x);
                }
                else
                {
                    if(b.empty())
                    {
                        while(!a.empty())
                        {
                            b.push(a.top());
                            a.pop();
                        }
                        a.push(x);
                    }
                    else
                    {
                        cout<<"ERROR:Full"<<'\n';
                    }
                }
            }
            else if(s=="D")
            {
                if(b.empty())
                {
                    if(a.empty())
                    {
                        cout<<"ERROR:Empty"<<'\n';
                    }
                    else
                    {
                        while(!a.empty())
                        {
                            b.push(a.top());
                            a.pop();
                        }
                        cout<<b.top()<<'\n';
                        b.pop();
                    }
                }
                else
                {
                    cout<<b.top()<<'\n';
                    b.pop();
                }
            }
        }
        return 0;
    }
    
    
    展开全文
  • C语言堆栈模拟队列

    2020-05-17 11:39:04
    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType item )...

    设已知有两个堆栈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

    思路:
    1.输入两个栈的大小,让1栈为小的那一个 。
    2.输入时:

    1. s1没满,s2为空,输入到s1中。

    2. s1满了,s2为空,将s1中的数据倒入s2中,再输入到s1中。

    3. s1满了,s2不为空,输出ERROR:Full。

    3.输出时:

    1. s2不是空的,直接输出s2.top()。

    2. s2是空的,s1不是空的,将s1中的元素倒入s2中,再输出s2.top()。

    3. s2是空的,s1也是空的,输出ERROR:Empty。

    #include <stdio.h>//函数库。
    
    int n1,n2,d,temp;//n1是较小的那个栈,n2是较大的那个栈。
    char s[2];//定义一个字符数组,大小为2的原因是字符数组后还要存放\0。
    int s1[1000],s2[1000],c1=0,c2=0;//定义两个稍微大一点栈,因为后面会有限制条件,所以不用担心死循环,c1是较小的那个栈的栈顶元素,c2是n2较大的那个栈的栈顶元素;
    
    int main()//主函数。
     {
    	scanf("%d%d",&n1,&n2);//n1为较小的那个栈的大小,n2为较大的那个栈的大小。
    	
    	if(n1 > n2) //反正就是要让n1为较小的那个栈的大小,n2为较大的那个栈的大小。
    	{
    		temp=n1;
    		n1=n2;
    		n2=temp;
    	}
    	
    	while(scanf("%s",s) && s[0] != 'T') //先输入一个操作,判断是否是结束操作。
    	{
    		if(s[0] == 'A') //如果是A那么说明要入s1栈了,但要判断是否满了。
    		{
    			scanf("%d",&d);
    			if(c1 == n1)
    			{
    				printf("ERROR:Full\n");
    			}
    			else 
    			{
    				s1[c1 ++] = d;
    			}
    		}
    		
    		else //如果是D操作,执行下列操作。
    		{
    			if(c2) //如果s2有元素,先输入s2中的元素。
    			{
    		      printf("%d\n",s2[-- c2]);
    			}
    			else if(c1)//判断s1中是否有元素,如果有执行下列操作。
    			{
    				while(c1) //把s1中元素倒进s2中,输出s2中元素。
    				{
    					s2[c2 ++] = s1[-- c1];
    				}
    				printf("%d\n",s2[-- c2]);
    			}
    			else //如果s1和s2都没有元素,输出空。
    			{
    				printf("ERROR:Empty\n");
    			}
    		}
    		
    		if(!c2 && c1 == n1) //当s2为空,s1满,就s1中元素倒进s2中。
    		{
    			while(c1) 
    			{
    				s2[c2 ++] = s1[-- c1];
    			}
    			
    		}
    	}
    	return 0;
    }
    

    需要注意的是while循环中,只有全部输入完毕后才打印结果,也就是说当while退出循环后才打印全部结果。对于这道题来讲,只有遇到了T然后才退出循环,打印所有结果。不然之前的输入是一直输入的。

    展开全文
  • 基础实验3-2.5 堆栈模拟队列PTA练习题 PTA练习题 基础实验3-2.5 堆栈模拟队列 (25 分) 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int ...

    PTA练习题

    基础实验3-2.5 堆栈模拟队列 (25 分)
    设已知有两个堆栈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

    这题是要我们用一大一小两个堆栈模拟队列,我这里用的是堆栈链式存储模拟队列,用堆栈的顺序存储同样能实现,代码有注释。

    // An highlighted block
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct SNode *Stack;
    struct SNode{
        int data;
        int top;
        struct SNode *next;
    };
    Stack Create();
    int IsEmpty(Stack s);
    void Push(int item, Stack s);
    int Pop(Stack s);
    int Top(Stack s);
    void exchange(Stack s1,Stack s2);
    int main()
    {
        int num1,num2,n1,n2;
        scanf("%d%d",&num1,&num2);
        if(num1>num2){
            n1=num2;
            n2=num1;
        }
        else{n1=num1;n2=num2;}
        Stack s1,s2;
        s1=Create();
        s2=Create();
        //s1作为容量小的堆栈,s2作大的堆栈
        char c;
        int n;
        scanf("%c",&c);
        while(c!='T'){
            if(c=='D'){
                if(IsEmpty(s2)==0){
                    printf("%d\n",Pop(s2));
                }
            else if(IsEmpty(s1)==1&&IsEmpty(s2)==1) printf("ERROR:Empty\n");
            else{
                while(IsEmpty(s1)==0){
                    exchange(s1,s2);
                }
                printf("%d\n",Pop(s2));
            }
        }
            if(c=='A'){
                scanf("%d",&n);
                    if(Top(s1)==n1){
                        if(IsEmpty(s2)==1){ //s1满,s2空,把s1一个个放到s2里
                            while(IsEmpty(s1)==0){
                                exchange(s1,s2);
                            }
                            Push(n,s1);
                        }
                        else printf("ERROR:Full\n");
                    }
                    else Push(n,s1);
                }
                scanf("%c",&c);
            }
            return 0;
    }
    Stack Create(){
        //创建一个空堆栈s
        Stack s;
        s=(Stack)malloc(sizeof(struct SNode));
        s->top=0;
        s->next=NULL;
        return s;
    }
    int IsEmpty(Stack s){
        //判断堆栈是否为空,空则返回1,不空返回0
        return (s->next==NULL);
    }
    void Push(int item, Stack s){
        //把item压入堆栈顶
        struct SNode *tmpcell;
        tmpcell=(struct SNode *)malloc(sizeof(struct SNode));
        if(s->next==NULL){tmpcell->top=1;}
        else {
            int i=s->next->top;
            tmpcell->top=++i;
        }
        tmpcell->next=s->next;
        s->next=tmpcell;
        tmpcell->data=item;
    }
    int Pop(Stack s){
        //删除并返回被删掉的栈顶元素data
        Stack firstcell;
        int n;
            firstcell=s->next;
            s->next=firstcell->next;
            n=firstcell->data;
            return n;
    }
    int Top(Stack s){
        //返回栈顶top
        if(s->next!=NULL) return (s->next->top);
        else return s->top;
    }
    void exchange(Stack s1,Stack s2){
    	//把s1栈顶元素放到s2
        Stack cup,p;
        cup=(Stack)malloc(sizeof(struct SNode));
        p=(Stack)malloc(sizeof(struct SNode));
        cup=s1->next;
        s1->next=cup->next;
        cup->next=NULL;
        if(s2->next==NULL) s2->next=cup;
        else{
            p=s2->next;
            cup->next=p;
            s2->next=cup;
        }
    }
    

    在这里插入图片描述

    展开全文
  • 算法题 堆栈模拟队列

    2020-03-04 16:41:25
    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType item )...
  • 7-22 堆栈模拟队列(25 分)设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数:int IsFull(Stack S):判断堆栈S是否已满,返回1或0;int ...
  • 堆栈模拟队列 (25分)

    2020-09-29 22:02:59
    堆栈模拟队列 (25分) 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty ...
  • PTA 7-22 堆栈模拟队列

    2020-06-07 14:37:32
    7-22 堆栈模拟队列 (25分) 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int ...
  • 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType ...
  • 7-22 堆栈模拟队列

    2018-02-23 23:34:00
    7-22 堆栈模拟队列(25 分) 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0...
  • 7-6 堆栈模拟队列

    2020-06-21 10:44:42
    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType item )...
  • 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType item )...
  • PTA-7-22 堆栈模拟队列

    2020-04-03 20:46:28
    本题考点:采用堆栈模拟队列 文章目录解题思路情况分析代码实现 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):...
  • PTA - 堆栈模拟队列

    2018-03-27 13:08:00
    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType ...
  • PTA练习题:堆栈模拟队列

    千次阅读 2020-05-16 12:23:17
    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType item )...
  • 堆栈模拟队列(c++)

    2021-04-05 21:39:30
    堆栈模拟队列题目答案参考 题目 答案 #include<iostream> #include<algorithm> #include<stack> using namespace std; int main() { stack<int> a; stack<int> b; int maxa,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 659
精华内容 263
热门标签
关键字:

堆栈模拟队列