队列存储结构 – 阿Q的小屋

引子 – 队列逻辑结构

典型的线性结构。
操作受限了，插入端受限在一边，删除端受限在另一边，导致了先进入的先被删除（先进先出FIFO）。日常生活中的排队就可以看作队列。
队列的应用只要涉及到多个目标同时使用一个资源的时候均能用到。毕竟要保障先排队的先使用资源嘛，插队是不对滴。

队列基本操作：创销，增删查（改都少，主要是入队和出队操作）。

顺序存储（循环队列）

为什么顺序存储推荐循环队列呢？

（阿Q注：此处的循环不是真的把内存空间前后相连哦！而是逻辑上的 – 用到取余%数学方法的循环）

看下图，就能理解为什么还要在逻辑上将数组变成环形（队头指针需要移动）：

遵守先进先出，并且出队后队头指针移动，导致数组可存储比列越来越小（浪费空间），最终出现假溢出现象

那如何进行逻辑上的循环呢？ % 运算，如下图：

队列种元素个数：（MaxSize + rear – front）% MaxSize

逻辑上成环通过%解决了，但是还存在一个问题，那即为对空和队满的条件如何判断呢？看下图：

队空和队满的条件都为 rear == front，即：rear == front 无法区分是队空还是队满了。如何解决呢？

类型中增加 tag 数据成员（tag == 0，队空； tag == 1，队满），这种方法切记入队和出队时都需要维护 tag（入队将tag设为1 – 表示可能队满；出队将tag 设为0 – 表示队空）。【rear == front && tag == ? (0 – 队空，1- 队满)】

类型中增加表示队内元素个数(Qcount) 的数据成员【Qcount == MaxSize – 队满；Qcount == 0 – 队空】

舍弃数组的一个空间（入队少用一个空间），如下图：

这种方法下，队空 [rear == front]，队满[(rear + 1) % MaxSize == front]

下面阿Q都将用第三种方法。

静态分配

存储类型表示

typedef int QElemtype;
#define MaxQSize 50

typedef struct
{
    /* data */
    QElemtype data[MaxQSize];
    int front, rear;
}SqQueue;

操作

创【初始化】，查【队头元素】，增【入队】- 对应的判队满，删【出队】- 对应的判队空（由于是静态分配的空间，销无需手写）

// 初始化
void InitQueue(SqQueue &Q)
{
    Q.front = Q.rear = 0;
}

// 判队空
bool QueueEmpty(SqQueue Q)
{
    return Q.rear == Q.front;
}

// 判队满
bool QueueFull(SqQueue Q)
{
    return (Q.rear + 1) % MaxQSize == Q.front;
}

// 查队头元素
bool GetHead(SqQueue Q, QElemtype &x)
{
    if(QueueEmpty(Q)) return false;
    x = Q.data[Q.front];
    return true;
}

// 进队（重点）
bool EnQueue(SqQueue &Q, QElemtype x)
{
    if(QueueFull(Q)) return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxQSize;
    return true;
}


// 出队（重点）
bool DeQueue(SqQueue &Q, QElemtype &x)
{
    if(QueueEmpty(Q)) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxQSize;
    return true;
}

// 当前队列元素个数
int GetElemNumber(SqQueue Q)
{
    return (MaxQSize + Q.rear - Q.front) % MaxQSize;
}

动态分配

存储类型表示

typedef int QElemtype;
#define MaxQSize 50

typedef struct
{
    /* data */
    QElemtype *data;
    int front, rear;
    int QSize; // 开辟的最大空间
}DSqQueue;  // dynamic assignment sequential queue

操作

创【初始化】，销【释放动态分配空间】，查【队头元素】，增【入队】- 对应的判队满，删【出队】- 对应的判队空

// 初始化
void InitQueue(DSqQueue &Q,int Qsize = MaxSize)
{
    Q.data = new QElemtype[MaxQSize];
    // 内存不足
    if(!Q.data) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    Q.QSize = Qsize;
}

// 销毁
void DestoryQueue(DSqQueue &Q)
{
    if(Q.data)
    {
        delete Q.data;
        Q.QSize = 0; // 队列不存在
    }   
}

// 判队空
bool QueueEmpty(DSqQueue Q)
{
    return Q.rear == Q.front;
}

// 判队满
bool QueueFull(DSqQueue Q)
{
    return (Q.rear + 1) % Q.QSize == Q.front;
}

// 查队头元素
bool GetHead(DSqQueue Q, QElemtype &x)
{
    if(QueueEmpty(Q)) return false;
    x = Q.data[Q.front];
    return true;
}

// 入队（重点）
bool EnQueue(DSqQueue &Q, QElemtype x)
{
    if(QueueFull(Q)) return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % Q.QSize;
    return true;
}

// 出队（重点）
bool DeQueue(DSqQueue &Q, QElemtype &x)
{
    if(QueueEmpty(Q)) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % Q.QSize;
    return true;
}

// 当前队列元素个数
int GetElemNumber(DSqQueue Q)
{
    return (Q.QSize + Q.rear - Q.front) % Q.QSize;
}

链式存储

结点：数据 + next指针；整条链：头指针 + 尾指针

存储类型表示

typedef int QElemType;

// 结点
typedef struct LinkNode
{
    /* data */
    QElemType data;
    struct LinkNode *next;
}LinkNode;

// 整条链
typedef struct
{
    /* data */
    LinkNode *front, *rear;
}LinkQueue;

先来看头指针 + 尾指针的情况，如下图：

阿Q觉得也太麻烦了点，有什么统一的操作办法嘛？其实头指针 -> 头结点指针就好啦(*^_^*)，如下图：

那阿Q接下来的操作都是在有头结点指针 + 尾指针的链队进行咯。

操作

// 头结点指针 + 尾指针
void InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = new LinkNode;
    Q.front->next = NULL;   
}

// 判队空
bool QueueEmpty(LinkQueue Q)
{
    return Q.front == Q.rear;
}

// 查队头元素
bool GetHead(LinkQueue Q,QElemType &x)
{
    if(QueueEmpty(Q)) return false;
    x = Q.front->next->data;
    return true;
}

// 无需判队满（除非内存不足）
// 入队
bool EnQueue(LinkQueue &Q,QElemType x)
{
    // 动态分配结点
    LinkNode *node = new LinkNode;
    if(!node) return false; //内存满了
    node->data = x;
    node->next = NULL;
    Q.rear->next = node;
    Q.rear = node;
    return true;
}

// 出队
bool DeQueue(LinkQueue &Q,QElemType &x)
{
    if(QueueEmpty(Q)) return false;
    LinkNode *delptr = Q.front->next; // 指向待出队结点
    Q.front->next = delptr->next;
    
    // 出队最后一个元素（需要判断）
    if(delptr == Q.rear) Q.rear = Q.front;
    
    x = delptr->data;
    
    // 释放动态分配的空间
    delete delptr;
    return true;
}

// 销毁
void DestoryQueue(LinkQueue &Q)
{
    QElemType x;
    while(!QueueEmpty(Q)) DeQueue(Q,x);
    // 还需要释放头结点
    delete Q.front;

    Q.front = Q.rear = NULL;
}

题目

非算法题

1、假设循环单链表表示的队列长度为n，队头固定在链表尾，若只设头指针，则进队操作的时间复杂度为？ O(n)

2、循环队列放在一维数组A[0…M-1]，end1指向队头元素，end2指向队尾元素，假设队列两端均可进行入队和出队操作，队列中最多能容纳M个元素，初始时为空。则队空条件为 (end2 + 1) % M，队满条件为 end2 == end1，对吗？

这种方案去设计循环队列，阿Q觉得在不增设数据成员的前提下队满条件无法设置（无法确定队是否满了），题中的队满条件有问题。

3、假设一个火车车轨的入口到出口间有n条轨道，列车前行方向为从左到右，列车可驶入任意一条轨道。现有编号为1~9的9列列车，驶入次序依次是 8,4,2,5,3,9,1,6,7。若期待驶出次序依次为1~9，则n至少是？

算法题

1、利用两个栈S1，S2来模拟一个队列，已知栈的4个运算定义如下：

Push(S,x); // x入栈 
Pop(S,x); // x出栈
StackEmpty(S); // 栈空
StackOverflow(S); // 栈满

如何利用栈的运算实现改队列的3个运算？

// 形参根据需求设计
Enqueue;
Dequque;
QueueEmpty;

阿Q分析：

入队

①S1没满，入栈S1即可。

②如果S1满了，S2为空，将S1中的元素全部出栈再入栈到S2，再将元素入栈到S1。

③如果S1满了，S2中还有元素，对不起，装不下了。

出队

①S1，S2都没元素，对不起，出不了。

①S2有元素，S2出栈顶元素即可。

②S1有元素，S2空。那就需要将S1当前的栈内元素全部出栈然后进入S2，然后出栈栈顶元素。

// 入队
bool Enqueue(Stack &S1, Stack &S2, Elemtype x)
{

    if(!StackOverflow(S1)){
        Push(S1,x);
        return true;
    }

    if(StackOverflow(S1) && StackEmpty(S2)) 
    {
        Elemtype tmp;
        while(!StackEmpty(S1))
        {
            Pop(S1,tmp);
            Push(S2,tmp);
        }
        Push(S1,x);
        return true;
    }

    // if(StackOverflow(S1) && !StackEmpty(S2)) return false; 
    // return false;
    else return false;
}

// 判队空
bool QueueEmpty(Stack S1, Stack S2)
{
    return (StackEmpty(S1) && StackEmpty(S2));
}

// 出栈
bool Dequeue(Stack &S1,Stack &S2, Elemtype &x)
{

    if(QueueEmpty(S1,S2)) return false;

    if(!StackEmpty(S2))
    {
        Pop(S2,x);
        return true;
    }

    if(!StackEmpty(S1) && StackEmpty(S2))
    {
        while(!StackEmpty(S1))
        {
            Pop(S1,x);
            Push(S2,x);
        }
        Pop(S2,x);
        return true;
    }
}

栈来实现二叉树层次遍历中用到了该思想。

2、设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占的空间只增不减；④入队操作和出队操作的时间复杂度始终为O(1)；

1）画出队列初始状态，并给出队空和队满条件。

2）画出第一个元素入队后的队列状态。

3）给出入队操作和出队操作的基本过程及操作算法。

阿Q的小想法

阿Q自己没想到用类似于循环队列的方式去处理。而是将出队元素结点插入到 rear 所指的结点后。这样处理 rear后有结点，只需将其结点的data 赋值，rear指向该结点。虽然满足题目所有要求，但是有个弊端，就是一直进行进队然后出队操作，rear后的结点数一直在增加（虽然最后能全部销毁，但这种方式还是不理想）

借鉴循环队列的思想，设计成首尾相连的循环单链表（仍然采取牺牲一个结点空间来解决队空和队满条件相同问题）。

// 3）基本过程描述（不用写具体代码，只需要写伪代码就行）

入队操作:

// 判队满
if(front == rear->next) 
   则在rear后面插入一个新的空闲节点；
入队元素保存到rear所指的结点中；rear = rear->next; 返回;

出队操作：

// 判队空
if(front == rear)
  出队失败;返回;
取front所指结点中的元素e; front = front->next;返回;

// 操作算法（需要写具体代码）
// 假设 已经初始化了如 1）中的循环单链表 CLinkQueue，并且结点定义为LinkNode
bool EnQueue(ClinkQueue &Q, Elemtype x)
{
    // 队满
    if(Q.front == Q.rear->next)
    {   
        LinkNode *node = new LinkNode;
        if(!node) return false; // 内存不足
        node->next = Q.rear->next;
        Q.rear->next = node;
    }
    Q.rear.data = x;
    Q.rear = Q.rear->next;
    return true;
}   

bool DeQueue(ClinkQueue &Q, Elemtype x)
{
    if(Q.front == Q.rear) return false; // 队空
    x = Q.front.data;
    Q.front = Q.front->next;
    return true;  
}

阿Q觉得这道算法题考的真不错，毕竟数据结构是多变的，要掌握思想，不局限于特定的结构，要多想想这种思想能用在什么地方。比如这题，借鉴循环队列的思想，用循环单链表的存储结构实现了可增长版的循环队列（升级版）。

一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28

顺序存储（循环队列）

静态分配

存储类型表示

操作

动态分配

存储类型表示

操作

链式存储

存储类型表示

操作

题目

非算法题

算法题

发送评论 编辑评论

发送评论编辑评论