服务器之家

服务器之家 > 正文

使用C语言来解决循环队列问题的方法

时间:2021-03-07 14:13     来源/作者:低调小一

题目描述:

    大家都知道数据结构里面有一个结构叫做循环队列。顾名思义,这是一个队列,并且是循环的。但是现在,淘气的囧哥给这个循环队列加上了一些规矩,其中有5条指令:

    (1) Push K, 让元素K进队列。

    (2) Pop,对头元素出队列。

    (3) Query K,查找队列中第K个元素,注意K的合法性。

    (4) Isempty,判断队列是否为空。

    (5) Isfull,判断队列是否已满。

    现在有N行指令,并且告诉你队列大小是M。

输入:

    第一行包含两个整数N和M。1<=N,M<=100000。

    接下来有N行,表示指令,指令格式见题目描述。

    其中元素均在int范围。

输出:

    对于指令(1),若队列已满,输出failed,否则不做输出。

    对于指令(2),若队列已空,输出failed,否则不做输出。

    对于指令(3),输出队列中第K个元素,若不存在,输出failed。

    对于指令(4)和(5),则用yes或者no回答。

    详情见样例。

样例输入:

    12 2Push 1Push 2Push 3Query 2Query 3IsemptyIsfullPopPopPopIsemptyIsfull

样例输出:

    failed2failednoyesfailedyesno

AC代码:

   

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
   
  #define queuesize 100001  //最大队列长度
   
  struct queue
  {
    int front;
    int rear;
    int data[queuesize];
    int count; //记录队列中的元素
  };
   
  void InitQueue(struct queue *Q);
  void EnQueue(struct queue *Q, int element, int m);
  void Dequeue(struct queue *Q, int m);
  void QueueSearch(struct queue *Q, int k, int m);
   
  int main()
  {
    int n, m, i, element, k, flag;
    char command[10];
   
    while(scanf("%d%d",&n, &m) != EOF)
    {
      if(n < 1 || m > 100000)
        return 0;
      struct queue *Q;
      Q = malloc(sizeof(struct queue));
      InitQueue(Q);
      for(i = 0; i < n; i ++)
      {
        scanf("%s",command);
        if (strcmp(command,"Push") == 0)
        {
          scanf("%d",&element);
          EnQueue(Q, element, m);
        }else if (strcmp(command,"Pop") == 0)
        {
          Dequeue(Q, m);
        }else if (strcmp(command,"Query") == 0)
        {
          scanf("%d",&k);
          QueueSearch(Q, k, m);
        }else if (strcmp(command,"Isempty") == 0)
        {
          flag = (Q -> count == 0)? 1 : 0;
          if(flag)
          {
            printf("yes\n");
          }else
          {
            printf("no\n");
          }
        }else if (strcmp(command,"Isfull") == 0)
        {
          flag = (Q -> count == m)? 1 : 0;
          if(flag)
          {
            printf("yes\n");
          }else
          {
            printf("no\n");
          }
        }
      }
    }  
    return 0;
  }
   
  /**
   * Description:队列初始化
   */
  void InitQueue(struct queue *Q)
  {
    Q -> front = Q -> rear = 0;
    Q -> count = 0;
  }
   
  /**
   * Description:入队操作
   */
  void EnQueue(struct queue *Q, int element, int m)
  {
    int flag;
    flag = (Q -> count == m)? 1 : 0; 
   
    if(!flag)
    {
      Q -> data[Q -> rear] = element;
      Q -> count ++;
      Q -> rear = (Q -> rear + 1) % m;
    }else
    {
      printf("failed\n");
    }
  }
   
  /**
   * Description:出队操作
   */
  void Dequeue(struct queue *Q, int m)
  {
    int flag;
    int element;
   
    flag = (Q -> count == 0)? 1 : 0;
   
    if(!flag)
    {
      element = Q -> data[Q -> front];
      Q -> front = (Q -> front + 1) % m;
      Q -> count --;
    }else
    {
      printf("failed\n");
    }
  }
   
  /**
   * Description:查找队列中的指定元素
   */
  void QueueSearch(struct queue *Q, int k, int m)
  {
    int flag, temp;
    flag = (Q -> count == 0)? 1: 0;
    temp = Q -> front + k - 1;
    if((!flag) && (k <= m && k >= 1))
    {
      if((Q -> front < Q -> rear) && ( Q-> front <= temp && Q -> rear > temp))
        printf("%d\n",Q -> data[temp]);
      else if((Q -> front > Q -> rear) && (temp >= Q -> front || temp < Q->rear))
        printf("%d\n",Q -> data[temp]);
      else if(Q -> front == Q -> rear)
        printf("%d\n",Q -> data[temp]);
      else
        printf("failed\n");
    }else
    {
      printf("failed\n");
    }
  }
标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部