根据给定的空间构造顺序循环队列，规定队满处理方法为少用一个元素空间。例如，给定5个元素空间构造循环队列，则只能存放4个元素。试根据入队及出队操作判断队列最后的元素存放情况，并输出最后队列中的元素值，即完成给定入队及出列操作后一次性全部出队的元素值。要求采用顺序队列完成，少用一个存储空间的方法区分队列的空和满。
输入的第一行为一个自然数n，表示要求构造的顺序循环队列空间数。 第二行为操作次k，接下来k行为出队入队操作，每行各代表一次操作。入队用in表示，出队用out表示，如果是入队，则in隔一空格后为一整数，表示入队元素值。
输出完成所有入队出队操作后，一次性出队元素。用一个空格隔开。可以假定队在完成所有操作后不为空。
-----------------------------------------------------------------
4 7 in 1 in 2 in 5 in 6 out out in 8 _____________________________________
5 8
首先，我先粘一个AC代码吧，不得不说，之前的队列是在《啊哈算法》上看到的，但是那个队列和现在这个题比起来要稍逊一些，0965这个题比啊哈上要复杂一些;
贴代码前，我写了一个做队列题目的流程图吧：
队列
↓
队头，队尾<struct node>
↓
队列里的数据元素<struct node>
↓
初始化一个指针用来操作<void startQueue(Queue *&l)>,在里面同时初始化队头和队尾;
↓
入队→判满→不满则放数据，满就return;<这里是一个void入队>
↓
出队→判空→空则返回一个标记值（-1），不空则返回被删除的那个数，最后在main函数里用来输出最后剩下的数据
↓
int main()
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <string.h> using namespace std; #define maxn 1005 int n; typedef struct node { int head,rear;//队列必须有队头和队尾; char data[maxn];//把数据类型统一定义为字符型; }Queue; void startQueue(Queue *&l) { l=(Queue *)malloc(sizeof(Queue)); l->head=l->rear=0;//初始化队头和队尾; } void EnterQueue(Queue *&l,int dat)//入队操作; { if((l->rear+1)%n==l->head) return;//只允许放n-1个元素,此处为判断队列是否已满; l->rear=(l->rear+1)%n; l->data[l->rear]=dat;//如果所有的位置都可以放就不用rear+1; } int DeleteQueue(Queue *&l) { if(l->head==l->rear) return -100; //队列里面什么都没有，删神马? l->head=(l->head+1)%n; int e=l->data[l->head]; return e; } int main() { int cnt; Queue *q; cin>>n>>cnt; startQueue(q); char order[20]; int data_; while(cnt--)//输入cnt行; { cin>>order; if(strcmp(order,"in")==0) { cin>>data_; EnterQueue(q,data_); } else DeleteQueue(q); } for(int i=0;;i++) { int k=DeleteQueue(q); if(k==-100) break; else cout<<k<<" "; } //system("pause"); return 0; } ------下面贴一个失败的代码，在我没有完全理解队列时写出来的失败产物，以此警示:
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <string> #include <string.h> using namespace std; typedef struct node { int data[1005]; struct node *next; }Queue; void createQueue(Queue *&Q,int num,int cnt) { void deleteQueue(Queue *&Q,int tar,int &nodeQ); string order; Q=(Queue *)malloc(sizeof(Queue)); Queue *p,*q; p=Q; int count=0; int head=0,rear=0; for(int i=0;i<cnt;i++) { q=(Queue *)malloc(sizeof(Queue)); cin>>order; if(count==num-1) { count=0; continue; } else if(order=="in") { cin>>q->data[rear]; rear++; rear=rear%(num-1); count++; } else if(order=="out") { head=head%(num-1); head++; continue; } p->next=q; p=q; } p->next=NULL; } void Traverse(Queue *&Q,int num) { Queue *temp=Q; for(int i=0;i<num-1;i++) { if(temp->data[i]) cout<<temp->data[i]<<" "; } } int main() { int num,cnt; Queue *queue; while(cin>>num) { cin>>cnt; getchar();getchar(); createQueue(queue,num,cnt); Traverse(queue,num); } return 0; }
