当前位置 : 主页 > 编程语言 > c语言 >

数据结构-->队列

来源:互联网 收集:自由互联 发布时间:2023-09-07
朋友们,感谢你们到访本人博客!!现在我将为大家介绍队列!! 那么什么是队列呢? --- 队列 : 只允许在一端进行插入数据的操作,在另一端进行删除数据的操作; 队列遵循 先进先

朋友们,感谢你们到访本人博客!!现在我将为大家介绍队列!!

那么什么是队列呢?

---> 队列只允许在一端进行插入数据的操作,在另一端进行删除数据的操作;队列遵循 先进先出 原则! 同时,队头是指 插入数据的一端,而队尾是指 删除数据的一端!!

为了方便形象化的理解,特此附上图示样解  ::>

数据结构-->队列_单链表

而我们如何实现队列,会更加优化一些呢!!答案是 用单链表 

前段时间,学习的链表如今就派上用场了!!至此,特别强调一下,前几期的链表博客有部分错误,现已修正好了,对好友而言感到十分抱歉!!毕竟本人也是刚刚学习数据结构!!


OK ! 让我们开始动手书写代码吧!!

头文件  “Queue.h”

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int QDataType;

typedef struct QueueNode
{
  QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
  QNode* tail;
  int size;
}Queue;

//初始化
void QInitial(Queue* pq);

//销毁
void QDestroy(Queue* pq);

//入队列
void QPush(Queue* pq, QDataType x);

//出队列
void QPop(Queue* pq);

//队列头部元素
QDataType QFront(Queue* pq);

//队列尾部元素
QDataType QBack(QNode* pq);

//对列元素个数
void Queueize(Queue* pq);

//布尔判空
bool QEmpty(Queue* pq);

实现环节 “Queue.c”

#include "Queue.h

//初始化
void QInitial(Queue* pq)
{
	pq ->head = NULL;
  pq ->tail = NULL;
  pq ->size = 0;
}

//销毁
void QDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq ->head;
  while(cur)
  {
		QNode* next = pq ->head ->next;
    free(pq ->head);
    cur = next;
  }
  
  pq ->head = NULL;
}

//入队列
void QPush(Queue* pq, QDataType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if(newnode == NULL)
  {
  	perror("malloc::fail");
    return ;
  }
  
  newnode ->data = x;
  newnode ->next = NULL;
  
  if(pq ->head == NULL)
  {
  	assert(pq ->tail == NULL);
    pq ->head = pa ->tail = NULL;
  }
  else
  {
    pq ->tail ->next = newnode;
    pq ->tail = newnode;
  }
  pq ->size++;
}

//出队列
void QPop(Queue* pq)
{
  assert(pq);
  if(pq ->head ->next == NULL)
  {
  	free(pq ->head);
    pq ->head = NULL;
  }
  else
  {
  	QNode* next = pq ->head ->next;
    free(pq ->head);
    pq ->head = NULL;
    pq ->head = next;
  }
  pq ->size--;
}

//队列头部元素
QDataType QFront(Queue* pq)
{
	assert(pq);
  
  return pq ->head ->data;
}

//队列尾部元素
QDataType QBack(QNode* pq)
{
	assert(pq);
  
  return pq ->tail ->data = NULL;
}

//对列元素个数
QDataType Queueize(Queue* pq)
{
	assert(pq);
  
  return pq ->size;
}

//布尔判空
bool QEmpty(Queue* pq)
{
	assert(pq);
  
  return pq ->size == 0;
}

测试环节 “Test.c”

#include "Queue.h"

int main()
{
  Queue q;
  
  QInitial(&q);
  QPush(&q, 21);
  QPush(&q, 24);
  QPush(&q, 27);
  QPush(&q, 23);
  QPush(&q, 22);
  
  while(!QEmpty(&q))
  {
    printf("%d ", QFront(&q));
    QPop(&q);
  }
  
  QDestroy(&q);
	return 0;
}





头文件 “Queue.h”

数据结构-->队列_队列_02

测试环节 “Test.c”

数据结构-->队列_队列_03

实现环节 “Queue.c”


数据结构-->队列_单链表_04


如此,我们的队列就已经设计好了!!

不过,仍然需要我们注意几点 :>




首先, 是关于指针 QNode 的二次分装,这其实是一个规范写法,更容易让逻辑清晰与严谨,防止出错!!

如果,我们不分装 QNode 指针 ,这会让我们再传指针时候,会更加的难以展开逻辑!!而且极易不好把控

因此,强烈建议按照上面的书写,方便实现队列,还是单链表式的队列!!

再者,入队列的操作,有些精华所在!!容易忽视一些情况!!而这,更能体现出一名程序员的代码素养!

好了,老友们!!今天的队列博客就到这里了!!下一期,我们将共同展开栈和队列的有关OJ题训练!!

感谢阅读!!敬请期待!!


上一篇:C++11 - 正则表达式
下一篇:没有了
网友评论