005-数据结构和算法-链式队列
2020-04-15 本文已影响0人
沉默Coder
上一章我们讨论了队列的顺序存储的实现,这一章我们换一种方式来实现队列
链式队列实现
我们再次强调,队列只是一种逻辑结构,是一种“先进先出”的线性表,所以和线性表一样,我们可以采用:
-顺序存储
-链式存储
的方式来实现队列。
这一章我们重点讲解如何使用链式存储的方式实现一个队列,如果对顺序存储方式实现不清楚的可以查看一下这篇文章 队列的顺序实现;
一些提前定义的变量和结构体:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int Element; /* Element类型根据实际情况而定,这里假设为int */
//定义节点
typedef struct SqNode
{
Element data;
struct SqNode * next;
} SqNode;
//定义队列,实际我们只需要使用定义队头和队尾指针
typedef struct
{
SqNode *front, *rear;
}SqQueue;
创建队列,我们这里使用一个头节点来标记队列的队头,头节点不存储数据,只是为了方面后续的操作
/// 初始化队列,创建队列中链表的头节点
Status InitQueue(SqQueue * Q)
{
Q->front = Q->rear = (SqNode *)malloc(sizeof(SqNode));
if (Q->front == NULL) {
return ERROR;
}
Q->front->next = NULL;
return OK;
}
///销毁队列,头节点也需要销毁
Status destroyQueue(SqQueue * Q)
{
//已经在销毁队列了,所以认为Q->rear已经失去了存在的意义,所以这里用Q->rear来标记Q->front的下一个节点
while (Q->front) {
Q->rear = Q->front->next;
Q->front->next = NULL;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
/// 清空队列,保留头节点
Status clearQueue(SqQueue *Q)
{
if(Q->front == Q->rear) return OK;
SqNode *p,*k;
p = Q->front->next;
Q->rear = Q->front;
Q->front->next = NULL;
while (p) {
k = p->next;
free(p);
p = k;
}
return OK;
}
/// 队列是否为空,如果队头和队尾指针指向了同一个元素,则表示该队列为空队列
Status isQueueEmpty(SqQueue Q)
{
return Q.front == Q.rear;
}
///队列的长度
Status queueLength(SqQueue Q)
{
int i = 0;
SqNode *p = Q.front->next;
while (p) {
i++;
p = p->next;
}
return i;
}
/// 元素入队,
Status inQueue(SqQueue *Q,Element e)
{
if(Q->front == NULL) return ERROR;
SqNode * node = (SqNode *)malloc(sizeof(SqNode));
if(node == NULL) return ERROR;
node->data = e;
node->next = NULL;
//将新元素添加到队尾
Q->rear->next = node;
//将队尾指针指向最后一个位置
Q->rear = node;
return OK;
}
/// 出队
Status outQueue(SqQueue *Q, Element *e)
{
//判断队列是否y为空
if(Q->rear == Q->front) return ERROR;
SqNode * s = Q->front->next;
Q->front->next = s->next;
*e = s->data;
s->next = NULL;
//判断弹出的元素是不是在队尾,如果是,则需要将队尾指针指向对头,否则释放后,Q->rear将是野指针
if(Q->rear == s) Q->rear = Q->front;
free(s);
return OK;
}
/// 获取对头元素
Status getHead(SqQueue Q,Element *e)
{
//判断队列是否为空
if(Q.rear == Q.front) return ERROR;
*e = Q.front->next->data;
return OK;
}
///打印队列元素
void printQueue(SqQueue Q)
{
if(Q.front == Q.rear) return;
SqNode * p = Q.front->next;
printf("队列元素:");
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
测试
int main(int argc, const char * argv[]) {
// insert code here...
Status iStatus;
Element d;
SqQueue q;
//1.初始化队列q
iStatus = InitQueue(&q);
//2. 判断是否创建成
if (iStatus) {
printf("成功地构造了一个空队列\n");
}
//3.判断队列是否为空
printf("是否为空队列?%d (1:是 0:否)\n",isQueueEmpty(q));
//4.获取队列的长度
printf("队列的长度为%d\n",queueLength(q));
//5.插入元素到队列中
inQueue(&q, -3);
inQueue(&q, 6);
inQueue(&q, 12);
printf("队列的长度为%d\n",queueLength(q));
printf("是否为空队列?%d (1:是 0:否)\n",isQueueEmpty(q));
//6.遍历队列
printQueue(q);
//7.获取队列头元素
iStatus = getHead(q, &d);
if (iStatus == OK) {
printf("队头元素是:%d\n",d);
}
//8.删除队头元素
iStatus =outQueue(&q, &d);
if (iStatus == OK) {
printf("删除了的队头元素为:%d\n",d);
}
//9.获取队头元素
iStatus = getHead(q, &d);
if (iStatus == OK) {
printf("新的队头元素为:%d\n",d);
}
//10.清空队列
clearQueue(&q);
//11.销毁队列
destroyQueue(&q);
return 0;
}
结果输出:
测试结果