假溢出的解决策略

假溢出：在顺序队列中，队列出队时并没有像线性表那样使后面的元素往前移。

为了解决假溢出，常用的方法是把队列想成一个首尾相接的环，这种叫循环队列。在循环队列的入队和出队操作中，用到了求模运算（%），以确保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;和判队列空的条件一摸一样，那怎么办？？我们有以下三种方案

• 闲置循环队列中一个元素空间。当 rear 的下一个位置是 front 时，则宣告列满。此时，循环队列为空的条件为 rear==front，而循环队列为满的条件为:(q->rear+1)%MAXSIZE==q->front。按照这种办法，循环队列出队、入队操作不变，只是入队时循环队列的判断条件修改为(q->rear+1)%MAXSIZE= q->front 即可。

• 在循环队列上增加一个标志变量 flag，初始时q->flag=0。当因为入队操作q->front==q->rear时，置q->flag为1;当因为出队操作使q->front==q->rear 时，置 q->flag为0。因此，循环队列空的条件为q->flag==0&&q->front==q->rear,循环队列满的条件为 q->flag==1&&q->front==q->rear。

• 在循环队列中增加一个计数器 count，初始时 count=0;成功出队时 q->count减1，成功入队时 count 加1。因此，循环队列空的条件为 q->count==0。循环队列满的条件为 q->count==MAXSIZE，或者 q->count>0&&q->rear==q->front。

flag法

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
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 
#include 
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 
#include 
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！