九度 1415 不一样的循环队列 【数据结构】

前端之家收集整理的这篇文章主要介绍了九度 1415 不一样的循环队列 【数据结构】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目地址:http://ac.jobdu.com/problem.php?pid=1415

题目描述:

大家都知道数据结构里面有一个结构叫做循环队列。顾名思义,这是一个队列,并且是循环的。但是现在,淘气的囧哥给这个循环队列加上了一些规矩,其中有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 2
Push 1
Push 2
Push 3
Query 2
Query 3
Isempty
Isfull
Pop
Pop
Pop
Isempty
Isfull
样例输出
Failed
2
Failed
no
yes
Failed
yes
no

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

int queue[100010];
int N,M;
int front,tail;

void Init(){
	front = 0;
	tail = 0;
}

int Isempty(){
	return (front == tail) ? 1 : 0;
}

int Isfull(){
	return (front == (tail + 1)%M) ? 1 : 0;
}

int Push(int k){
	if (!Isfull()){
		queue[tail] = k;
		tail = (tail + 1) % M;
		return 1;
	}
	return 0;
}

int Pop(){
	if (!Isempty()){
		front = (front + 1) % M;
		return 1;
	}
	return 0;
}

int Query(int k,int * ans){//检查k的合法性 
	if (k > (tail - front + M) % M || k < 1)
		return 0;
	else{
		*ans = queue[(front + k - 1)%M];
		return 1;
	}
}

int main(int argc,char *argv[]) {
	int i,k,ans;
	char ope[10];
	while (scanf("%d%d",&N,&M) != EOF){
		++M;///////////////////////////////
		Init();
		while (N-- != 0){
			scanf("%s",ope);
			if (strcmp(ope,"Push") == 0){
				scanf("%d",&k);
				if (!Push(k)) printf("Failed\n");
			}
			else if (strcmp(ope,"Pop") == 0){
				if (!Pop()) printf("Failed\n");
			}
			else if(strcmp(ope,"Query") == 0){
				scanf("%d",&k);
				if (Query(k,&ans)) printf("%d\n",ans);
				else printf("Failed\n");
			}
			else if (strcmp(ope,"Isempty") == 0){
				if (Isempty())
					printf("yes\n");
				else
					printf("no\n");
			}
			else{
				if (Isfull())
					printf("yes\n");
				else
					printf("no\n");
			}
		}
	}
	return 0;
}
原文链接:https://www.f2er.com/datastructure/383084.html

猜你在找的数据结构相关文章