数据结构 栈&队列

数据结构 栈&队列

2-4

依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是( )

数据结构 栈&队列

删除,移动头指针;

增加,移动尾指针;

删除a,b ,队头c

2-3

在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为( )

数据结构 栈&队列

这道题目,我坚持自己的答案,就是这个答案!

2-1

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

数据结构 栈&队列

删除,front++

增加,rear++

是 2 和 6,循环队列 6%6=0

2 和 0

2-3

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

元素个数size = (rear-front+m)%m+1;

由此可得,rear = (size+front-1)%m;

编程题答案在我其他博客里,直接在侧栏搜索就行

代码:

队列

链队列   链队列C

双向队列


 
 
 
2-2

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

数据结构 栈&队列

 第一个出栈的元素是4,说明栈里已经压入了 1 2 3 4,四个元素;
那么5可以随时入栈,出栈,所以 5可以在2,3,4,5位置出栈,5在2,3,4出栈的时候,1就是最后出栈的,5在5出栈,那么1就在4出栈;
2-7

设一个栈的输入序列是1、2、3、4、5,则下列序列中,是栈的合法输出序列的是?

数据结构 栈&队列

解读下A:

1.压入 1 2 3

2.弹出 3 2 1

3.压入 4 5

4.弹出 5 4

出栈顺序就是 3 2 1 5 4,成立,别的也可以用相同的方式进行分析;

 
2-11

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

数据结构 栈&队列

可以看出,最后两个ps都是压入后就弹出的,所以就是研究 ooo的弹出组合;

ooo

 排列组合:
压入三个:再弹出 : 1种
压入两个:再弹出 : 2种
压入一个:再弹出 : 2种
总 5 种
 
 
 
 

 

队列&栈函数题(只补充之前博客里没有的)

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

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

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

输入样例:

SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX
输出样例:
YES
NO
NO
NO

----------------------------------------------------------------------
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#define EXP_STACK 50
#define ERROR -1
#define OK 1
using namespace std;
typedef int Elemtype;
typedef int Status;
;
int STACK_SIZE;
typedef struct
{
    Elemtype *base;
    Elemtype *top;
    int sta_len;
    int ElemNumber;
}Stack;
Status InitStack(Stack &Sta)
{
    Sta.base = (Elemtype *)malloc(STACK_SIZE*sizeof(Elemtype));
    ;
    Sta.top = Sta.base;
    Sta.sta_len = STACK_SIZE;
    Sta.ElemNumber = ;
}
Status GetTop(Stack sta,Elemtype &e)
{
    if(sta.top==sta.base) return ERROR;
    e = *(sta.top-);
    return OK;
}
Status Push(Stack &S,Elemtype e)
{
    if(S.top-S.base>=S.sta_len)
    {
        S.base = (Elemtype *)realloc(S.base,(EXP_STACK+S.sta_len)*sizeof(Elemtype));
        S.sta_len+=EXP_STACK;
    }
    *S.top++ = e;
    S.ElemNumber+=;
    return OK;
}
Status Pop(Stack &S)
{
    if(S.top==S.base) return ERROR;
    --S.top;
    S.ElemNumber--;
    return OK;
}
int main()
{
    int cases;
    int Len;
    scanf("%d%d",&cases,&Len);
    STACK_SIZE = Len;
    while(cases--)
    {
        ];
        scanf("%s",opr);
        int len = strlen(opr);
        Stack Sta;
        InitStack(Sta);
        //cout<<Sta.sta_len<<" "<<Sta.ElemNumber<<endl;
        bool Fits = true;
        ;i<len;i++)
        {
            if(opr[i]=='S')
            {
                if(Sta.ElemNumber==Len)
                {
                    Fits = false;
                    break;
                }
                Push(Sta,);
            }
            else if(opr[i]=='X')
            {
                int Ans = Pop(Sta);
                )
                {
                    Fits = false;
                    break;
                }
            }
        }
        if(Sta.ElemNumber) Fits = false;
        if(Fits)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

堆栈操作合法性

- 符号配对( 分)
请编写程序检查C语言源程序中下列符号是否配对:/*与*/、(与)、[与]、{与}。

输入格式:
输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候,标志着输入结束。程序中需要检查配对的符号不超过100个。

输出格式:
首先,如果所有符号配对正确,则在第一行中输出YES,否则输出NO。然后在第二行中指出第一个不配对的符号:如果缺少左符号,则输出?-右符号;如果缺少右符号,则输出左符号-?。

输入样例1:
void test()
{
    ];
    ; i<; i++) /*/
        A[i] = i;
}
.
输出样例1:
NO
/*-?
输入样例2:
void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.
输出样例2:
NO
?-]
输入样例3:
void test()
{
    int i
    ];
    ; i<; i++) /**/
        A[i] = 0.1*i;
}
.
输出样例3:
YES

--------------------------------------------------------------------

#include<cstdio>
#include<iostream>
#include<cmath>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<cstring>
#define STACK_INIT_SIZE 10000
#define STACKINCREMENT 10
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2
using namespace std;
typedef char SElemType,Status;
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
} Stack;
Status InitStack(Stack &S)
{
    S.base=(SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    if(!S.base)
        exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return OK;
}
Status Push(Stack &S,SElemType e)
{
    if(S.top-S.base>=S.stacksize)
    {
        S.base=(SElemType*)malloc(sizeof(SElemType)*(S.stacksize+STACKINCREMENT));
        if(!S.base)
            exit(OVERFLOW);
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
    return OK;

}
Status Pop(Stack &S)
{
    if(S.top==S.base)
        return ERROR;
    S.top--;
    return OK;
}
Status GetTop(Stack &S,SElemType &e)
{
    if(S.base==S.top)
        return ERROR;
    e=*(S.top-);
    return OK;
}
+;
char s[maxn];
bool Find(Stack &S,char ch)
{
    char tmp[maxn];
    memset(tmp,'\n',sizeof(tmp));
    ;
    while(S.top!=S.base)
    {
        SElemType e2;
        GetTop(S,e2);
        if(e2==ch)
        {
            Pop(S);
            ; i>=; i--)
                Push(S,tmp[i]);
            return true;
        }
        else
        {
            tmp[num++]=e2;
        }
        Pop(S);
    }
    ; i>=; i--)
        Push(S,tmp[i]);
    return false;
}
void judge(char ch)
{
    if(ch=='(')
     printf("(-?\n");
     else if(ch=='[')
        printf("[-?\n");
     else if(ch=='{')
        printf("{-?\n");
     else if(ch=='<')
        printf("/*-?\n");
}
int main()
{
    Stack Sta;
    InitStack(Sta);
    ;
    while(gets(s))
    {
        ]=='.') break;
        int len=strlen(s);
        ;i<strlen(s);i++)
        {
            if(s[i]=='('||s[i]=='['||s[i]=='{')
                Push(Sta,s[i]);
            ]==<len)
            {
                ++i;
               Push(Sta,'<');
            }

            else if(s[i]==')')
            {

                if(Sta.top!=Sta.base)
                {
                    SElemType e;
                    GetTop(Sta,e);
                    if(e=='(')
                        Pop(Sta);
                    else if(flag)
                    {
                        printf("NO\n");
                        flag=;
                        judge(e);
                    }
                }
                else if(flag)
                {
                    flag=;
                    printf("NO\n");
                    printf("?-)\n");
                }

            }
            else if(s[i]==']')
            {

                if(Sta.top!=Sta.base)
                {
                    SElemType e;
                    GetTop(Sta,e);
                    if(e=='[')
                        Pop(Sta);
                    else if(flag)
                    {
                        printf("NO\n");
                        flag=;
                        judge(e);
                    }
                }
                else if(flag)
                {
                    flag=;
                    printf("NO\n");
                     printf("?-]\n");
                }

            }
            else if(s[i]=='}')
            {

                if(Sta.top!=Sta.base)
                {
                    SElemType e;
                    GetTop(Sta,e);
                    if(e=='{')
                        Pop(Sta);
                    else if(flag)
                    {
                        printf("NO\n");
                        flag=;
                        judge(e);
                    }
                }
                else if(flag)
                {
                    flag=;
                    printf("NO\n");
                     printf("?-}\n");
                }

            }
            ]==<len)
            {
                ++i;
                if(Sta.top!=Sta.base)
                {
                    SElemType e;
                    GetTop(Sta,e);
                    if(e=='<')
                        Pop(Sta);
                    else if(flag)
                    {
                        printf("NO\n");
                        flag=;
                        judge(e);
                    }
                }
                else if(flag)
                {
                    flag=;
                    printf("NO\n");
                    printf("?-*/\n");
                }

            }
        }
    }
   if(flag)
   {
       if(Sta.base==Sta.top)
        printf("YES\n");
       else
       {
           SElemType e;
           GetTop(Sta,e);
           printf("NO\n");
           judge(e);
       }
   }
}

符号配对

简单的递归策略非常好理解:

只用一个题举例子:

数据结构 栈&队列

 分析:参数 n,x 两个, 条件 三个;
double P( int n, double x )
{
    if(n==0) return 1;   // 条件一
    else if(n==1) return x;//条件二
    else if(n>1)
    {
        return ((2*n-1)*P(n-1,x)-(n-1)*P(n-2,x))/n;//条件三
    }
}

  这就是根据条件和参数还原一下;

 
 

Made by Kindear
 
 
上一篇:[WCF编程]4.契约概述


下一篇:Android ScrollView监听滑动到顶部和底部的两种方式(你可能不知道的细节)