线性表：顺序队列算法实现

小咪咪 2022-05-31 13:10 188阅读 0赞

# 顺序队列介绍 #

**顺序队列是队列的顺序存储结构，顺序队列实际上是运算受限的顺序表**。我们知道**队列是一种先将先出的数据结构**，它是一种受限制的线性表，我们的顺序队列是一种队列，采用的是顺序存储结构。与**其对应的是采用链式存储结构的队列 也就是链式队列**。**顺序队列通常采用一维数组进行存储**。所以呢**本次编写顺序队列 就采用前面封装好的动态数组呗**。动态数组你知道么，不知道请看：[**数据结构与算法：动态数组（利用万能指针实现任意类型数组操作）**][Link 1]

# 顺序队列相关算法接口 #

对外提供**SeqQueue类型也就是void\* 类型 对用户隐藏底层实现**。

#pragma once
    #ifndef __SEQQUEUE_H__
    #define __SEQQUEUE_H__
    typedef void* SeqQueue;
    typedef enum {FALSE,TRUE} Boolean;
    
    //初始化
    SeqQueue Init_SeqQueue();
    
    //入队
    Boolean Push_SeqQueue(SeqQueue queue ,void* data);
    
    //出队
    void* Pop_SeqQueue(SeqQueue queue);
    
    //返回队头元素
    void* Front_SeqQueue(SeqQueue queue);
    
    //返回队尾元素
    void* Rear_SeqQueue(SeqQueue queue);
    
    //返回队元素个数
    int Size_SeqQueue(SeqQueue queue);
    
    //返回队是否为空
    int IsEmpty_SeqQueue(SeqQueue queue);
    
    //销毁队列
    void Destroy_SeqQueue(SeqQueue queue);
    
    #endif // !__SEQQUEUE_H__

# 顺序队列相关算法实现 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "DynamicArray.h"
    #include "SeqQueue.h"
    #define MAXSIZE 1024
    
    //初始化
    SeqQueue Init_SeqQueue()
    {
    	DynamicArray *arr =  Init_DynamicArray(MAXSIZE);
    	return arr;
    }
    
    //入队 从队尾入队
    Boolean Push_SeqQueue(SeqQueue queue, void* data)
    {
    	if (queue == NULL || data == NULL)
    	{
    		return FALSE;
    	}
    	DynamicArray *arr = queue;
    	//队满
    	if (arr->m_size == MAXSIZE)
    	{
    		return FALSE;
    	}
    	InsertByIndex_DynamicArray(arr, data, arr->m_size);
    	return TRUE;
    }
    
    //出队 从队头出队
    void* Pop_SeqQueue(SeqQueue queue)
    {
    	if (queue == NULL)
    	{
    		return NULL;
    	}
    	DynamicArray *arr = queue;
    	//队空
    	if (arr->m_size == 0)
    	{
    		return NULL;
    	}
    	return RemoveByIndex_DynamicArray(arr, 0);
    }
    
    //返回队头元素
    void* Front_SeqQueue(SeqQueue queue)
    {
    	if (queue == NULL)
    	{
    		return NULL;
    	}
    	DynamicArray *arr = queue;
    	//队空
    	if (arr->m_size == 0)
    	{
    		return NULL;
    	}
    	return arr->pArr[0];
    }
    
    //返回队尾元素
    void* Rear_SeqQueue(SeqQueue queue)
    {
    	if (queue == NULL)
    	{
    		return NULL;
    	}
    	DynamicArray *arr = queue;
    	//队空
    	if (arr->m_size == 0)
    	{
    		return NULL;
    	}
    	return arr->pArr[arr->m_size-1];
    }
    
    //返回队元素个数
    int Size_SeqQueue(SeqQueue queue)
    {
    	if (queue == NULL)
    	{
    		return 0;
    	}
    	DynamicArray *arr = queue;
    	return arr->m_size;
    }
    
    //返回队是否为空
    Boolean IsEmpty_SeqQueue(SeqQueue queue)
    {
    	if (Size_SeqQueue(queue) == 0)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }
    
    //销毁队列
    void Destroy_SeqQueue(SeqQueue queue)
    {
    	if (queue == NULL)
    	{
    		return;
    	}
    	DynamicArray *arr = queue;
    	Destroy_DynamictArray(arr);
    }

# 代码运行检测 #

## Main.c测试代码 ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "SeqQueue.h"
    //用结构体测试 数据
    typedef struct Person
    {
    	char name[64];
    	int age;
    }Person;
    
    int main(int argc, char *argv[])
    {
    	Person p1 = { "Lily",11 };
    	Person p2 = { "Laymond",21 };
    	Person p3 = { "John",31 };
    	Person p4 = { "Leo",41 };
    	Person p5 = { "Zeo",51 };
    	SeqQueue queue = Init_SeqQueue();
    	Push_SeqQueue(queue, &p1);
    	Push_SeqQueue(queue, &p2);
    	Push_SeqQueue(queue, &p3);
    	Push_SeqQueue(queue, &p4);
    	Push_SeqQueue(queue, &p5);
    	printf("队头元素:name=%s,age=%d\n", ((Person*)Front_SeqQueue(queue))->name, ((Person*)Front_SeqQueue(queue))->age);
    	printf("队尾元素:name=%s,age=%d\n", ((Person*)Rear_SeqQueue(queue))->name, ((Person*)Rear_SeqQueue(queue))->age);
    	printf("队列的元素个数:%d\n", Size_SeqQueue(queue));
    	Person* p = NULL;
    	printf("将队列的元素依次出队\n");
    	while (!IsEmpty_SeqQueue(queue))
    	{
    		p = Pop_SeqQueue(queue);
    		printf("name=%s,age=%d\n", p->name, p->age);
    	}
    	printf("队列的元素个数:%d\n", Size_SeqQueue(queue));
    	Destroy_SeqQueue(queue);
    	return 0;
    }

## 运行结果 ##

![20180225224353314][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79293915
[20180225224353314]: /images/20220531/4f41f1da8c4d426599265796de7dd942.png