队列

9/1/2023
阅读时间 2 分钟

在实际生活中队列的用处随处可见，只要是排队的地方都会出现这样的结构

队列和栈差不多都是对于数据的存和取有严格要求的线性结构

和栈结构与所不同的是，队列是两端开口，要求数据从一端进，必须要从另一端出

通常我们将进数据的一段称为“队尾”，出数据的一段称为“队头”，数据元素进队列的过程称为“入队”，出队列的过程称为“出队”。而且队列要遵守先进先出的原则。

队列和栈一样也拥有两种实现方式：

顺序队列：在顺序表的基础上实现队列结构；
链队列：在链表的基础上实现队列；

顺序队列

简单实现

由于顺序队列的底层使用的是数组，因此需要预先审批一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们就需要定义两个指针top和rear分别用于指向队尾元素和队头元素。

这是一开始我们创建顺序队列时两个指针都指向同一个位置

这是开始后输入数据随着数据增加rear指针指队头。

这是输出时数据的走向。

#include <stdio.h>
int enQueue(int * a, int rear, int data){
  a[rear++]=data;
  return rear;
}
void deQueue(int * a, int top, int rear){
  while(front!=rear){
    printf("出队元素：%d\n",a[top++]);
  }
}
int main(){
  int a[100];
  int top,rear;
  top=rear=0;
  rear=enQueue(a,rear,1);
  rear=enQueue(a,rear,2);
  rear=enQueue(a,rear,3);
  rear=enQueue(a,rear,4);
  deQueue(a,top,rear);
  return 0;  
}

此方法是存在缺陷的，我们看上面的图片，就不难看出这样的顺序队列会造成大量的资源浪费，顺序队列使用过的地方也必能再用，而顺序队列自己也不会再往回走了，造成了整体后移的效果。如果申请的空间不足就会造成溢出产生错误。

循环队列

说白了就是将上面的方法进行改进使他成为一个圆环。其实这只是一个想象图，我们完全没有必要真的是新这样一种结构，还用之前的程序，我们做一些小小的修改。

#include <stdio.h>
#define max 5
int enQueue(int * a, int top, int rear, int data){
  if((rear+1)%max==top){
    printf("空间已满");
    return rear;
  }
  a[rear%max]=data;
  rear++;
  return rear;
}
int deQueue(int * a, int top, int rear){
  if(top==rear%max){
    printf("队列为空");
    return top;
  }
  printf("%d",a[top]);
  top=(top+1)%max;
  return top;
}
int main(){
  int a[max];
  int top, rear;
  top=rear=0;
  rear=enQueue(a,top,rear,1);
  rear=enQueue(a,top,rear,2);
  rear=enQueue(a,top,rear,3);
  rear=enQueue(a,top,rear,4);
  top=deQueue(a,top,rear);
  rear=enQueue(a,top,rear,5);
  top=deQueue(a,top,rear);
  rear=enQueue(a,top,rear,6);
  top=deQueue(a,top,rear);
  top=deQueue(a,top,rear);
  top=deQueue(a,top,rear);
  top=deQueue(a,top,rear);
  return 0;
}

使用此方法需要注意：

当队列为空时队列头指针等于队列尾指针；
当数组满员时队列头指针等于队列尾指针；

链队列

说白了就是用链式存储结构实现队列的存取。

typedef struct QNode{
  int data;
  struct QNode * next;
}QNode;
QNode * initQueue(){
  QNode * queue= (QNode*)malloc(sizeof(QNode));
  //对头结点进行初始化
  queue->next=NULL;
  return queue;
}

入队

QNode * enQueue(QNode * rear, int data){
  //
  QNode * enElem=(QNode*)malloc(sizeof(QNode));
  enElem->data=data;
  enElem->next=NULL;
  rear->next=enElem;
  rear=enElem;
  return rear;
}

出队

void deQueue(QNode * top, QNode * rear){
  if(top->next==NULL){
    printf("队列为空");
    return rear;
  }
  QNode * p=top->next;
  printf("%d",p->data);
  top->next=p->next;
  if(rear==p){
    rear=top;
  }
  free(p);
}

#include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
  int data;
  struct QNode * next;
}QNode;
QNode * initQueue(){
  QNode * queue =(QNode*)malloc(sizeof(QNode));
  queue->next=NULL;
  return queue;
}
QNode * enQueue(QNode * rear, int data ){
  QNode * enElem=(QNode*)malloc(sizeof(QNode));
  enElem->data=data;
  enElem->next=NULL;
  rear->next=enElem;
  rear=enElem;
  return rear;
}
QNode * deQueue(QNode * top, QNode * rear){
  if(top->next==NULL){
    printf("\n队列已空");
    return rear;
  }
  QNode * p=top->next;
  printf("%d",p->data);
  top->next=p->next;
  if(rear==p){
    rear=top;
  }
  free(p);
  return rear;
}
int main(){
  QNode * queue,* top, *rear;
  queue=top=rear=initQueue();
  rear=enQueue(rear,1);
  rear=enQueue(rear,2);
  rear=enQueue(rear,3);
  rear=enQueue(rear,4);
  rear=deQueue(top,rear);
  rear=deQueue(top,rear);
  rear=deQueue(top,rear);
  rear=deQueue(top,rear);
  rear=deQueue(top,rear);
  return 0;
}

Posts in this Series

基础操作算法与数据结构，C语言进阶