概念
是一种只能在表尾进行插入,表头进行删除操作的特殊线性表
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;
}
网友评论