数据结构(队列)

简介: 数据结构(队列)

1.队列的概念和结构

概念:队列是一种线性表,它只能从一端插入数据,从另一端删除数据,在插入数据的一端称为队头,在删除数据的一端称为队尾。队列遵循先进先出的原则。

生动形象一点就跟我们日常排队一样,先排的人先走,后排的人后走。

结构如图:

91619b6f210d4deda3d39a354515c8cc.png

2.队列的实现

队列的实现建议使用链表来实现,因为如果用数组的话出队列要调整数组,比较麻烦,而使用链表实现就可以避免这个问题。

实现过程如图:

1fb84e451a6549ada3bb41031f3860cc.png

队列的头文件:

// 链式结构:表示队列 
typedef int QDataType;
typedef struct QListNode
{
  struct QListNode* _next;
  QDataType _data;
  
}QNode;
 
// 队列的结构 
typedef struct Queue
{
  QNode* _phead;
  QNode* _ptail;
  int size;
}Queue;
 
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);


初始化队列:

void QueueInit(Queue* q)
{
  q->_phead = q->_ptail = NULL;
  q->size = 0;
}


队尾入队列:

void QueuePush(Queue* q, QDataType data)
{
  if (q->_phead == NULL)
  {
    QNode* node = (QNode*)malloc(sizeof(QNode));
    node->_data = data;
    node->_next = NULL;
    q->_phead = q->_ptail=node;
    q->size++;
  }
  else
  {
    QNode* node = (QNode*)malloc(sizeof(QNode));
    node->_data = data;
    node->_next = NULL;
    q->_ptail->_next = node;
    q->_ptail = node;
    q->size++;
  }
}


队头出队列:

void QueuePop(Queue* q)
{
  QNode* node = q->_phead->_next;
  free(q->_phead);
  q->_phead = node;
  q->size--;
}


获取队列头部元素:

QDataType QueueFront(Queue* q)
{
  return q->_phead->_data;
}


获取队列队尾元素:

QDataType QueueBack(Queue* q)
{
  return q->_ptail->_data;
}


获取队列中有效元素个数:

int QueueSize(Queue* q)
{
  return q->size;
}


检测队列是否为空,如果为空返回非零结果,如果非空返回0:

int QueueEmpty(Queue* q)
{
  if (q->size == 0)
    return 0;
  else
    return 1;
}


销毁队列:

void QueueDestroy(Queue* q)
{
  if (q->_phead == q->_ptail)
  {
    free(q->_phead);
    q->_phead = q->_ptail = NULL;
    q->size--;
  }
  else
  {
    QNode* node = q->_phead->_next;
    free(q->_phead);
    q->_phead = node;
    q->size--;
  }
}


目录
相关文章
|
20天前
|
存储 Java 容器
深入浅出 栈和队列(附加循环队列、双端队列)
深入浅出 栈和队列(附加循环队列、双端队列)
|
3天前
数据结构——栈和队列
数据结构——栈和队列
7 1
|
13天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现(两个方式实现)
【数据结构】栈和队列的模拟实现(两个方式实现)
|
21天前
|
算法 Java
Java数据结构——队列
Java数据结构——队列
29 4
|
2天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
2天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
12 4
|
3天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
6天前
|
算法 调度 Python
数据结构与算法-队列篇
数据结构与算法-队列篇
12 3
|
6天前
数据结构初阶 队列
数据结构初阶 队列
7 0
|
11天前
|
算法
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
13 0