【C语言 数据结构】队列 - 链式、顺序

时间：2022-11-19 07:55:32



文章目录

  • ​​队列 - 链式、顺序​​
  • ​​一、概念​​
  • ​​1.1 队列的定义​​
  • ​​1.2 队列的初始化​​
  • ​​1.3 队列的销毁​​
  • ​​1.4 队列的判空​​
  • ​​1.5 队列的尾插​​
  • ​​1.6 队列的头删​​
  • ​​1.7 取队头、取队尾​​
  • ​​1.8 获取队列的元素个数​​
  • ​​1.9 打印队列​​
  • ​​二、循环队列 - 顺序​​

队列 - 链式、顺序

一、概念

1.和栈不同的是，队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端进行删除操作

  • 队尾：允许插入的一端
  • 队头：允许删除的一端

2.在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。

  • 基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。

3.队列采用的 FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

1.1 队列的定义

// 定义队列数据类型
typedef int QDataType;
// 定义队列节点
typedef struct QueueNode{
 struct QueueNode* next; // 节点link
 QDataType data; // 节点数据
}QNode;
// 定义队列
typedef struct Queue{
 QNode* head; // 定义头指针
 QNode* tail; // 定义尾指针
}Queue;

​​返回顶部​​

1.2 队列的初始化

// 队列初始化
void QueueInit(Queue* pq){
 assert(pq); // 断言
 pq->head = pq->tail = NULL; // 置空
}

​​返回顶部​​

1.3 队列的销毁

// 队列的销毁
void QueueDestroy(Queue* pq){
 assert(pq); // 断言
 QueueNode* cur = pq->head; // 定义临时节点遍历 
 while (cur){
  // 保存下一个节点的地址
  QueueNode* next = cur->next;
  // 释放空间
  free(cur);
  // 指向下一个节点
  cur = next;
 }
 // 置空
 pq->head = pq->tail = NULL;
}

​​返回顶部​​

1.4 队列的判空

// 队列的判空
int QueueIsEmpty(Queue* pq){
 assert(pq); // 断言
 return pq->tail == NULL;
}

​​返回顶部​​

1.5 队列的尾插

// 对列的插入
void QueuePush(Queue* pq,QDataType x){
 // 断言
 assert(pq);
 // 创建新的队列节点
 QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
 if(newNode == NULL){
  printf("创建空间失败！");
      exit(-1);
 }
 // 节点赋值
 newNode->data = x;  
 newNode->next = NULL;
 // 如果是空队列
 if(pq->head==NULL){
    // 当前节点作为队列的第一个元素节点
    pq->head = pq->tail = newNode;
 }else {
   // 如果不是空队列那么，上一个节点的link指向newNode，且将尾指针指向新节点
    pq->tail->next = newNode;
    pq->tail = newNode;
 }
}

​​返回顶部​​

1.6 队列的头删

// 队列的头删 
void QueueHeadPop(Queue* pq){
  // 断言
  assert(pq);
  // 判空
  assert(!QueueIsEmpty(pq));
  // 如果不是空，只允许头删，那么就是将头指针后一个节点即可
  QueueNode* next = pq->head->next;
  free(pq->head);  // 释放当前head指向的节点 - 删除的头节点
  pq->head = next; // 头指针后移

  // 判空,如果删完了,不能再删了
  if(pq->head ==NULL){
    pq->tail = NULL;
  }

}

​​返回顶部​​

1.7 取队头、取队尾

// 取队头
QDataType QueueFront(Queue* pq){
  // 断言
  assert(pq);
  // 判空
  assert(!QueueIsEmpty(pq));
  return pq->head->data;
}

// 取队尾
QDataType QueueBack(Queue* pq){
  // 断言
  assert(pq);
  // 判空
  assert(!QueueIsEmpty(pq));
  return pq->tail->data;
}

​​返回顶部​​

1.8 获取队列的元素个数

// 获取队列的元素个数
int QueueLength(Queue* pq){
  // 断言
  assert(pq);
  int i = 0; // 计数
  QueueNode* curr = pq->head;
  // 遍历
  while(curr){
    i++; 
    curr = curr->next;
  }
  return i;
}

​​返回顶部​​

1.9 打印队列

// 打印队列
void QueuePrint(Queue* pq){
  // 断言 
  assert(pq);
  // 判空
  assert(!QueueIsEmpty(pq));
  // 创建临时节点
  QueueNode* curr = pq->head;
  // 遍历
  while(curr){
    printf("%d->",curr->data); 
    curr = curr->next;
  }
}

​​返回顶部​​

二、循环队列 - 顺序

【C语言 数据结构】队列 - 链式、顺序

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

在循环队列中，当队列为空时，有​​front=rear​​，而当所有队列空间全占满时，也有​​front=rear​​。为了区别这两种情况，规定循环队列最多只能有​​MaxSize-1​​个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。

因此，队列判空的条件是​​front=rear​​，而队列判满的条件是​​front=（rear+1)%MaxSize​​。

#define _CRT_SECURE_NO_WARNINGS
#include<malloc.h>
#include<stdio.h>
#include<assert.h>
#define  MAX_SIZE  6

typedef char CQDataType;
typedef struct {
    CQDataType *base;
    int front;   // 头
    int rear;    // 尾
} SqQueue;

// 队列初始化
void InitQueue(SqQueue* Q){
    Q->base= (CQDataType*)malloc(MAX_SIZE*sizeof(CQDataType));
    if (Q->base== NULL) exit(-1);
    Q->front = 0;
    Q->rear = 0;
}
 //入队元素
void PushQueue(SqQueue* Q, CQDataType data)  {
    assert(Q); // 断言
    // 队满
    if ((Q->rear + 1) % MAX_SIZE == Q->front)   {
        printf("full!");
        exit(-1);
    }
    Q->base[Q->rear] = data;//当前尾指针处添加数据
    Q->rear = (Q->rear + 1) % MAX_SIZE;//尾指针向前移动
}
//出队元素
void PopQueue(SqQueue* Q, int* e)    {
    assert(Q); // 断言
    if (Q->front == Q->rear){
        printf("empty");
        exit(-1);
    }
    *e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE; //头指针向前移动
}


// 求当前队列长度
int queueLength(SqQueue* Q) {
    assert(Q); // 断言
    return ((Q->rear) - (Q->front) + MAX_SIZE) % MAX_SIZE;
} 

// 输出队列中的数据元素 
int PrintQueue(SqQueue* Q){
    assert(Q); // 断言
    if (Q->rear == Q->front){
        printf("当前队列为空队列\n");
    }
    while (Q->front != Q->rear){
        printf("该队列的第%d个的值为:%c\n", Q->front, Q->base[Q->front]);
        Q->front = (Q->front + 1) % MAX_SIZE;
    }
    return 0;
}

int main() {
    SqQueue Q;
    InitQueue(&Q);
    PushQueue(&Q, 'A');
    printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
    PushQueue(&Q, 'B');
    printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
    PushQueue(&Q, 'C');
    printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
    PushQueue(&Q, 'D');
    printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
    PushQueue(&Q, 'E');
    printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
    PushQueue(&Q, 'F');
    printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
    // 输出队列
    PrintQueue(&Q);

    system("pause");
    return 0;
}

【C语言 数据结构】队列 - 链式、顺序

​​返回顶部​​


标签：

相关文章