顺序循环队列
可以插入一头叫队尾rear，可以删除的一头叫队头front
为了解决假溢出，使用循环队列
设置一个计数器，每次插入count都加1，删除就减1。队列空的时候 count==1，队列满的时候 count>0&&rear==front。
当然解决满和空 还有其它方法：少用一个单元，设标志位。
SeqCQueue.h
typedef struct
{
DataType queue[MaxQueueSize]; //顺序的嘛，用数组
int rear;
int front;
int count;
}SeqCQueue;
void QueueInitiate(SeqCQueue *Q) //初始化
{
Q->rear=0;
Q->front=0;
Q->count=0;
}
int QueueNotEmpty(SeqCQueue Q)
{
if(Q.count!=0) return 1;
else
return 0;
}
int QueueAppend(SeqCQueue *Q,DataType x) //插入
{
if(Q->count>0&&Q->rear==Q->front) //队头队尾相等，计数器还大于0，满啦
{
printf("over");
return 0;
}
else
{
Q->queue[Q->rear]=x; //将队尾赋值x，和栈一样，rear始终是指向队头元素的下一个位置
Q->rear=(Q->rear+1)%MaxQueueSize; //如果rear+1等于MaxQueueSize的话，它就会重新置0，循环了嘛
Q->count++;
return 1;
}
}
int QueueDelete(SeqCQueue *Q,DataType *d)
{
if(Q->count==0)
{
printf("empty");
return 0;
}
else
{
*d=Q->queue[Q->front];
Q->front=(Q->front+1)%MaxQueueSize; //一样，如果队头到了最顶上，再删除的话，front就重新指到最底下
Q->count--;
return 1;
}
}
int QueueGet(SeqCQueue Q,DataType *d)
{
if(Q.count==0)
{
printf("empty");
return 0;
}
else
{
*d=Q.queue[Q.front];
return 1;
}
}
例子用到了前面的顺序栈
判断回文，如“ABCDEDCBA”这种
思想：把字符串放入一个栈和一个队列中，然后出栈，出队列
因为它们两个的方向不同，每次比较就是让前后对应位置的字符比较
#include <stdio.h>
#include <string.h>
#define MaxQueueSize 100
#define MaxStackSize 100
typedef char DataType;
#include "SeqCQueue.h"
#include "SeqStack.h"
void HuiWen(char str[])
{
SeqCQueue myQueue;
SeqStack myStack;
char x,y;
int i,length;
length=strlen(str); //字符串长
QueueInitiate(&myQueue);
StackInitiate(&myStack);
for(i=0;i<length;i++)
{
QueueAppend(&myQueue,str[i]); //装入队列
StackPush(&myStack,str[i]); //装入栈
}
while(QueueNotEmpty(myQueue)==1 && StackNotEmpty(myStack)==1) //不是空时
{
if(QueueDelete(&myQueue,&x)==1 && StackPop(&myStack,&y)==1 && x!=y) //对应项等不等
{
printf("%s 不是回文",str);
return;
}
}
if(QueueNotEmpty(myQueue)||StackNotEmpty(myStack)) // 一个空了，一个没空，那肯定不是
printf("%s 不是回文\n",str);
else //两个同时为0，都空了，才是回文
printf("%s 是回文\n",str);
}
void main(void)
{
char str1[]="ABCDEDCBA";
char str2[]="ABCDEDCAB";
HuiWen(str1);
HuiWen(str2);
}
评论