数据结构（C语言）-线性表之队列（顺序队列、链式队列）-学习笔记04

• 1. 基本介绍
• 2. 顺序队列
• • 2.1 定义 sequeue.h
  • 2.2 sequeue.c
• 3. 链式队列
• • 3.1 定义 linkqueue.h
  • 3.2 linkqueue.c

• 队列是限制在一端进行插入和另一端进行删除操作的线性表
• 允许进行存入操作的一端是队尾
• 允许进行删除操作的是队头
• 没有元素时是空队
• 先进先出

#define N 128

typedef int data_t;

typedef struct{
	data_t data[N];
	int front, rear;
}sequeue;

sequeue *sequeue_create(); //创建队列
int sequeue_enqueue(sequeue *sq, data_t x);//入队
data_t sequeue_dequeue(sequeue *sq);//出队
int sequeue_empty(sequeue *sq);//判断队是否为空
int sequeue_full(sequeue *sq);//判断队是否已满
int sequeue_clear(sequeue *sq);//清空队列数据
sequeue *sequeue_free(sequeue *sq);//释放队列空间

• front是队头，rear是队尾指向的空位置，初始化的时候都是指向0

#include 
#include 
#include 
#include "sequeue.h"

sequeue *sequeue_create(){
	sequeue *sq;
	if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL){
		return NULL;
	}
	memset(sq->data, 0, sizeof(sq->data));
	sq->front = sq->rear = 0;
	return sq;
}

int sequeue_enqueue(sequeue *sq, data_t x){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	if ((sq->rear+1)%N == sq->front){
		printf("sqeueue is fulln");
		return -1;
	}
	sq->data[sq->rear] = x;
	sq->rear = (sq->rear+1) % N;
	return 0;
}

data_t sequeue_dequeue(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	data_t data;
	data = sq->data[sq->front];
	sq->front = (sq->front+1)%N;
	return data;
}

int sequeue_empty(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	return sq->front == sq->rear;
}

int sequeue_full(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	return (sq->rear+1)%N == sq->front;
}

int sequeue_clear(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	sq->front = sq->rear = 0;
	return 0;
}

sequeue *sequeue_free(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return NULL;
	}
	free(sq);
	sq = NULL;
	return NULL;
}

• 插入在队尾进行，删除操作在队头进行，由队头指针和队尾指针控制队
  
• 空队如下图所示
  

先定义一个结点，在定义一个队列，队列的front指向头结点，队列的rear指向链表的最后一个元素

typedef int data_t;

typedef struct node{
	data_t data;
	struct node *next;
}listnode, *linklist;

typedef struct {
	linklist front;
	linklist rear;
}linkqueue;

linkqueue *create();
int enqueue(linkqueue *lq, data_t x);
data_t dequeue(linkqueue *lq);
int empty(linkqueue *lq);
int clear(linkqueue *lq);
linkqueue *queue_free(linkqueue *lq);

#include 
#include 
#include "linkqueue.h"

linkqueue *create(){
	linkqueue *lq;
	lq = (linkqueue *)malloc(sizeof(linkqueue));
	if (lq == NULL)
		return NULL;
	lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
	if (lq->front == NULL)
		return NULL;

	lq->front->next = NULL;
	lq->front->data = 0;
	return lq;
}

int enqueue(linkqueue *lq, data_t x){
	linklist p;
	if ((p = (linklist)malloc(sizeof(listnode))) == NULL){
		return -1;
	}
	p->data = x;
	p->next = NULL;
	lq->rear->next = p;
	lq->rear = p;
	return 0;
}

data_t dequeue(linkqueue *lq){
	linklist p;
	p = lq->front;
	lq->front = lq->front->next;
	free(p);
	p = NULL;
	return lq->front->data;
}

int empty(linkqueue *lq){
	return (lq->front == lq->rear);
}

int clear(linkqueue *lq){
	linklist p;
	while(lq->front != lq->rear){
		p = lq->front;
		lq->front = lq->front->next;
		printf("clear: %dn", p->data);
		free(p);
	}
	return 0;
}

linkqueue *queue_free(linkqueue *lq){
	linklist p;
	while(lq->front){
		p = lq->front;
		lq->front = lq->front->next;
		printf("free: %dn", p->data);
		free(p);
	}
	free(lq);
	return NULL;
}