假溢出:在顺序队列中,队列出队时并没有像线性表那样使后面的元素往前移。
为了解决假溢出,常用的方法是把队列想成一个首尾相接的环,这种叫循环队列。在循环队列的入队和出队操作中,用到了求模运算(%),以确保front和rear的值保持在队列的有效范围内。
对于队列q,初始化为空队列使q->front==q->rear==0。
新元素入队时操作为:
q->data[q->rear]=x;
q->rear=(q->rear+1)%MAXSIZE;
出队操作为:
x=q->data[q->front];
q->front=(q->front+1)%MAXSIZE;
此时我们发现从一开始一直入队直到队列满时,此时q->front==q->rear==0;和判队列空的条件一摸一样,那怎么办??我们有以下三种方案
flag法
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
#define MAXSIZE 6
typedef struct
{
DataType data[MAXSIZE];
int front, rear;
int flag;
}CSeqQueue;
void Init_Queue(CSeqQueue* q)
{
q->front = 0;
q->rear = 0;
q->flag = 0;
}
int Out_Queue(CSeqQueue* q, DataType* x)
{
if (q->flag == 0 && q->front == q->rear)
{
printf("队列为空!\n");
return 0;
}
else
{
*x = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
if (q->front == q->rear)
q->flag = 0;
return 1;
}
}
int In_Queue(CSeqQueue* q, DataType x)
{
if (q->flag == 1 && q->flag == q->rear)
{
printf("队列已满!");
return 0;
}
else
{
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAXSIZE;
if (q->front == q->rear)
q->flag = 1;
return 1;
}
}
int Length_Queue(CSeqQueue* q)
{
// return (q->rear-q->front+MAXSIZE)%MAXSIZE;
return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
int main()
{
CSeqQueue* q;
int i;
DataType x;
q = (CSeqQueue*)malloc(sizeof(CSeqQueue));
Init_Queue(q);
printf("请插入%d个数字:", MAXSIZE);
for (i = 1; i <= MAXSIZE; i++)
{
scanf("%d", &x);
if (In_Queue(q, x) == 0)break;
}
printf("现在出队三个:");
for (i = 1; i <= 3; i++)
{
if (Out_Queue(q, &x) == 0)break;
printf("%5d", x);
}
printf("\n目前队列中有%d个元素:", Length_Queue(q));
for (i = q->front; i != q->rear; i = (i + 1) % MAXSIZE)
{
printf("%5d", q->data[i]);
}
system("pause");
return 0;
}
count法
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
#define MAXSIZE 6
typedef struct
{
DataType data[MAXSIZE];
int front, rear;
int count;//队列中元素个数
}CSeqQueue;
void Init_Queue(CSeqQueue* q)
{
q->front = 0;
q->rear = 0;
q->count = 0;
}
int Out_Queue(CSeqQueue* q, DataType* x)
{
if (q->count == 0)
{
printf(" 队列已为空,无元素可取\n");
return 0;
}
else
{
*x = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
q->count--;
return 1;
}
}
int In_Queue(CSeqQueue* q, DataType x)
{
if (q->count == MAXSIZE)
{
printf("队已满,不能插入元素\n");
return 0;
}
else
{
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAXSIZE;
q->count++;
return 1;
}
}
int Length_Queue(CSeqQueue* q)
{
return q->count;
}
void main()
{
CSeqQueue* q;
int i;
DataType x;
q = (CSeqQueue*)malloc(sizeof(CSeqQueue));
Init_Queue(q);
printf("请插入6个数字:");
for (i = 1; i <= 6; i++)
{
scanf("%d", &x);
if (In_Queue(q, x) == 0)break;
}
printf("队列现在满了,你试着再插入一个\n");
scanf("%d", &x);
In_Queue(q, x);
printf("将前3个数字出队:");
for (i = 1; i <= 3; i++)
{
if (Out_Queue(q, &x) == 0)break;
printf("%5d", x);
}
printf("\n目前队列中有%d个元素:", Length_Queue(q));
for (i = q->front; i != q->rear; i = (i + 1) % MAXSIZE)
{
printf("%5d", q->data[i]);
}
printf("\n");
system("pause");
}
少用一个空间
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
#define MAXSIZE 6
typedef struct
{
DataType data[MAXSIZE];
int front, rear;
}CSeqQueue;
void Init_Queue(CSeqQueue* q)
{
q->front = 0;
q->rear = 0;
}
int Out_Queue(CSeqQueue* q, DataType* x)
{
if (q->front == q->rear)
{
printf("队列为空!\n");
return 0;
}
else
{
*x = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
return 1;
}
}
int In_Queue(CSeqQueue* q, DataType x)
{
if ((q->rear + 1) % MAXSIZE == q->front)
{
printf("队列已满!");
return 0;
}
else
{
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAXSIZE;
return 1;
}
}
int Length_Queue(CSeqQueue* q)
{
// return (q->rear-q->front+MAXSIZE)%MAXSIZE;
return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
int main()
{
CSeqQueue* q;
int i;
DataType x;
q = (CSeqQueue*)malloc(sizeof(CSeqQueue));
Init_Queue(q);
printf("请插入%d个数字:", MAXSIZE-1);
for (i = 1; i < MAXSIZE; i++)
{
scanf("%d", &x);
if (In_Queue(q, x) == 0)break;
}
printf("现在出队三个:");
for (i = 1; i <= 3; i++)
{
if (Out_Queue(q, &x) == 0)break;
printf("%5d", x);
}
printf("\n目前队列中有%d个元素:", Length_Queue(q));
for (i = q->front; i != q->rear; i = (i + 1) % MAXSIZE)
{
printf("%5d", q->data[i]);
}
system("pause");
return 0;
}