开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

数据结构——循环队列PTA习题

简介: 数据结构——循环队列PTA习题
+关注继续查看

单选题


image


题解


初始化创建空队列时,令front=rear=0,每当插入新的队列尾元素时,rear增1,每当删除一个队列首元素时,front增1。因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置。


front :0+2=2,


rear 4+2=6——>0.


函数题


6-1 另类循环队列 (20分)


如果用一个循环数组表示队列,并且只设队列头指针Front,不设尾指针Rear,而是另设Count记录队列中元素个数。请编写算法实现队列的入队和出队操作。


函数接口定义:


bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );


其中Queue结构定义如下:


typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;  /* 存储元素的数组   */
    Position Front;     /* 队列的头指针     */
    int Count;          /* 队列中元素个数   */
    int MaxSize;        /* 队列最大容量     */
};
typedef PtrToQNode Queue; 


注意:如果队列已满,AddQ函数必须输出“Queue Full”并且返回false;如果队列是空的,则DeleteQ函数必须输出“Queue Empty”,并且返回ERROR。


输入样例:


4
Del
Add 5
Add 4
Add 3
Del
Del
Add 2
Add 1
Add 0
Add 10
End


输出样例:


Queue Empty
5 is out
4 is out
Queue Full
3 2 1 0


代码



#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElementType;
typedef enum { addq, delq, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;  /* 存储元素的数组   */
    Position Front;     /* 队列的头、尾指针 */
    int Count;          /* 队列中元素个数   */
    int MaxSize;        /* 队列最大容量     */
};
typedef PtrToQNode Queue; 

Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = 0;
    Q->Count = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );

Operation GetOp();  /* 裁判实现,细节不表 */

int main()
{
    ElementType X;
    Queue Q;
    int N, done = 0;

    scanf("%d", &N);
    Q = CreateQueue(N);
    while ( !done ) {
        switch( GetOp() ) {
        case addq: 
            scanf("%d", &X);
            AddQ(Q, X);
            break;
        case delq:
            X = DeleteQ(Q);
            if ( X!=ERROR ) printf("%d is out\n", X);
            break;
        case end:
            while (Q->Count) printf("%d ", DeleteQ(Q));
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代码将被嵌在这里 */
bool AddQ(Queue Q, ElementType X)
{
    if (Q->MaxSize==Q->Count)
    {
        printf("Queue Full\n");
        return ERROR;
    }
    ++Q->Count;
    Q->Data[(Q->Front + Q->Count) % Q->MaxSize] = X;
    return true;

}
ElementType DeleteQ(Queue Q)
{
    if (Q->Count==0)
    {
        printf("Queue Empty\n");
        return ERROR;
    }
    --Q->Count;
    Q->Front = (Q->Front + 1) % Q->MaxSize;
    return Q->Data[Q->Front];

}


6-2 双端队列 (25分)


双端队列(deque,即double-ended queue的缩写)是一种具有队列和栈性质的数据结构,即可以(也只能)在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列,请编写例程实现下列操作:


Push(X,D):将元素X插入到双端队列D的头;


Pop(D):删除双端队列D的头元素,并返回;


Inject(X,D):将元素X插入到双端队列D的尾部;


Eject(D):删除双端队列D的尾部元素,并返回。


函数接口定义:


bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );


其中Deque结构定义如下:


typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;      /* 存储元素的数组   */
    Position Front, Rear;   /* 队列的头、尾指针 */
    int MaxSize;            /* 队列最大容量     */
};
typedef PtrToQNode Deque; 


注意:Push和Inject应该在正常执行完操作后返回true,或者在出现非正常情况时返回false。当Front和Rear相等时队列为空,Pop和Eject必须返回由裁判程序定义的ERROR。


输入样例:


3
Pop
Inject 1
Pop
Eject
Push 2
Push 3
Eject
Inject 4
Inject 5
Inject 6
Push 7
Pop
End


输出样例:


Deque is Empty!
1 is out
Deque is Empty!
2 is out
Deque is Full!
Deque is Full!
3 is out
Inside Deque: 4 5


代码


#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, inject, eject, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;      /* 存储元素的数组   */
    Position Front, Rear;   /* 队列的头、尾指针 */
    int MaxSize;            /* 队列最大容量     */
};
typedef PtrToQNode Deque; 

Deque CreateDeque( int MaxSize )
{   /* 注意:为区分空队列和满队列,需要多开辟一个空间 */
    Deque D = (Deque)malloc(sizeof(struct QNode));
    MaxSize++;
    D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    D->Front = D->Rear = 0;
    D->MaxSize = MaxSize;
    return D;
}

bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

Operation GetOp();          /* 裁判实现,细节不表 */
void PrintDeque( Deque D ); /* 裁判实现,细节不表 */

int main()
{
    ElementType X;
    Deque D;
    int N, done = 0;

    scanf("%d", &N);
    D = CreateDeque(N);
    while (!done) {
        switch(GetOp()) {
        case push: 
            scanf("%d", &X);
            if (!Push(X, D)) printf("Deque is Full!\n");
            break;
        case pop:
            X = Pop(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            else printf("%d is out\n", X);
            break;
        case inject: 
            scanf("%d", &X);
            if (!Inject(X, D)) printf("Deque is Full!\n");
            break;
        case eject:
            X = Eject(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            else printf("%d is out\n", X);
            break;
        case end:
            PrintDeque(D);
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代码将被嵌在这里 */

// 头插
bool Push(ElementType X, Deque D)
{
    // 算尾部位置,如果满了返回false
    if ((D->Rear + 1) % (D->MaxSize) == D->Front)
        return false;
    // 减完了才能用公式
    D->Front--;
    D->Front = (D->MaxSize + D->Front) % (D->MaxSize);
    D->Data[D->Front] = X;
    return true;
}

// 头删
ElementType Pop(Deque D)
{
    if (D->Front == D->Rear)
        return ERROR;
    ElementType d = D->Data[D->Front];
    D->Front++;
    D->Front = D->Front % (D->MaxSize);
    return d;
}

// 尾插
bool Inject(ElementType X, Deque D)
{
    // 算尾部位置,如果满了返回false
    if ((D->Rear + 1) % (D->MaxSize) == D->Front)
        return false;
    D->Data[D->Rear] = X;
    D->Rear = (D->Rear + 1) % D->MaxSize;
    return true;
}

// 尾删
ElementType Eject(Deque D)
{
    if (D->Front == D->Rear)
        return ERROR;
    if (!D->Rear)
        D->Rear = D->MaxSize;
    D->Rear--;
    ElementType d = D->Data[D->Rear];
    return d;
}


编程题


7-1 堆栈模拟队列 (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


代码


模拟队列


#include<stdio.h>
#include<iostream>
#include<stack>
#include<string>

using namespace std;
stack<int>s1, s2;   //定义两个栈
int n1, n2;         //两个栈的容量

int main()
{
    char c;
    int m, p, q;
    cin >> n1 >> n2;
    if (n1 > n2) 
        swap(n1, n2);  // 保证更大的容量的S2作为输出栈
    getchar();
    while (1) 
    {     
        // 无限循环输入
        cin >> c;
        if (c == 'T') 
            break;     // 输入字符为T时结束
        if (c == 'A') 
        {
            cin >> m;
            if (s1.size() == n1 && s2.size() != 0)   // 只有当s1为满,s2不为空时才是满的情况
                printf("ERROR:Full\n");
            else if (s1.size() == n1 && s2.size() == 0) 
            {   
                // 当s1为满,s2为空时,先将s1里面所有的元素转移到s2,再将新加入的元素放置s1
                q = n1;
                while (q--) 
                {
                    p = s1.top();
                    s1.pop();
                    s2.push(p);
                }
                s1.push(m);
            }
            else if (s1.size() != n1)  // 若s1不满,可直接将新入的元素放置s1里面
                s1.push(m);;
        }
        if (c == 'D') 
        {   
            //输入字符为D时要出队
            if (s1.size() == 0 && s2.size() == 0)    //只有当s1,s2均为空时才为队空的情况
                printf("ERROR:Empty\n");
            else if (s1.size() != 0 && s2.size() == 0)
            {  
                //若s2为空,s1不空,则先把s1里面所有元素转移至s2,再输出s2的栈顶元素
                q = s1.size();
                while (q--) {
                    p = s1.top();
                    s1.pop();
                    s2.push(p);
                }
                cout << s2.top() << endl;
                s2.pop();
            }
            else if (s2.size() != 0) 
            { 
                //如果s2不为空,可直接输出s2栈顶元素
                cout << s2.top() << endl;
                s2.pop();
            }
        }
    }
    return 0;
}



直接用queue


#include<bits/stdc++.h> 
using namespace std;
queue<int> q; 
  
int main()
{  
    int m,n,i,a;  
    char c;  
    cin>>m>>n;  
    n+=m;   
    for(i=0;;i++)
    {  
        cin>>c;  
        if(c=='T')  
            return 0;
        if(c=='A')
        {  
            cin>>a;  
            if(q.size()==n)
            {
                cout<<"ERROR:Full"<<endl;  
            }  
            else
            {  
                q.push(a);  
            }  
        }  
        else if(c=='D')
        {  
            if(q.size()==0)
            {  
                cout<<"ERROR:Empty"<<endl;  
            }  
            else
            {  
                cout<<q.front()<<endl;  
                q.pop();   
            }  
        }  
    }  
    return 0;  
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构——堆PTA习题
数据结构——堆PTA习题
10 0
Java数据结构--稀疏数组和队列(一)
Java数据结构--稀疏数组和队列(一)
30 0
Java数据结构--稀疏数组和队列(二)
Java数据结构--稀疏数组和队列(二)
27 0
【数据结构】——拿捏 栈和队列2
【数据结构】——拿捏 栈和队列2
17 0
< 数据结构 > 队列的实现
目录 前言 队列的概念 队列的结构 队列的应用场景 队列的实现 创建队列结构 队列初始化 队列销毁 入队列 出队列 队列判空 获取队列元素个数 获取队列头部元素 获取队列尾部元素 总代码 Queue.h 文件 Queue.c 文件 Test.c 文件
43 0
【化解数据结构】详解队列,优先队列,循环队列,并实现一个队列
【化解数据结构】详解队列,优先队列,循环队列,并实现一个队列
27 0
数据结构——队列
1 队列是一种只允许在表的一端插入元素,在另一端删除元素的特殊的线性表。允许插入的一端成为队尾(rear),允许删除的一端成为队头(front)。当队列中没有任何元素时成为空队列。队列是一种先进先出的线性表,简称FIFO表。 2 与栈类似,队列也是一种操作受限的特殊的线性表,同样可以采用顺序存储结构和链式存储结构来表示队列。 3 队列的顺序存储表示——循环队列 队列的顺序存储表示同样
992 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载