队列

概念

是一种只能在表尾进行插入，表头进行删除操作的特殊线性表

1. 使用顺序存储结构

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

/*队列的基本操作就是入队和出队
入队：从队列尾部插入
出队： 从队列头部删除
FIFO
*/
#define CAPACITY 100
typedef int DataType;
typedef struct SeqQueue
{
   int front; // 头索引
   int rear;  //尾部索引
   int size;  //当前长度
   unsigned capacity; //最大容量
   DataType * data;


} Queue;

// 初始化队列

void Initialize(Queue * q)
{
   q->capacity = CAPACITY;
   q->front = q->size = 0;
   q->rear = q->capacity - 1;
   q->data = (DataType *)malloc(sizeof(DataType)*CAPACITY);

}

// 判断队列是否为空
bool IsEmpty(Queue * q)
{
   if (q->size == 0)
       return true;
   else
       return false;
}

//判断队列是否为满
bool IsFull(Queue *q)
{
   if(q->size == q->capacity)
       return true;
   else
       return false;
}

//入队操作
void Enqueue(Queue * q,DataType item)
{
   if(IsFull(q))
       return;
   q->rear = (q->rear + 1) % q->capacity;
   q->data[q->rear] = item;
   q->size++;
   printf("%d enqueued to queue\n",item);
   printf("size = %d\n",q->size);
}

//出队操作
DataType Dequeue(Queue * q)
{

   if (IsEmpty(q))
       return ;

   DataType item;
   item = q->data[q->front];
   q->front = (q->front + 1) % q->capacity;
   q->size--;
   printf("%d \n",q->size);
   printf("%d dequeue \n",item);
   return item;
}

DataType front (Queue * q)
{
   if (IsEmpty(q))
       return NULL;
   return q->data[q->front];
}
DataType rear(Queue * q)
{
   if (IsEmpty(q))
       return NULL;
   return q->data[q->rear];
}

int main(void)
{
   Queue queue;
   Initialize(&queue);
   Enqueue(&queue,10);
   Enqueue(&queue,20);
   Enqueue(&queue,30);
   Enqueue(&queue,40);

   Dequeue(&queue);
   Dequeue(&queue);
   printf("Front item is %d\n",front(&queue));
   printf("Rear item is %d\n",rear(&queue));
   return 0;
}

2. 使用链式存储

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

//定义结点
typedef int DataType;
typedef struct node
{
    DataType data;
    struct node * next;
}Node;

typedef struct queue
{
    Node * front;
    Node * rear;
}Queue;

//初始化队列
void Initialize(Queue * q)
{
    q->front = q->rear = NULL;
}
//创建一个新结点
Node * newNode(DataType x)
{
    Node * temp = (Node*)malloc(sizeof(Node));
    if(temp == NULL)
        return NULL;
    temp->data = x;
    temp->next = NULL;
    return temp;
}

//入队
void EnQueue(Queue * q,DataType x)
{
    Node * temp = newNode(x);
    if (temp == NULL)
       {
           printf("memory alloctated failed.\n");
           exit(1);
           }
    if(q->rear == NULL)
    {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;


}

//出队
Node * DeQueue(Queue * q)
{
    if (q->front == NULL)
        return NULL;
    Node * temp = q->front;
    q->front = q->front->next;

    if(q->front == NULL)
        q->rear = NULL;
    return temp;
}

//Driver Program to test anove functions

int main(void)
{
    Queue q;
    Initialize(&q);
    EnQueue(&q,10);
    EnQueue(&q,20);
    DeQueue(&q);
    DeQueue(&q);
    EnQueue(&q,30);
    EnQueue(&q,40);
    EnQueue(&q,50);
    Node * item = DeQueue(&q);
    if (item != NULL)
        printf("Dequeued item is %d",item->data);
    return 0;
}