AB8. 【模板】循环队列
描述
请你实现一个循环队列，该循环队列可利用的空间大小等于输入描述
第一行输入两个整数输出描述
按对应操作要求输出。示例1
输入:
3 10 push 1 push 2 front push 3 push 4 pop pop pop front pop
输出:
1 full 1 2 3 empty empty
C 解法, 执行用时: 16ms, 内存消耗: 908KB, 提交时间: 2022-04-07
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* queue;
int count=0;
int front=-1;
int rear=-1;
void Push(int x)
{
if(front == -1 && rear == -1) {
front = 0;
}
else if((rear+1)%count == front) {
printf("full\n");
return;
}
rear = (rear + 1) % count;
queue[rear] = x;
}
void Front()
{
if(front == -1 && rear == -1) {
printf("empty\n");
return;
}
printf("%d\n", queue[front]);
}
void Pop()
{
if(front == -1 && rear == -1) {
printf("empty\n");
return;
}
printf("%d\n", queue[front]);
if(front == rear) front = rear = -1;
else front = (front + 1) % count;
}
int main()
{
int q;
char command[50]={0}, ch;
char params[2][50] = {0};
int count1 = 0;
int count2 = 0;
int count3 = 0;
scanf("%d %d\n", &count, &q);
queue = (int *)malloc(count*sizeof(int));
for(int i=0; i<q; i++) {
memset(command, '\0', 50);
memset(params[0], '\0', 50);
memset(params[1], '\0', 50);
count1=count2=count3=0;
while((ch=getchar()) != '\n') command[count1++] = ch;
for(int j=0; j<count1; j++) {
if(command[j] != ' ') params[count2][count3++] = command[j];
else {
count2++;
count3=0;
}
}
if(strcmp(params[0], "push") == 0) Push(atoi(params[1]));
else if(strcmp(params[0], "pop") == 0) Pop();
else if(strcmp(params[0], "front") == 0) Front();
}
return 0;
}
C 解法, 执行用时: 17ms, 内存消耗: 904KB, 提交时间: 2022-07-23
#include <stdlib.h>
#include <stdio.h>
struct queue
{
int *data;
int capacity;
int headIdx;
int tailIdx;
};
void free_circular_queue(struct queue* iQueue)
{
if(iQueue != NULL)
{
free(iQueue->data);
free(iQueue);
}
}
struct queue* create_circular_queue(int capa)
{
struct queue* o;
o = (struct queue*)malloc(sizeof(struct queue));
o->data = (int*)malloc(sizeof(int) * capa);
o->capacity = capa;
o->headIdx = -1;
o->tailIdx = -1;
return o;
}
void push_circular_queue(struct queue* iQueue, int num)
{
if(iQueue->tailIdx == -1 && iQueue->headIdx == -1){
iQueue->headIdx = 0;
}else if ((iQueue->tailIdx + 1) % iQueue->capacity == iQueue->headIdx){
printf("full\n");
return;
}
iQueue->tailIdx = (iQueue->tailIdx + 1) % iQueue->capacity;
iQueue->data[iQueue->tailIdx] = num;
}
void pop_circular_queue(struct queue* iQueue)
{
if(iQueue->tailIdx == -1 && iQueue->headIdx == -1){
printf("empty\n");
return;
}
printf("%d\n", iQueue->data[iQueue->headIdx]);
if(iQueue->headIdx == iQueue->tailIdx){
iQueue->tailIdx = -1;
iQueue->headIdx = -1;
}else{
iQueue->headIdx = (iQueue->headIdx + 1) % iQueue->capacity;
}
}
void front_circular_queue(struct queue* iQueue)
{
if(iQueue->tailIdx == -1 && iQueue->headIdx == -1){
printf("empty\n");
return;
}
printf("%d\n", iQueue->data[iQueue->headIdx]);
}
#define CHAR_CAPACITY 20
int main(void)
{
char inputC[CHAR_CAPACITY];
fgets(inputC, CHAR_CAPACITY, stdin);
int capa, opraNum;
int idx = 0, spaceIdx;
while(inputC[idx] != '\0'){
if(inputC[idx++] == ' ')
{
spaceIdx = idx - 1;
inputC[spaceIdx] = '\0';
}
}
capa = atoi(inputC);
opraNum = atoi(inputC + spaceIdx + 1);
struct queue* mQueue = NULL;
mQueue = create_circular_queue(capa);
for(int i = 0; i < opraNum; i++)
{
fgets(inputC, CHAR_CAPACITY, stdin);
if(inputC[0] == 'p'){
if(inputC[1] == 'u'){
push_circular_queue(mQueue, atoi(inputC + 5));
}else{
pop_circular_queue(mQueue);
}
}
if(inputC[0] == 'f'){
front_circular_queue(mQueue);
}
}
free_circular_queue(mQueue);
return 0;
}
C 解法, 执行用时: 17ms, 内存消耗: 904KB, 提交时间: 2022-07-06
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[20];
int fr=0;
int re=0;
int l,*a;
void _push();
void _pop();
void _front();
int main()
{
int q,i;
scanf("%d%d",&l,&q);
getchar();
l++;
a=(int*)malloc(l*sizeof(int));
for (i=0;i<q;i++)
{
gets(s);
if(s[1]=='u')
_push();
else if(s[1]=='o')
_pop();
else if(s[1]=='r')
_front();
}
}
void _push()
{
if((re+1)%l==fr)
{
printf("full\n");
return;
}
int sl=strlen(s);
char sr[10];
strcpy(sr,s+5);
int n=atoi(sr);
a[re]=n;
re=(re+1)%l;
//printf("%d %d\n",fr,re);
}
void _pop()
{
if(fr==re)
{
printf("empty\n");
return;
}
int sl=strlen(s);
char sr[10];
strcpy(sr,s+4);
int n=atoi(sr);
printf("%d\n",a[fr]);
fr=(fr+1)%l;
//printf("%d %d\n",fr,re);
}
void _front()
{
if(fr==re)
{
printf("empty\n");
return;
}
printf("%d\n",a[fr]);
}
C 解法, 执行用时: 18ms, 内存消耗: 864KB, 提交时间: 2022-04-04
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int datatype;
typedef struct cq
{
datatype *a;
int front;
int rear;
}CQ;
void CQInit(CQ*pc,int n)
{
pc->a=(datatype*)malloc(sizeof(datatype)*(n+1));
pc->front=0;
pc->rear=0;
}
void CQpush(CQ*pc,int x,int n)
{
if((pc->rear+1)%(n+1)==pc->front)
{
printf("full\n");
return;
}
else
{
pc->a[pc->rear]=x;
pc->rear=(pc->rear+1)%(n+1);
}
}
void CQpop(CQ*pc,int n)
{
if(pc->front==pc->rear)
{
printf("empty\n");
return;
}
else
{
printf("%d\n",pc->a[pc->front]);
pc->front=(pc->front+1)%(n+1);
}
}
void CQFront(CQ*pc,int n)
{
if(pc->front==pc->rear)
{
printf("empty\n");
return;
}
else
{
printf("%d\n",pc->a[pc->front]);
}
}
int main()
{
int n,q,x,j;
scanf("%d %d",&n,&q);
char c,arr[10];
CQ Cirq;
CQInit(&Cirq,n);
getchar();
for (int i=1;i<=q;i++)
{
j=0;
memset(arr,'\0',sizeof(arr));
while((c=getchar())!='\n')
{
if(c==' ')
break;
else
arr[j]=c,j++;
}
if(c==' ')
scanf("%d",&x),getchar();
if(strcmp("push",arr)==0)
{
CQpush(&Cirq,x,n);
continue;
}
if(strcmp("pop",arr)==0)
{
CQpop(&Cirq,n);
continue;
}
if(strcmp("front",arr)==0)
{
CQFront(&Cirq,n);
continue;
}
}
return 0;
}
C 解法, 执行用时: 18ms, 内存消耗: 904KB, 提交时间: 2022-04-17
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void queue_opt(int *queue, int size, int *pos, char *buf)
{
int u;
int v;
size++;
if(strncmp(buf, "push", 4) == 0)
{
u = atoi(buf+5);
v = pos[1] + 1;
v %= size;
if(v == pos[0])
{
printf("full\n");
}
else
{
pos[1] = v;
queue[v] = u;
}
}
else if(strncmp(buf, "pop", 3) == 0)
{
v = pos[0] + 1;
v %= size;
if(pos[0] == pos[1])
{
printf("empty\n");
}
else
{
pos[0] = v;
printf("%d\n", queue[v]);
}
}
else if(strncmp(buf, "front", 5) == 0)
{
v = pos[0] + 1;
v %= size;
if(pos[0] == pos[1])
{
printf("empty\n");
}
else
{
printf("%d\n", queue[v]);
}
}
}
int main()
{
char buf[128];
int a[100*1000];
int size;
int n;
int pos[2] = {0, 0};
int i;
scanf("%d %d\n", &size, &n);
if(n < 1 || n > 100*1000 || size < 1 || size > 100*1000)
{
return -1;
}
for(i=0; i<n; i++)
{
memset(buf, 0x00, sizeof(buf));
fgets(buf, 127, stdin);
queue_opt(a, size, pos, buf);
}
return 0;
}