初学队列Ⅱ

初学队列Ⅱ


队列的链式储存

队列的链式存储也称为链队列。为了便于操作,可给链队列添加一个头结点,并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同,且均指向头结点

队列链式储存的结构示意

以下代码实现的大概类似于一个带头结点的单向链表

用C语言表示大概是这样的:

1
2
3
4
5
6
7
8
9
10
11
struct qnode
{
int data;
struct qnode *next;
};
struct queue
{
struct qnode *front;
struct qnode *rear;
};

初始化队列

务必记得初始化!!

1
2
3
4
5
6
7
8
void init(struct queue *q)
{
q->front = (struct qnode*)malloc(sizeof(struct qnode));
q->rear = (struct qnode*)malloc(sizeof(struct qnode));
q->front = q->rear;
q->front->next = NULL;
return;
}

入队列操作

1
2
3
4
5
6
7
8
9
void push(struct queue *q,int num)
{
struct qnode *t = (struct qnode*)malloc(sizeof(struct qnode));
t->data = num;
t->next = NULL;
q->rear->next = t;
q->rear = t;
return;
}

出队列操作

变量 e 用来返回pop出来的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
int pop(struct queue *q,int *e)
{
struct qnode *t;
if(q->front == q->rear) //队列为空
return -1;
t = q->front->next;
*e = t->data;
q->front->next = t->next;
if(q->rear == t) //如果队尾就是队头,则删除之后rear指向front
q->rear = q->front;
free(t);
return 0;
}

创建一个队列

1
2
3
4
5
6
7
8
9
10
void create_queue(struct queue *q,int n)
{
int i,t;
for(i=0;i<n;i++)
{
scanf("%d",&t);
push(q,t);
}
return;
}

遍历输出队列内的元素

1
2
3
4
5
6
7
8
9
10
11
void print(struct queue *q)
{
while(1)
{
int e;
if(pop(q,&e)==-1) return;
printf("%d ",e);
}
printf("\n");
return;
}