第3章 栈和队列 编程题

PS ： 这函数题真的跟X一样,非要搞起来显得那么复杂,还得跟着它那令人心碎的逻辑走,等以后要是有心情了再考虑补上

目录

7-1 队列的实现及基本操作

7-2 队的基本操作 

7-3 h0181. 约瑟夫问题

7-4 括号匹配

7-5 判断回文

7-6 模拟栈

7-7 模拟队列

7-8 队列操作

7-9 汉诺塔（Lanqiao）

7-10 表达式转换

7-11 逆波兰表达式求值

7-1 队列的实现及基本操作

// 数组模拟
#include<stdio.h>
int main()
{
    int N,command,queue[100001],head=0,tail=0; // 模拟队列
    scanf("%d",&N);
    while (N--)
    {
        scanf("%d",&command);
        if(command==1) scanf("%d",&queue[tail++]);
        else if(head==tail) printf("invalid\n");
        else printf("%d\n",queue[head++]);
    }
    return 0;
}

7-2 队的基本操作 

http://t.csdn.cn/CiXx0

7-3 h0181. 约瑟夫问题

#include<stdio.h>
int main()
{
    int n,m,result;
    while (scanf("%d %d",&n,&m) && (n!=0 || m!=0) ){
        result = 1;
        for(int z=1;z<=n;z++) result = (result+m)%z;
        printf("%d\n",result+1);
    }
    return 0;
}

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


struct Queue{
    int data;
    struct Queue* next;
}*queue,*pop;


struct Queue *createQueue(int len);   // 生成长度为len循环队列
int main()
{
    int n,m;
    while (scanf("%d %d",&n,&m) && (n!=0 || m!=0)){
        queue = createQueue(n);
        while (queue->next!=NULL)
        {
            for(int z=1;z<m;z++) queue=queue->next;
            if(queue->next->next!=queue)
            {
                pop = queue->next;
                queue->next = pop->next;
                free(pop);
            }
            else
            {
                free(queue->next);
                queue->next = NULL;
            }
        }
        printf("%d\n",queue->data-1);
        free(queue);
    }
    return 0;
}
// 生成循环队列
struct Queue *createQueue(int len)
{
    struct Queue *head,*body;
    head = (struct Queue *) malloc(sizeof(struct Queue));
    head->data = 1;     // 0 默认空数据
    body = head;
    for(int z=2;z<=len;z++){
        body->next = (struct Queue *) malloc(sizeof(struct Queue));
        body = body->next;
        body->data = z;
    }
    body->next = head;
    return head;
}

7-4 括号匹配

#include<stdio.h>

int flag(char a,char b);
int main()
{

    char str[2022],stack[502];
    int N,top;
    scanf("%d",&N);
    getchar();
    while (N--)
    {
        gets(str);
        top = 0;
        for(int z=0;str[z]!='\0';z++)
        {
            if(str[z]=='(' || str[z]=='{' || str[z]=='[') stack[++top] = str[z];
            else if(str[z]==')' || str[z]=='}' || str[z]==']')
            {
                if(flag(stack[top],str[z])) top--;
                else
                {
                    top = -1;
                    break;
                }
            }
        }
        top == 0 ? puts("Yes") : puts("No");
    }

    return 0;
}
int flag(char a,char b)
{
    if(a=='{' && b=='}') return 1;
    if(a=='(' && b==')') return 1;
    if(a=='[' && b==']') return 1;
    return 0;
}

7-5 判断回文

#include <stdio.h>
#include <string.h>
int main()
{
    char s[520];
    gets(s);
    
    int len = strlen(s),flag = 1;
    for(int z=0;z<len/2;z++) if(s[z]!=s[len-z-1]) {
        flag = 0;
        break;
    }
    
    for(int z=0;z<len;z++) putchar(s[z]);
    flag == 1 ? puts("是回文。") : puts("不是回文。");
    return 0;
}

7-6 模拟栈

#include<stdio.h>

int main()
{
    int stack[200408],top=0,N,command;
    char str[200814];
    scanf("%d",&N);
    while (N--)
    {
        scanf("%s",&str);
        command = 0;
        for(int z=0;str[z]!='\0';z++) command += str[z];
        switch (command) {
            case 448: scanf("%d",&stack[top++]); break;
            case 335: top--;break;
            case 559: top==0 ? puts("YES") : puts("NO"); break;
            case 566: printf("%d\n",stack[top-1]);break;
        }
    }

    return 0;
}

7-7 模拟队列

#include<stdio.h>

int main()
{
    int queue[200408],head=0,tail=0,N,command;
    char str[200814];
    scanf("%d",&N);
    while (N--)
    {
        scanf("%s",&str);
        command = 0;
        for(int z=0;str[z]!='\0';z++) command += str[z];
        switch (command) {
            case 448: scanf("%d",&queue[tail++]); break;
            case 335: head++;break;
            case 559: head==tail ? puts("YES") : puts("NO"); break;
            case 566: printf("%d\n",queue[head]);break;
        }
    }

    return 0;
}

7-8 队列操作

#include<stdio.h>

int main()
{
    int queue[200408],head=0,tail=0,N,command;
    scanf("%d",&N);

    for(int z=0;z<N;z++)
    {
        scanf("%d",&command);
        switch (command) {
            case 1: scanf("%d",&queue[tail++]); break;
            case 2:
                if(head<tail) printf("%d\n",queue[head++]);
                else puts("no"),N = 0;
                break;
            case 3: printf("%d\n",tail-head);
        }
    }
    return 0;
}

7-9 汉诺塔（Lanqiao）

#include<stdio.h>
int N,M,result=0;
void N0_ON(int deep,char a,char b,char c)
{
    if(deep==0) return;
    N0_ON(deep-1,a,c,b);
    if(++result==M) printf("#%d: %c->%c\n",deep,a,c);
    N0_ON(deep-1,b,a,c);
}
int main()
{
    scanf("%d %d",&N,&M);
    N0_ON(N,'A','B','C');
    printf("%d",result);
    return 0;
}

7-10 表达式转换

http://t.csdn.cn/2HGe5

7-11 逆波兰表达式求值

#include<stdio.h>
int atoi(char *key);    // 字符串转数字
int main()
{
    int stack[2022]={0},top=0,num;
    char str[88480];
    while (scanf("%s",&str)!=EOF)
    {
        if(str[0]=='+' || str[0]=='-' || str[0]=='*')
        {
            num = stack[--top];
            switch (str[0]) {
                case '+': stack[top-1]+=num; break;
                case '-': stack[top-1]-=num; break;
                case '*': stack[top-1]*=num; break;
            }
        }
        else stack[top++] = atoi(str);
    }
    printf("%d",stack[0]);
    return 0;
}
int atoi(char *key)
{
    int result = 0;
    for(int z=0;key[z]!='\0';z++) result = result*10+key[z]-'0';
    return result;
}