C高级编程 第十五天（队列 顺序存储 链式存储）

目录

1.队列

2.队列的顺序存储

①初始化队列

②入队

③出队

④返回队头

⑤返回队尾

⑥判断是否为空

⑦返回队列大小

⑧销毁队列

3.队列的链式存储

①初始化队列

②入队

③出队

④返回队头

⑤返回队尾

⑥判断是否为空

⑦返回队列大小

⑧销毁队列

---

1.队列

先进先出，引用了之前动态数组的静态库

#define MAX 1024typedef void* SeqQueue;

2.队列的顺序存储

①初始化队列

//初始化队列
SeqQueue init_SeqQueue()
{struct dynamicArray* array = initData(MAX);return array;
}

②入队

//入队
void push_SeqQueue(SeqQueue queue, void* data)
{//本质 尾插if (queue == NULL || data == NULL){return NULL;}struct dynamicArray* array = queue;//队列满了if (array->m_Capacity == array->m_Size){return NULL;}insert_Array(queue, data, array->m_Size);
}

③出队

//出队
void pop_SeqQueue(SeqQueue queue)
{//本质 头删if (queue == NULL){return NULL;}struct dynamicArray* array = queue;//队列为空时if (array->m_Size == 0){return NULL;}removeByPos(array, 0);
}

④返回队头

//返回队头
SeqQueue front_SeqQueue(SeqQueue queue)
{//本质 输出第一个元素if (queue == NULL){return NULL;}struct dynamicArray* array = queue;//队列为空时if (array->m_Size == 0){return NULL;}void* result = array->pAddr[0];return result;
}

⑤返回队尾

//返回队尾
SeqQueue back_SeqQueue(SeqQueue queue)
{//本质 输出最后一个元素if (queue == NULL){return NULL;}struct dynamicArray* array = queue;//队列为空时if (array->m_Size == 0){return NULL;}void* result = array->pAddr[array->m_Size-1];return result;
}

⑥判断是否为空

//判断队列是否为空
int isEmpty(SeqQueue queue)
{if (queue == NULL){return 1;}struct dynamicArray* array = queue;if (array->m_Size == 0){return 1;}return 0;
}

⑦返回队列大小

//返回队列大小
int size_SeqQueue(SeqQueue queue)
{if (queue == NULL){return 0;}struct dynamicArray* array = queue;int result = array->m_Size;return result;
}

⑧销毁队列

//销毁队列
void destory_SeqQueue(SeqQueue queue)
{if (queue == NULL){return NULL;}destory(queue);
}

3.队列的链式存储

//节点结构体
struct LinkNode
{struct LinkNode* next;
};//队列结构体
struct LQueue
{struct LinkNode pHeader;	//头结点int m_size;		//队列大小struct LinkNode* pTail;		//尾结点指针
};typedef void* LinkQueue;

①初始化队列

//初始化队列
LinkQueue init_SeqQueue()
{struct LQueue* queue = (struct LQueue*)malloc(sizeof(struct LQueue));if (queue == NULL){return NULL;}queue->m_size = 0;queue->pHeader.next = NULL;queue->pTail = &(queue->pHeader);return queue;
}

②入队

//入队
void push_SeqQueue(LinkQueue queue, void* data)
{//本质 尾插if (queue == NULL || data==NULL){return;}struct LinkNode* mynode = (struct LinkNode* )data;struct LQueue* myQueue = (struct LQueue*) queue;myQueue->pTail->next = mynode;mynode->next = NULL;myQueue->pTail = mynode;myQueue->m_size++;
}

③出队

void pop_SeqQueue(LinkQueue queue)
{//本质 头删if (queue == NULL){return;}struct LQueue* myQueue = (struct LQueue*)queue;struct LinkNode* mynode = myQueue->pHeader.next;//队列为空if (myQueue->m_size == 0){return;}//如果只有一个节点时，尾结点要变化if (myQueue->m_size == 1){myQueue->pHeader.next = mynode->next;myQueue->pTail = &(myQueue->pHeader);myQueue->m_size--;return;}myQueue->pHeader.next = mynode->next;free(mynode);mynode = NULL;myQueue->m_size--;
}

④返回队头

//返回队头
LinkNode* front_SeqQueue(LinkQueue queue)
{//本质 输出第一个元素if (queue == NULL){return NULL;}struct LQueue* myQueue = (struct LQueue*)queue;//队列为空时if (myQueue->m_size == 0){return NULL;}struct LinkNode* firstNode = myQueue->pHeader.next;return firstNode;
}

⑤返回队尾

//返回队尾
LinkNode* back_SeqQueue(LinkQueue queue)
{//本质 输出最后一个元素if (queue == NULL){return NULL;}struct LQueue* myQueue = (struct LQueue*)queue;//队列为空时if (myQueue->m_size == 0){return NULL;}struct LinkNode* lastNode = myQueue->pTail;return lastNode;
}

⑥判断是否为空

//判断是否为空
int isEmpty(LinkQueue queue)
{if (queue == NULL){return 0;}struct LQueue* myQueue = (struct LQueue*)queue;if (myQueue->m_size == 0){return 1;}return 0;
}

⑦返回队列大小

//返回队列大小
int size_SeqQueue(LinkQueue queue)
{if (queue == NULL){return 0;}struct LQueue* myQueue = (struct LQueue*)queue;int size = myQueue->m_size;return size;
}

⑧销毁队列

//销毁队列
void destory_SeqQueue(LinkQueue queue)
{if (queue == NULL){return;}free(queue);queue = NULL;
}