C语言队列的插入与删除

#include <stdio.h>

#include <stdlib.h>

#define MAXQSIZE 100     //最大队列长度

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef struct

{

int *base

int front

int rear     //尾指针，若队列不空，指向队列尾元素的下一个位置

}SqQueue

void InitQueue(SqQueue *Q)

{

Q->front = Q->rear = 0

if (Q->base == NULL) {

Q->base = (int*)malloc(sizeof(int)* MAXQSIZE)

}

}

void DesQueue(SqQueue *Q) {

free(Q->base)

Q->base = NULL

Q->front = Q->rear = 0

}

int QueueLength(SqQueue *Q)

{

if (Q->base == NULL) return ERROR

return (Q->rear - Q->front + MAXQSIZE) % MAXQSIZE

}

void display(SqQueue *Q)

{

int i

if (Q->base == NULL) {

printf("\n ERROR ")

return

}

for (i = Q->front i != Q->rear i++) {

i = i % MAXQSIZE

printf("%3d", Q->base[i])

}

printf("\n")

}

int InQueue(SqQueue *Q, int e)

{

if (Q->base == NULL) return ERROR

if ((Q->rear + 1) % MAXQSIZE == Q->front)

return OVERFLOW

Q->base[Q->rear] = e

Q->rear = (Q->rear + 1) % MAXQSIZE

return OK

}

int DeQueue(SqQueue *Q, int m)

{

int i = 0

if (Q->base == NULL) return ERROR

if (Q->front == Q->rear)

return ERROR

while (i != m && Q->front != Q->rear)

{

printf("\n%dDeleted\n", Q->base[Q->front])

Q->front = (Q->front + 1) % MAXQSIZE

i++

}

if (i != m) {

printf("\n ERROR ")

return ERROR

}

return OK

}

void main()

{

int m, n, d, i

SqQueue Q = { 0, 0, 0 }

InitQueue(&Q)

printf("请输入要插入的元素个数：")

scanf("%d", &m)

printf("要插入的元素:")

for (i = 1 i <= m i++)

{

scanf("%d", &n)

InQueue(&Q, n)

}

printf("插入元素后,队列中的元素为:")

display(&Q)

printf("队列长度为:")

printf("%d\n", QueueLength(&Q))

printf("输入要删除的元素个数:")

scanf("%d", &d)

DeQueue(&Q, d)

printf("\n删除元素后，队列中元素为:")

display(&Q)

printf("\n")

DesQueue(&Q)

}

队列的插入 *** 作在队尾进行，而删除 *** 作在对头进行。每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除 *** 作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。

当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

顺序队列中的溢出现象：

（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

（2）"真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

（3）"假上溢"现象：由于入队和出队 *** 作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队 *** 作。该现象称为"假上溢"现象。

---