[数据结构与算法]链队列的入队出队-----数据结构与算法笔记

一、队列

参考书：《数据结构（C语言）》–严蔚敏等编著，清华大学出版社。

1、链队列

队列和栈恰恰相反，队列是一种先进先出的结构(FIFO)，它也是一种线性表，也有两种存储结构：链队列和顺序循环队列。
队列只允许在表的一端插入，只允许在另一端删除。和我们平常排队是一个模样，允许插入（入队）的一端叫队尾，允许删除（出队）的一端叫队头，表示图如下：

而在实际情况当中，我们将表写成下面这样：

链队列定义了队头指针和队尾指针，所以判空队列标志在于：Q.front == Q.rear;
并且：

当队为空时，入队会改变头和尾指针；
当队非空时，入队只会改变尾指针；

相关代码：

#include "stdio.h"
#include "stdlib.h"
#define OK		1
#define ERROR	0
#define TRUE	1
#define FALSE	0
#define OVERFLOW	-2

typedef int Status;
typedef char QElemType;
typedef struct QNode {
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct {
	QueuePtr front;	//队头指针 
	QueuePtr rear;	//队尾指针 
}LinkQueue;

Status InitQueue(LinkQueue &Q);
//构造一个空队列Q 
Status InitQueue(LinkQueue &Q) {
	Q.front = Q.rear = new QNode;
	if(!Q.front) exit(OVERFLOW);
	Q.front->next = NULL;	//将Q.front(Q.rear同)指向NULL 
	return OK;
}

Status EnQueue(LinkQueue &Q,QElemType e);
//入队，e为Q的新的队尾元素
Status EnQueue(LinkQueue &Q,QElemType e) {
	QueuePtr p;
	p = new QNode;
	if(!p) exit(OVERFLOW);
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;	//Q.rear所指向的是队尾，入队的元素在队尾，所以将Q.rear的next指向p 
	Q.rear = p;			//更新Q.rear队尾指针指向队尾元素p 
	return OK;
} 

Status DeQueue(LinkQueue &Q,QElemType &e);
//出队，用e返回其值，删除队头节点
Status DeQueue(LinkQueue &Q,QElemType &e) {
	if(Q.front == Q.rear) return ERROR;
	QueuePtr p;
	p = Q.front->next;	//Q.front所指向的是队头，所以将队头交给p(待删除的) 
	e = p->data;
	Q.front->next = p->next;
	if(Q.rear == p) Q.rear = Q.front;	//若只有一个元素出队，那么出队后就是空队列
	free(p);
	return OK; 
} 

Status QueueDisPlay(LinkQueue &Q);
//打印最终的队列的元素
Status QueueDisPlay(LinkQueue &Q) {
	if(Q.front == Q.rear) return ERROR;
	QueuePtr p;
	p = Q.front->next;	//将Q.front所指向的头结点交给p
	while(p){
		if(p->next != NULL)
			printf("%c,",p->data);
		else {
			printf("%c",p->data);
		}
		p = p->next;
	} 
} 

int main(void) {
	LinkQueue Q;
	InitQueue(Q);
	QElemType ch;
	char e;
	printf("请输入入队元素(可分段输入(输入最后一段Enter后按Ctrl+Z))：\n"); 
	while((ch=getchar()) != EOF){
		if(ch == '\n')
			continue;
		else
			EnQueue(Q,ch);
	}
	DeQueue(Q,e);
	printf("整个队列队头元素为：%c\n",e);
	printf("剩余队列元素依次为：\n");
	QueueDisPlay(Q); 
	
	return 0;
} 

/*
输入:abc
    def
输出:a
    bcdef

输入:e
    aegt
输出:e
    aegt
*/