数据结构和算法系列4 队列

时间：2022-04-02 10:24:13

上一篇讲了栈，这一篇要总结的是我们常用的队列，我想从以下几个方面进行总结。

1，什么是队列？
2，队列的存储结构？
3，队列的常用操作及实现代码？

1，什么是队列

1，首先，队列也是一种特殊的线性表，它是一种操作受限的线性表。它只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(font)。

2，对于队列，与现实生活中的排队类似，新加入的成员总是在队尾，而排在队列最前面的总是最先离开队列，即先进先出，因此队列也称为先进先出表(FIFO)。

2，队列的存储结构

数据结构和算法系列4 队列

实现代码：

/// <summary>    /// 封装顺序队列
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
    {
private const int _maxSize = 100;
public int MaxSize
        {
get { return _maxSize; }
        }

//保存数据
public T[] data=new T[_maxSize];

//头指针
public int head;

//尾指针
public int rear;
    }

3，队列的常见操作及实现代码

1，初始化队列

思路：构造一个空队列，即将头指针head和尾指针rear都设置为0。

2，入队

思路：若队列不满，则将数据x插入到尾指针rear指向的位置，然后再将rear加1。

3，出队

思路：若队列不空，则将头指针head加1，并返回被删除的元素。

4，取队头

思路：若队列不空，则返回队头元素。

5，取队长

思路：即尾指针rear-头指针head。

6，判队空

思路：只需要判断头指针head与尾指针是否相等即可

7，判队满

思路：只需判断尾指针与MaxSize是否相等即可

注：在一个非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。

C#版：

namespace DS.Model
{
/// <summary>
/// 学生实体
/// </summary>
public class Student
    {
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
    }
}

namespace DS.BLL
{
/// <summary>
/// 队列常见操作逻辑类
/// </summary>
public class SeqQueueBLL
    {
/// <summary>
/// 初始化
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public static SeqQueue<T> Init<T>(SeqQueue<T> seqQueue)
        {
            seqQueue.head = 0;
            seqQueue.rear = 0;
return seqQueue;
        }

/// <summary>
/// 入队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public static SeqQueue<T> Enter<T>(SeqQueue<T> seqQueue,T data)
        { 
//是否队满
if (IsFull(seqQueue)) return null;

            seqQueue.data[seqQueue.rear++] = data; //等价于seqQueue.data[seqQueue.rear] = data; seqQueue.rear++;
return seqQueue;
        }

/// <summary>
/// 出队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public static T Dequeue<T>(SeqQueue<T> seqQueue)
        { 
//是否队空
if (IsEmpty(seqQueue)) return default(T);

var data = seqQueue.data[seqQueue.head];
            seqQueue.head++;
return data;
        }

/// <summary>
/// 取队头
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public static T GetHead<T>(SeqQueue<T> seqQueue)
        { 
//是否队空
if(IsEmpty(seqQueue)) return default(T);

return seqQueue.data[seqQueue.head];
        }

/// <summary>
/// 取队长
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public static int GetLength<T>(SeqQueue<T> seqQueue)
        {
return seqQueue.rear - seqQueue.head;
        }


/// <summary>
/// 判断是否队满
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public static bool IsFull<T>(SeqQueue<T> seqQueue)
        {
if (seqQueue.rear >= seqQueue.MaxSize) return true;
return false;
        }

/// <summary>
/// 判断是否队空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public static bool IsEmpty<T>(SeqQueue<T> seqQueue)
        {
if (seqQueue.head == seqQueue.rear) return true;
return false;
        }
    }

/// <summary>
/// 封装顺序队列
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
    {
private const int _maxSize = 100;
public int MaxSize
        {
get { return _maxSize; }
        }

//保存数据
public T[] data=new T[_maxSize];

//头指针
public int head;

//尾指针
public int rear;
    }
}

namespace SeqQueue.CSharp
{
class Program
    {
static void Main(string[] args)
        {
            SeqQueue<Student> seqQueue = new SeqQueue<Student>();

            Console.WriteLine("********************初始化*******************\n");
            SeqQueueBLL.Init(seqQueue);
            Console.WriteLine("当前队列的长度是：{0}", SeqQueueBLL.GetLength(seqQueue));

            Console.WriteLine("\n********************入队*******************\n");
            Console.WriteLine("插入五条数据到队列\n");
            SeqQueueBLL.Enter(seqQueue, new Student { ID = 1, Name = "a", Age = 1 });
            SeqQueueBLL.Enter(seqQueue, new Student { ID = 2, Name = "b", Age = 2 });
            SeqQueueBLL.Enter(seqQueue, new Student { ID = 3, Name = "c", Age = 3 });
            SeqQueueBLL.Enter(seqQueue, new Student { ID = 4, Name = "d", Age = 4 });
            SeqQueueBLL.Enter(seqQueue, new Student { ID = 5, Name = "e", Age = 5 });
            Display(seqQueue);

            Console.WriteLine("\n********************出队*******************\n");
            Console.WriteLine("将队头出队\n");
            Student student= SeqQueueBLL.Dequeue(seqQueue);
            Display(seqQueue);

            Console.WriteLine("\n********************取队头*******************\n");
            Student result= SeqQueueBLL.GetHead(seqQueue);
            Console.WriteLine("ID={0},Name={1},Age={2}\n", result.ID, result.Name, result.Age);

            Console.WriteLine("\n********************取队长*******************\n");
            Console.WriteLine("当前队列中有{0}个元素\n",SeqQueueBLL.GetLength(seqQueue));

            Console.ReadKey();
        }

/// <summary>
/// 展示数据
/// </summary>
/// <param name="seqQueue"></param>
private static void Display(SeqQueue<Student> seqQueue)
        {
            Console.WriteLine("\n*****展示数据*****\n");

for (int i = seqQueue.head; i < seqQueue.rear; i++)
            {
                Console.WriteLine("ID={0},Name={1},Age={2}\n", seqQueue.data[i].ID, seqQueue.data[i].Name, seqQueue.data[i].Age);
            }
            Console.WriteLine("*****展示完毕*****\n");
        }
    }
}

程序运行结果：

数据结构和算法系列4 队列

数据结构和算法系列4 队列

 

C语言版：

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status; 
typedef int ElemType;

/* 队列的顺序存储结构 */
typedef struct
{
    ElemType data[MAXSIZE];
int head;        /* 头指针 */
int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SeqQueue;

/*初始化*/
Status Init(SeqQueue *seqQueue)
{
    seqQueue->head=0;
    seqQueue->rear=0;
return OK;
}

/*入队*/
Status Enter(SeqQueue *seqQueue,ElemType e)
{
//是否队满
if (IsFull(seqQueue)) return ERROR;

    seqQueue->data[seqQueue->rear]=e;
    seqQueue->rear++;
return OK;

}

/*出队*/
Status Dequeue(SeqQueue *seqQueue,ElemType *e)
{
//是否队空
if (IsEmpty(seqQueue)) return ERROR;

*e=seqQueue->data[seqQueue->head]; //为什么不能用e=seqQueue->data[seqQueue->head]
    seqQueue->head++;
return OK;
}

/*取队头*/
Status GetHead(SeqQueue *seqQueue,ElemType *e)
{
//是否队空
if (IsEmpty(seqQueue)) return ERROR;

*e=seqQueue->data[seqQueue->head];
return OK;
}

/*取队长*/
int GetLength(SeqQueue *seqQueue)
{
return seqQueue->rear-seqQueue->head;
}

/*是否队满*/
Status IsFull(SeqQueue *seqQueue)
{
if (seqQueue->rear>=MAXSIZE) return TRUE;
return FALSE;
}

/*是否队空*/
Status IsEmpty(SeqQueue *seqQueue)
{
if (seqQueue->rear==seqQueue->head) return TRUE;
return FALSE;
}

/*展示数据*/
void Display(SeqQueue *seqQueue)
{
int i;
    printf("*****展示数据*****\n");
for (i=seqQueue->head;i<seqQueue->rear;i++)
    {
        printf("%d ",seqQueue->data[i]);
    }
    printf("\n*****展示完毕*****\n");
}

void main()
{
    SeqQueue seqQueue;
    ElemType e;
    Status i;
int j;

    printf("***************初始化***************\n");
    i=Init(&seqQueue);
if (i==OK) printf("初始化成功!\n");
else printf("初始化失败!\n");

    printf("\n***************入队***************\n");
    printf("插入五条数据到队列\n");
for (j=1;j<6;j++)
    {
        i=Enter(&seqQueue,j);
    }
    Display(&seqQueue);

    printf("\n***************出队***************\n");
    printf("将队头出队\n");
    Dequeue(&seqQueue,&e);
    Display(&seqQueue);

    printf("\n***************取队头***************\n");
    GetHead(&seqQueue,&e);
    printf("当前队头元素是：%d\n",e);

    printf("\n***************取队长***************\n");
    printf("当前队列中有%d个元素\n",GetLength(&seqQueue));

    getchar();
}

程序运行结果：

数据结构和算法系列4 队列

标签：

相关文章