基础数据结构_队列

内容

特点

1. 先进先出（FIFO）。
2. 一端进行插入，另一端进行删除的线性表。
3. 没有有效数据节点的队列称作空队。

难点

1. 如何让入队和出队的时间复杂度都为O(1)：将顺序队列臆想成一个环形。
2. 判空和判满条件冲突，都是队头==队尾
   1. 方案一：加个标志，保存有效值个数。
   2. 方案二：在队尾浪费一个空间，不再保存有效值，而是作为一个标记。

实现

//queue.h
#pragma once

typedef int ElemType;
typedef struct Queue
{
    ELEM_TYPE *base;
    int front;
    int tail;
    //int cursize;
}Queue, *PQueue;
//增删改查
//初始化
void Init_queue(Queue *pq);
//入队
bool Push(Queue *pq, ElemType val);
//出队
bool Pop(Queue *pq, ElemType *pval);
//获取队头元素值
bool Head(Queue *pq, ElemType *pval);
//获取有效值个数
int GetLength(Queue *pq);
//判空
bool IsEmpty(Queue *pq);
//判满
bool IsFull(Queue *pq);
//清空
void Clear(Queue *pq);
//销毁
void Destroy(Queue *pq);
//show
void Show(Queue *pq);

//初始化
void Init_queue(Queue *pq)
{
    assert(pq!=NULL);
    pq->base = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    assert(pq->base !=NULL);
    pq->front = pq->tail = 0;
}
//入队
bool Push(Queue *pq, ElemType val)
{
    assert(pq!=NULL);
    if(IsFull(pq))
    {
        return false;
    }
    pq->base[pa->tail] = val;
    pq->tail = (pq->tail + 1) % MAXSIZE;
    return true;
}
//出队
bool Pop(Queue *pq, ElemType *pval)
{
    if(IsEmpty(pq))
    {
        return false;
    }
    *pval = pq->base[pq->front];
    pq->front = (pq->front + 1) % MAXSIZE;
    return true;
}
//获取队头元素值
bool Head(Queue *pq, ElemType *pval)
{
    if(IsEmpty(pq))
    {
        return false;
    }
    *pval = pq->base[pq->front];
    return true;
}
//获取有效值个数
int GetLength(Queue *pq)
{
	return (pq->tail - pq-> front + MAXSIZE) % MAXSIZE;
}
//判空
bool IsEmpty(Queue *pq)
{
    return pq->front == pq->tail;
}
//判满
bool IsFull(Queue *pq)
{
    return (pq->tail+1)%MAXSIZE == pq->front;
}
//清空
void Clear(Queue *pq)
{
    pq->tail = pq->front = 0;
}
//销毁
void Destroy(Queue *pq)
{
    free(pq->base);
    pq->base = NULL;
}
//show
void Show(Queue *pq)
{
    int p = pq->front;
    while(p != pq->tail)
    {
        printf("%d ",pq->base[p]);
        p = (p+1) % MAXSIZE;
    }
    printf("\n");
}

//test
#include"queue.h"
int main()
{
    Queue q;
    Init_queue(&q);
    for(int i = 0;i<20;i++)
    {
        Push(&q,i+1);
    }
    
    Show(&q);
    
    for(int i = 0;i<5;i++)
    {
        int tmp;
        Pop(&q,&tmp);
        printf("%d\n",tmp);
    }
    Show(&q);
    
    printf("%d \n",GetLength(&q));
    
    Clear(&q);
    Show(&q);
    Destroy(&q);
    return 0;
}

链队列

//lqueue.h
typedef L

//lqueue.cpp

//test.cpp