栈 队列

目录

1.1栈的基本概念

1.1.1栈的定义

1.1.2栈的基本操作

 1.2栈的顺序存储结构

1.2.1构造原理

 1.2.2基本算法

1.3栈的链式存储结构

1.3.1构造原理

1.3.2基本算法

2.1队列的基本概念

2.1.1队列的定义

 2.1.2队列的基本运算

 2.2队列的顺序存储结构

2.2.1构造原理

2.2.1基本算法

 2.3队列的链式存储结构

2.3.1构造原理

 2.3.2基本算法

3.1例题

判断题

单选题

函数题

另类堆栈

用顺序栈实现将非负的十进制数转换为指定的进制数 

 简单表达式求值

另类循环队列

编程题

 括号匹配

栈操作的合法性 


1.1栈的基本概念

1.1.1栈的定义

栈:限定仅在表尾进行插入操作和删除操作的线性表

栈顶:表尾,允许操作的一端

栈底:表头,不允许操作

空栈:当表没有元素时

先进后出 FILO(Frist In Last Out) 

1.1.2栈的基本操作

初始化栈:将栈S置为一个空栈(不含任何元素)

入栈 :将元素插入到栈中,又称为压栈或进栈

出栈:删除栈顶元素,又称为退栈

取栈顶元素:取出栈顶元素

判断栈是否为空:若为空返回真,否则返回假

判断栈是否为满:若为空返回真,否则返回假

 1.2栈的顺序存储结构

1.2.1构造原理

描述栈的顺序储存结构最简单的方法是利用一维数组data[0…M-1]来表示,同时定义一个整型变量(不妨取名top)给出栈顶元素的位置。

#define M (1000+5)

typedef char ElemType;

typedef struct{

    ElemType data[M];

    int top;    //初始top=-1

}SqStack;

 1.2.2基本算法

初始化栈

void init(SqStack *s){
    s->top=-1;
}

测试栈是否为空

int isEmpty(SqStack s){
    return s.top==-1;
}

测试栈是否已满

int isFull(SqStack s){
    return s.top==M-1;
}

入栈

int push(SqStack *s,ElemType item){
    if(isFull(*s)) return 0;
    else{
        s->data[++(s->top)]=item;
        return 1;
    }
}

出栈

int pop(SqStack *s,ElemType *item){
    if(isEmpty(*s)) return 0;
    else{
        *item=s->data[(s->top)--];
        return 1;
    }
}

1.3栈的链式存储结构

1.3.1构造原理

typedef struct node{

    ElemType data;

    struct node *next;

}SNode,*LinkStack;

LinkStack top;    //栈顶指针

1.3.2基本算法

栈初始化

void init(LinkStack *top){
    *top=NULL;
}

 测试栈是否为空

int isEmpty(LinkStack top){
    return top==NULL;
}

入栈

int push(LinkStack *top,ElemType item){
    LinkStack p=(LinkStack)malloc(sizeof(SNode));
    if(p==NULL) return 0;
    else{
        p->data=item;
        p->next=*top;
        *top=p;
        return 1;
    }
}

出栈

int pop(LinkStack *top,ELemType *item){
    LinkStack p;
    if(isEmpty(*top)) return 0;
    else{
        p=*top;
        *item=(*top)->data;
        *top=(*top)->next;
        free(p);
        return 1;
    }
}

2.1队列的基本概念

2.1.1队列的定义

队列简称队。是一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。允许插入的一段称为队尾,队尾元素的位置由rear指出;允许删除的一端称为队头,队头元素的位置由front指出。

先进先出 FIFO(Frist In First Out) 

 2.1.2队列的基本运算

初始化队列:将队列q设置成一个空队列

入队列:将元素x插入到队尾中,也称“进队”,“插入”

入队列:将队列q的队头元素删除,并用x返回其值,也称“退队”,“删除”

取队头元素:得到队列q队头元素之值,并用x返回其值

判队空:判断队列q是否为空,若空返回1,否则返回0

 2.2队列的顺序存储结构

2.2.1构造原理

在实际程序设计过程中,通常借助一个一维数组data[0…M-1]来描述队列的顺序储存结构,同时,设置两个变量front与rear分别指出当前队头元素与队尾元素的位置。

#define M  (1000+5)

typedef struct{

    ElemType data[M];

    int front,rear;

}SqQueue;

2.2.1基本算法

初始化队列

void init(SqQueue *q){
    q->front=q->rear=0;
}

测试队列是否为空

int isEmpty(SqQueue q){
    return q.front==q->rear;
}

测试队列是否已满

int isFull(SqQueue q){
    return q->rear==M;
}

入队

int push(SqQueue *q,ElemType item){
    if(q->rear==M) return 0;
    else{
        q->data[q->rear]=item;
        q->rear++;
        return 1;
    }
}

出队

int pop(SqQueue *q,ElemType *item){
    if(isEmpty(*q)) return 0;
    else{
        *item=q->data[q->front];
        q->front++;
        return 1;
    }
}

 2.3队列的链式存储结构

2.3.1构造原理

队列的链式储存结构是一个用线性链表表示一个队列,指针front与rear分别指向实际队头元素与实际队尾元素的位置。

 typedef stuct node{

    ElemType data;

    stuct node *next;

}QNode,*QLink;

typedef stuct {

    QLink front;

    QLink rear;

}LinkQueue;

 2.3.2基本算法

初始化队列

void init(LinkQueue *q){
    q->front=(QLink)malloc(sizeof(QNode));
    q->front->next=NULL;
    q->rear=q->front;
}

测试队列是否为空

int isEmpty(LinkQueue q){
    return q->front->next==NULL;
}

销毁一个队列

void delQueue(QLink *front,QLink *rear){
    while(*front){   //队列非空时
        rear=front->next;
        free(front);
        front=rear;
    }
}

3.1例题

判断题

1-1 在用数组表示的循环队列中,front值一定小于等于rear值。

1-2 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为:123。

1-3 若一个栈的输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。

1-4 队列是一种插入和删除操作分别在表的两端进行的线性表,是一种先进后出的结构。

1-5 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。

1-6 若一个栈的输入序列为1,2,3,…,N,输出序列的第一个元素是i,则第j个输出元素是j−i−1。

1-7 栈顶元素和栈底元素有可能是冋一个元素。

1-8 "Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array.

1-9 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。

1-10 循环队列也存在着空间溢出问题。

1-11 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。

1-12 若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志,则在设置一个空队时只需将队首指针和队尾指针赋同一个值,不管什么值都可以。

单选题

2-1

设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4,则最后一个出栈的元素必定是:

A.1

B.3

C.5

D.1或者5

2-2

表达式a*(b+c)-d的后缀表达式是:

A.a b c + * d -

B.a b c d * + -

C.a b c * + d -

D.- + * a b c d

2-3

线性表、堆栈、队列的主要区别是什么?

A.线性表用指针,堆栈和队列用数组

B.堆栈和队列都是插入、删除受到约束的线性表

C.线性表和队列都可以用循环链表实现,但堆栈不能

D.堆栈和队列都不是线性结构,而线性表是

2-4

top为指向栈顶元素的指针,判定栈S(最多容纳m个元素)为空的条件是:

A.S->top == 0

B.S->top == -1

C.S->top != m-1

D.S->top == m-1

2-5

如果循环队列用大小为m的数组表示,队头位置为front、队列元素个数为size,那么队尾元素位置rear为:

A.front+size

B.front+size-1

C.(front+size)%m

D.(front+size-1)%m

2-6

假设有5个整数以1、2、3、4、5的顺序被压入堆栈,且出栈顺序为3、5、4、2、1,那么为了获得这样的输出,堆栈大小至少为:

A.2

B.3

C.4

D.5

2-7

若已知一队列用单向链表表示,该单向链表的当前状态(含3个对象)是:1->2->3,其中x->y表示x的下一节点是y。此时,如果将对象4入队,然后队列头的对象出队,则单向链表的状态是:

A.1->2->3

B.2->3->4

C.4->1->2

D.答案不唯一

2-8

若用大小为6的数组来实现循环队列,且当前frontrear的值分别为0和4。当从队列中删除两个元素,再加入两个元素后,frontrear的值分别为多少?

A.2和0

B.2和2

C.2和4

D.2和6

2-9

若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是?

A.b c a e f d

B.c b d a e f

C.d c e b f a

D.a f e d c b

2-10

有六个元素以6、5、4、3、2、1的顺序进栈,问哪个不是合法的出栈序列?

A.2 3 4 1 5 6

B.3 4 6 5 2 1

C.5 4 3 6 1 2

D.4 5 3 1 2 6

2-11

若一个栈的入栈序列为1、2、3、…、N,输出序列的第一个元素是i,则第j个输出元素是:

A.i−j−1

B.i−j

C.j−i−1

D.不确定

2-12

将5个字母ooops按此顺序入栈,则有多少种不同的出栈顺序可以仍然得到ooops

A.1

B.3

C.5

D.6

2-13

给定一个堆栈的入栈序列为{ 1, 2, ⋯, n },出栈序列为{ p1​, p2​, ⋯, pn​ }。如果p2​=n,则存在多少种不同的出栈序列?

A.1

B.2

C.n−1

D.n

2-14

以下不是栈的基本运算的是( )。

A.删除栈顶元素

B.删除栈底元素

C.判断栈是否为空

D.将栈置为空栈

2-15

一个递归的定义可以用递归过程求解,也可以用非递归过程求解,但单从运行时间来看, 通常递归过程比非递归过程( )。

A.较快

B.较慢

C.相同

D.无法确定

2-16

设顺序栈的栈顶指针(int 类型)指向栈顶元素位置,则判断一个栈ST(最多元素为MaxSize)为栈满的条件是()。

A.ST.top != -1

B.ST.top == -1

C.ST.top != MaxSize - 1

D.ST.top == MaxSize - 1

2-17

假设一个栈的输入序列是1,2,3,4,则不可能得到的输出序列是( )。

A.1,2,3,4

B.4,1,2,3

C.4,3,2,1

D.1,3,4,2

2-18

设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4,则最后一个出栈的元素必定是____。

A.1

B.3

C.5

D.1或者5

2-19

为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是?

A.堆栈

B.队列

C.树

D.图

2-20

某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作,则不可能得到的出队序列是:

A.b a c d e

B.d b a c e

C.e c b a d

D.d b c a e

2-21

如果循环队列用大小为m的数组表示,且用队头指针front和队列元素个数size代替一般循环队列中的frontrear指针来表示队列的范围,那么这样的循环队列可以容纳的元素个数最多为:

A.m-1

B.m

C.m+1

D.不能确定

2-22

在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( )。

A.f->next=s; f=s;

B.r->next=s; r=s;

C.s->next=s; r=s;

D.s->next=f; f=s;

2-23

循环顺序队列中是否可以插入下一个元素()。

A.与队头指针和队尾指针的值有关

B.只与队尾指针的值有关,与队头指针的值无关

C.只与数组大小有关,与队首指针和队尾指针的值无关

D.与曾经进行过多少次插入操作有关

2-24

现有队列 Q 与栈 S,初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }(1在队头),S 为空。若允许下列3种操作:(1)出队并输出出队元素;(2)出队并将出队元素入栈;(3)出栈并输出出栈元素,则不能得到的输出序列是:

A.1, 2, 5, 6, 4, 3

B.2, 3, 4, 5, 6, 1

C.3, 4, 5, 6, 1, 2

D.6, 5, 4, 3, 2, 1

2-25

若用一个大小为6的数组来实现循环队列,且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。

A.1和5

B.2和4

C.4和2

D.5和1

2-26

设一数列的顺序为1,2,3,4,5,6,通过队列操作可以得到( )的输出序列。

A.3,2,5,6,4,1

B.1,2,3,4,5,6

C.6,5,4,3,2,1

D.4,5,3,2,6,1

2-27

判断一个循环队列QU(最多元素为MaxSize)为空的条件是()。

A.QU.front == QU.rear

B.QU.front != QU.rear

C.QU.front == (QU.rear + 1) % MaxSize

D.QU.front != (QU.rear + 1) % MaxSize

2-2

用单链表表示的链队的队头在链表的()位置。

A.链头

B.链尾

C.链中

D.均可以

2-29

关于栈和队列的下列说法正确的是()

A.栈的插入操作是在栈顶进行,插入时需将栈内所有元素后移;

B.栈是后进先出的结构,出栈时除了栈顶元素,其余元素无需移动;

C.循环队列的出队操作删除的是队头元素,采用循环队列存储时,其余队列元素均需要移动;

D.链队列的入队操作在表尾进行,操作时间与队列长度成正比

2-30

最不适合用作链队的链表是()。

A.只带队头指针的非循环双链表

B.只带队头指针的循环双链表

C.只带队尾指针的循环双链表

D.只带队尾指针的循环单链表

2-31

下列关于栈的叙述中,错误的是:

  1. 采用非递归方式重写递归程序时必须使用栈
  2. 函数调用时,系统要用栈保存必要的信息
  3. 只要确定了入栈次序,即可确定出栈次序
  4. 栈是一种受限的线性表,允许在其两端进行操作

A.仅 1

B.仅 1、2、3

C.仅 1、3、4

D.仅 2、3、4

2-32

假设栈初始为空,将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中,当扫描到f时,栈中的元素依次是( )。

A.+(*-

B.+(-*

C./+(*-*

D./+-*

2-33

已知程序如下:。

int S(int n)
{ return (n<=0)?0:s(n-1)+n;}
void main()
{
 count<<S(1);
}

程序运行时使用栈来保存调用过程的信息,自栈底到栈顶保存的信息依次对应的是( )

A.main()→S(1)→S(0)

B.S(0)→S(1)→main()

C.main()→S(0)→S(1)

D. S(1)→S(0)→main()

函数题
另类堆栈

在栈的顺序存储实现中,另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满?

函数接口定义:

bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );

其中Stack结构定义如下:

typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType *Data;  /* 存储元素的数组 */
    Position Top;       /* 栈顶指针       */
    int MaxSize;        /* 堆栈最大容量   */
};
typedef PtrToSNode Stack;

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

裁判测试程序样例:

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

#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType *Data;  /* 存储元素的数组 */
    Position Top;       /* 栈顶指针       */
    int MaxSize;        /* 堆栈最大容量   */
};
typedef PtrToSNode Stack;

Stack CreateStack( int MaxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = 0;
    S->MaxSize = MaxSize;
    return S;
}

bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );

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

int main()
{
    ElementType X;
    Stack S;
    int N, done = 0;

    scanf("%d", &N);
    S = CreateStack(N);
    while ( !done ) {
        switch( GetOp() ) {
        case push: 
            scanf("%d", &X);
            Push(S, X);
            break;
        case pop:
            X = Pop(S);
            if ( X!=ERROR ) printf("%d is out\n", X);
            break;
        case end:
            PrintStack(S);
            done = 1;
            break;
        }
    }
    return 0;
}

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

输入样例:

4
Pop
Push 5
Push 4
Push 3
Pop
Pop
Push 2
Push 1
Push 0
Push 10
End

输出样例:

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

 代码

bool Push( Stack S, ElementType X ){
    if(S->Top>=S->MaxSize){   
//Top定义为栈顶的上一个位置,此刻通过判断Top是否>=MaxSize判断表满
        printf("Stack Full\n");
        return false;
    }
    S->Data[S->Top++]=X;
    return ture;
}
ElementType Pop( Stack S ){
    if(S->Top) return S->Data[--S->Top];
    else{
        printf("Stack Empty\n");
        return ERROR;
    }
}
用顺序栈实现将非负的十进制数转换为指定的进制数 

利用顺序栈将输入的非负的十进制数N转换为指定的d(二、八或十六)进制数。

顺序栈的定义如下:

#define STACKSIZE  100  
typedef int DataType; 
typedef struct
{      
   DataType items[STACKSIZE];     /*存放栈中元素的一维数组*/
   int top;                    /*用来存放栈顶元素的下标*/
}SqStack;

函数接口定义:

int DecimalConvert(SqStack *s, int dec, int scale);

函数参数说明:形参--sdecscale,其中,s是存放转换后的scale进制数的各位数字,dec 主函数输入的待转换的十进制数,scale是指定的数制(只能是2、8或16)。 函数返回值:1,表示函数执行完成;0,表示函数未成功执行。

裁判测试程序样例:

#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE  100  
typedef int DataType;
typedef struct
{
    DataType items[STACKSIZE];   /*存放栈中元素的一维数组*/
    int top;                     /*用来存放栈顶元素的下标*/
}SqStack;
int InitSqStack(SqStack* S)
{ // 初始化顺序栈
    S->top = -1;
    return 1;
}
int SqStackPush(SqStack* S, DataType e)
{ // 压栈函数
    if (S->top == STACKSIZE - 1)
        return 0;     /*栈已满*/
    S->top++;
    S->items[S->top] = e;

    return 1;
}
int SqStackPop(SqStack* S, DataType* e)
{ /* 将栈S的栈顶元素弹出,放到e所指的存储空间中 */
    if (S->top == -1)     /* 栈为空 */
        return 0;
    *e = S->items[S->top];     /* 将栈顶元素带回来 */
    S->top--;                    /* 修改栈顶指针 */

    return 1;
}
int SqStackEmpty(SqStack S)
{  /* S为顺序栈 */
    if (S.top == -1)
        return 1;
    else
        return 0;
}
/* 本题要求函数 */
int DecimalConvert(SqStack* s, int dec, int scale);

int main()
{
    SqStack s;
    char ch[] = "0123456789ABCDEF";  //二、八、十六进制所使用的数字
    unsigned dec, scale;
    DataType tmp;
    InitSqStack(&s);
    scanf("%d %d", &dec, &scale); // 某些编译器要求此处改为scanf_s
    if (DecimalConvert(&s, dec, scale))
    {
        printf("十进制数:%d,转换为:%d进制数,结果为:", dec, scale);
        while (!SqStackEmpty(s))
        {
            SqStackPop(&s, &tmp);
            printf("%c", ch[tmp]);
        }
    }
    else
        printf("数制转换未成功!");
    return 0;
}
/* 请在这里填写答案 */

输入样例:

20 2

输出样例:

十进制数:20,转换为:2进制数,结果为:10100

输入样例:

20 8

输出样例:

十进制数:20,转换为:8进制数,结果为:24

输入样例:

20 16

输出样例:

十进制数:20,转换为:16进制数,结果为:14

代码 

int DecimalConvert(SqStack *s, int dec, int scale){
    if(dec<0) return 0;
    while(dec){
        int r=dec%scale      
//裁判测试中有将>9的数转换成字母,所以我们只需要求出余数即可
        SqStackPush(s,r);   //压入栈s中
        dec/=scale;
    }
    return 1;
}
 简单表达式求值

本题要求实现两个整数的运算,运算符仅有四种:+、-、* 、/ ,但是以字符串的形式输入表达式。注意这里的除数结果是整数,即5/4=1。

函数接口定义:

int cal( char a[] );

其中 a是用户传入的参数,此处为表达式,表达式。

裁判测试程序样例:

#include <stdio.h>
int cal( char s[] );
int main()
{
    char a[100];
    int res;
    scanf("%s",a);
    
    res=cal(a);
    
    printf("%d",res);

    return 0;

}
/* 请在这里填写答案 */

输入样例:

123+12=

输出样例:

135

代码

#include<math.h>
int cal(char *s){
    int count1=0,count2=0,num=0;
    int c[100],d[100],c1=0,d1=0,aaa=0,i;
    while(s[num++]);
    num--;                         //计算字符串长度
    for(int i=0;i<num;i++){        //第一个数字每一位存数组
        if(s[i]>='0'&&s[i]<='9')   //保证数字
            c[count1++]=s[i]-'0';
        else
            break;
    }
    for(int i=count1+1;i<num;i++){ //第二个数字每一位存数组
        if(s[i]>='0'&&s[i]<='9')
            d[count2++]=s[i]-'0';
        else
            break;
    }
    for(int i=count1-1;i>=0;i--){    //把数组转成数字
        c1+=c[i]*pow(10,count1-i-1);
    }
    for(int i=count2-1;i>=0;i--){
        d1+=d[i]*pow(10,count2-i-1);
    }
    switch(s[count1]){              //加减乘除四个操作
        case '+':aaa=c1+d1;break;
        case '-':aaa=c1-d1;break;
        case '*':aaa=c1*d1;break;
        case '/':aaa=c1/d1;break;
    }
    return aaa;
}
另类循环队列

如果用一个循环数组表示队列,并且只设队列头指针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。

裁判测试程序样例:

 

#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;
}

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

输入样例:

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 

代码

bool AddQ( Queue Q, ElementType X ){
    if(Q->Count>=Q->MaxSize){
        printf("Queue Full\n");
        return false;
    }
    Q->Data[(Q->Front+Q->Count)%Q->MaxSize]=X;  //注意Q是循环队列
    Q->Count++;
    return true;
}
ElementType DeleteQ( Queue Q ){
    if(Q->Count==0){
        printf("Queue Empty\n");
        return ERROR;
    }
    ElementType X=Q->Data[Q->Front];    //队列先进的先出
    Q->Front=(Q->Front+1)%Q->MaxSize;
    Q->Count--;
    return X;

}
编程题
 括号匹配

给定一串字符,不超过100个字符,可能包括括号、数字、字母、标点符号、空格,编程检查这一串字符中的( ) ,[ ],{ }是否匹配。

输入格式:

输入在一行中给出一行字符串,不超过100个字符,可能包括括号、数字、字母、标点符号、空格。

输出格式:

如果括号配对,输出yes,否则输出no。

输入样例1:

sin(10+20)

输出样例1:

yes

输入样例2:

{[}]

输出样例2:

no

代码

#include<stdio.h>
int main(){
    char s1[120],s2[120];
    int s2l,flag=1;
    gets(s1);
    for(int i=0;s1[i]!='\0';i++){         //字符串中包含空格
        if(s1[i]=='('||s1[i]=='['||s1[i]=='{'){
            s2[s2l++]=s1[i];
        }
        else if(s1[i]==')'){
            if(s2l<1||s2[s2l]!='('){
                flag=0;
                break;
            }
            s2l--;
        }
        else if(s1[i]==']'){
            if(s2l<1||s2[s2l]!='['){
                flag=0;
                break;
            }
            s2l--;
        }
        else if(s1[i]=='}'){
            if(s2l<1||s2[s2l]!='}'){
                flag=0;
                break;
            }
            s2l--;
        }
    }
    if(flag==0||index!=0) printf("no");
    else printf("yes");
    return 0;
}
栈操作的合法性 

假设以SX分别表示入栈和出栈操作。如果根据一个仅由SX构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写程序,输入SX序列,判断该序列是否合法。

输入格式:

输入第一行给出两个正整数 n 和 m,其中 n 是待测序列的个数,m(≤50)是堆栈的最大容量。随后 n 行,每行中给出一个仅由SX构成的序列。序列保证不为空,且长度不超过100。

输出格式:

对每个序列,在一行中输出YES如果该序列是合法的堆栈操作序列,或NO如果不是。

输入样例:

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例:

YES
NO
NO
NO

 代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    char str[120];
    while(n--){
        cin>>str;
        int l=0;
        int flag=0;
        for(int j=0;j<strlen(str);j++){
            if(str[j]=='S') l++;
            else if(str[j]=='X') l--;
            else flag++;
            if(l>m||l<0) break;
        }
    if(l==0&&flag==0) cout<<"YES\n";
    else cout<<"NO\n";
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/651672.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++ | Leetcode C++题解之第115题不同的子序列

题目&#xff1a; 题解&#xff1a; class Solution { public:int numDistinct(string s, string t) {int m s.length(), n t.length();if (m < n) {return 0;}vector<vector<unsigned long long>> dp(m 1, vector<unsigned long long>(n 1));for (i…

通过Zerossl给IP申请免费SSL证书, 实现https ip访问

参考通过Zerossl给IP申请免费SSL证书 | LogDicthttps://www.logdict.com/archives/tong-guo-zerosslgei-ipshen-qing-mian-fei-sslzheng-shu

软件系统开发标准流程文档(Word原件)

目的&#xff1a;规范系统开发流程&#xff0c;提高系统开发效率。 立项申请需求分析方案设计方案评审开发调整测试阶段系统培训试运行测试验收投入使用 所有文档过去进主页获取。 软件项目相关全套精华资料包获取方式①&#xff1a;点我获取 获取方式②&#xff1a;本文末个人…

【cocos creator 】生成六边形地图

想要生成一个六边形组成的地图 完整代码示例 以下是完整的代码示例&#xff0c;包含了注释来解释每一步&#xff1a; cc.Class({extends: cc.Component,properties: {hexPrefab: {default: null,type: cc.Prefab},mapWidth: 10, // 网格的宽度&#xff08;六边形的数量&am…

(delphi11最新学习资料) Object Pascal 学习笔记---第13章第4节 (内存管理和接口)

13.4 内存管理和接口 ​ 在第11章中&#xff0c;我介绍了接口的内存管理的关键要素。与对象不同&#xff0c;接口是受管理且具有引用计数。如我所提到的&#xff0c;接口引用会增加所引用对象的引用计数&#xff0c;但您可以声明接口引用为弱引用以禁用引用计数&#xff08;但…

Prometheus Operator创建告警规则并接入钉钉报警

prometheus之钉钉报警 前言1. 添加prometheus报警规则1.2 添加自定义报警规则文件 2. 配置钉钉报警2.2 部署dingding插件 3. 编写alertmanager配置文件 前言 在kubenetes上安装了kube-promethues&#xff08;包含Prometheus Operator&#xff09;,程序正常跑起来了&#xff0c…

Transformer详解(4)-前馈层残差连接层归一化

1、前馈层 前馈层接收自注意力层的输出作为输入。 from torch import nn import torch.nn.functional as Fclass FeedForward(nn.Module):def __init__(self, d_model512, d_ff2048, dropout0.1):super().__init__()# d_ff 默认设置为2048self.linear_1 nn.Linear(d_model,…

Python | Leetcode Python题解之第115题不同的子序列

题目&#xff1a; 题解&#xff1a; class Solution:def numDistinct(self, s: str, t: str) -> int:m, n len(s), len(t)if m < n:return 0dp [[0] * (n 1) for _ in range(m 1)]for i in range(m 1):dp[i][n] 1for i in range(m - 1, -1, -1):for j in range(n …

自适应容积卡尔曼滤波|(自适应CKF)的MATLAB源代码

介绍 容积卡尔曼滤波在理论上拥有比UKF更高的精度和稳定性&#xff0c;本自适应算法通过对观测残差的计算&#xff0c;在观测协方差R不准确或无法获得时&#xff0c;对R进行调节&#xff0c;以起到降低估计误差的作用。 模型 使用的是三维的非线性模型&#xff0c;经过适当修…

计算机网络导论

网络结构的演变 网状结构 最开始的网络&#xff0c;主机之间都是两两相连 好处 这样连接&#xff0c;好处是安全性比较高&#xff08;A与B之间的连线断了&#xff0c;可以绕一下C&#xff09;&#xff1b; 另外通信不需要互相等待&#xff08;没有中间交换设备&#xff0c;所…

Vue3_创建项目

目录 一、创建vue项目 1.下载vue 2.进入刚才创建的项目 3.安装依赖 4.运行项目 ​5.打包项目放入生产环境 二、vue项目组成 1.项目文件结构 2.项目重要文件 Vue (发音为 /vjuː/&#xff0c;类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、C…

QQ名片满级会员展示生成HTML源码

源码介绍 QQ名片满级会员展示生成HTML源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c;保存素材去选择QQ个性名片-选择大图模板-把图上传照片墙即可 源码效果 源码下载 蓝奏云&#xff1a;http…

OrangePi Kunpeng Pro 开箱测评之一步到喂

前情提要&#xff1a;大家好&#xff0c;我是Samle。有幸接到 CSDN 发来的测评邀请&#xff0c;下面针对 OrangePi Kunpeng Pro 开发板进行一些实践操作&#xff0c;让大家能更好的上手这块板子。 以下内容来自 官方说明 OrangePi Kunpeng Pro采用4核64位处理器AI处理器&#…

【Linux-RTC】

Linux-RTC ■ rtc_device 结构体■ RTC 时间查看与设置■ 1、时间 RTC 查看■ 2、设置 RTC 时间 ■ rtc_device 结构体 Linux 内核将 RTC 设备抽象为 rtc_device 结构体 rtc_device 结构体&#xff0c;此结构体定义在 include/linux/rtc.h 文件中 ■ RTC 时间查看与设置 ■ 1…

SpringBoot 结合 WebSocket 实现聊天功能

目录 一、WebSocket 介绍 二、源码 2.1 pom.xml 2.2 WebSocket配置类&#xff0c;用于配置WebSocket的相关设置 2.3 自定义WebSocket处理器类&#xff0c;用于处理WebSocket的生命周期事件 2.4 自定义WebSocket握手拦截器&#xff0c;用于增强WebSocket的握手过程 2.5 Ses…

衍生品赛道的 UniSwap:SynFutures 或将成为行业领军者

经过一个周期的发展&#xff0c;DeFi 已经成为基于区块链构建的最成功的去中心化应用&#xff0c;并彻底改变了加密市场的格局。加密货币交易开始逐步从链下转移到链上&#xff0c;并从最初简单的 Swap 到涵盖借贷、Staking、衍生品交易等广泛的生态系统。 在 DeFi 领域&#x…

stream-并行流

定义 常规的流都是串行的流并行流就是并发的处理数据&#xff0c;一般要求被处理的数据互相不影响优点&#xff1a;数据多的时候速度更快&#xff0c;缺点&#xff1a;浪费系统资源&#xff0c;数据少的时候开启线程更耗费时间 模版 Stream<Integer> stream1 Stream.of…

《Ai企业知识库》-模型实践-rasa开源学习框架-搭建简易机器人-环境准备(针对windows)-02

rasa框架 Conversational AI Platform | Superior Customer Experiences Start Here 阿丹: 其实现在可以使用的ai的开发框架有很多很多&#xff0c;就需要根据各个模型的能力边界等来讨论和设计。 rasa整体流程以及每一步的作用 NLU(自然语言理解): 自然语言理解&#xff…

[docker] docker 安全知识 - 镜像,port registry

[docker] docker 安全知识 - 镜像&#xff0c;port & registry 这是第一篇&#xff0c;安全部分还有一篇笔记就记完了 说实话&#xff0c;看完了要学的这些东西&#xff0c;感觉大多数安全问题都可以通过验证登录的合法性去解决 镜像 镜像的问题还是比较多的&#xff0…

【学习记录】服务器转发使用tensorboard

场景 代码在服务器上运行&#xff0c;想使用tensorboard查看训练的过程。 但是服务器上不能直接访问地址&#xff0c;所以要转发端口到本地&#xff0c;从而在本地网页中能够打开tensorboard。 参考&#xff1a;https://zhuanlan.zhihu.com/p/680596384 这时我们需要建立本地…