队列的基本操作(c语言版).doc

#include<stdio.h>
#include<stdlib.h>
typedef int elemType;

struct QueuePtr{
elemType data;
struct QueuePtr *next;
};
struct LinkQueue{
struct QueuePtr *front;
struct QueuePtr *rear;
};

void initQueue(struct LinkQueue *Q)
/*第一个操作构造一个空队列q*/
{
Q->front = Q->rear = NULL;
/* 把队首和队尾指针置空 */
return;
}

void push(struct LinkQueue *Q, elemType x)
/*第二个操作插入元素e为q的新的队尾元素 */
{
/* 得到一个由newP指针所指向的新结点 */
struct QueuePtr *newP;
newP = (struct QueuePtr*)malloc(sizeof(struct QueuePtr));
if(newP == NULL){
printf("内存空间分配失败！ ");
exit(1);
}
/* 把x的值赋给新结点的值域，把新结点的指针域置空 */
newP->data = x;
newP->next = NULL;
/* 若链队为空，则新结点即是队首结点又是队尾结点 */
if(Q->rear == NULL){
Q->front = Q->rear = newP;
}
else{
/* 若链队非空，则依次修改队尾结点的指针域和队尾指针，使之指向新的队尾结点 */
Q->rear = Q->rear->next = newP;
/*可以分两句话来写*/
}

}

elemType pop(struct LinkQueue *Q)
/*第三个操作队列不为空，则删除q的队头元素，用e返回其值，并返回ok； */
{
struct QueuePtr *p;
elemType temp;
/* 若链队为空则停止运行 */
if(Q->front == NULL){
printf("队列为空，无法删除！ ");
exit(1);
}
temp = Q->front->data;
/* 暂存队尾元素以便返回 */
p = Q->front;
/* 暂存队尾指针以便回收队尾结点 */
Q->front = p->next;
/* 使队首指针指向下一个结点 */
/* 若删除后链队为空，则需同时使队尾指针为空 */
if(Q->front == NULL){
Q->rear = NULL;
}
free(p); /* 回收原队首结点 */
return temp; /* 返回被删除的队首元素值 */
}
/*第四个操作返回队列头元素*/
elemType gettop(struct LinkQueue *Q)
{
/* 若链队为空则停止运行 */
if(Q->front == NULL){
printf("队列为空，无法删除！ ");
exit(1);
}
return Q->front->data;
/* 返回队首元素 */
}
/*第五个操作判断队列是否为空*/
int emptyQueue(struct LinkQueue *Q)
{
/* 判断队首或队尾任一个指针是否为空即可 */
if(Q->front == NULL){
printf("asd");
return 0;
}
else{
printf("dfg");
return 1;
}
}
/*第六个操作清空队列*/
void clearQueue(struct LinkQueue *Q)
{
struct QueuePtr *p = Q->front;
/* 队首指针赋给p */
/* 依次删除队列中的每一个结点，最后使队首指针为空 */
while(p != NULL){
Q->front = Q->front->next;
free(p);
p = Q->front;
} /* 循环结束后队首指针已经为空 */
Q->rear = NULL;
printf("\n队列已经清空\n");
return;
}

int main()
{
struct LinkQueue Q;

int i;
int a,b,c,d;
a=b=c=d=0;
// initQueue(&q);
while(1)
{
printf("\n每种方法都对应一个编号，输入编号进行相应的操作。\n");
printf("1--操作initQueue构造一个队列Q\n");
printf("2--操作gettop返回队列顶元素e\n");
printf("3--操作enQueue插入元素e到队里尾部\n");
printf("4--操作pop删除Q队列的首元素\n");
printf("5--操作clearQueue将Q清为空队列 \n");
printf("6--操作emptyQueue判断Q是否为空队列，是返回0，否返回1；\n");
printf("7--退出程序\n");
printf("请选择一个基本操作：");
scanf("%d",&a);

switch(a)
{
case 1:initQueue(&Q);break;
case 2:
c=0;
c=gettop(&Q);
printf("\n队列头元素是%d\n",c);
break;
case 3:
printf("\n请输入一个要插入队列的元素：");
scanf("%d",&b);
push(&Q,b);break;
case 4:
c=pop(&Q);
printf("\n删除的元素是%d\n",c);
break;
case 5:
clearQueue(&Q);
break;
case 6:
d=emptyQueue(&Q);
printf("\n队列是%d 0是空，1是非空\n",d);
break;
case 7:
goto quit;
default:printf("请输入1-6之间的数字。\n");

}

}
quit:
system("pause");
}