Skip to content

Latest commit

 

History

History
336 lines (274 loc) · 8.24 KB

从零开始学习数据结构_队列.md

File metadata and controls

336 lines (274 loc) · 8.24 KB

队列是两端出入数据，分队首、队尾，堆栈是单端出入数据，有栈顶指针。

要明确理解栈和队列的应用场景，这些场景我提到过啊，比如栈常用在函数调用发生时，形参压栈，保留现场信息（细节看：从零开始学习数据结构-->栈，以及递归转为非递归使用栈，队列下文会提到键盘缓冲区的本质上是循环队列。

一、队列

逻辑线性结构，先进先出 FIFO；入队列在队尾，出队列在队首；

队首等于队尾存在 2 种情况： 空队：刚刚做完出队列操作； 满队：刚刚做完入队列操作；

模型如下：

队列的实现：循环链表（物理非线性结构）、循环数组（物理线性结构）

二、循环队列

模型如下：

此时队列中有多少个数据？

- (tail-head+maxRoom) % maxRoom

存储数据的控制头：

private:
    Type *data;  //申请队列的空间
    int count;   //队列空间大小
    int head;    //队头
    int tail;    //队尾
    boolean lastAction;  //最后一次动作,出队还是入队
};

2.1 C++代码实现

#ifndef _QUEUE_H_
#define _QUEUE_H_

typedef unsigned char boolean;
#define DEFAULT    10
#define IN    1
#define OUT 0

template<typename Type>
class Queue{
public:
    Queue(size_t sz = 0){
        count = sz > DEFAULT ? sz : DEFAULT;
        data = new Type[count];
        head = tail = 0;
        lastAction = OUT;
    }
    Queue(const Queue &t);
    Queue& operator=(const Queue &t);
    ~Queue(){
        delete []data;
    }
public:
    bool isEmpty(){
        return lastAction == OUT && head == tail;
    }
    bool isFull(){
        return lastAction == IN && head == tail;
    }
    bool in(const Type &x);
    bool out(Type *value);
    bool getHead(Type *value);
    void lookAllQueueElem()const;
private:
    Type *data;
    int count;
    int head;
    int tail;
    boolean lastAction;
};

template<typename Type>
bool Queue<Type>::in(const Type &x){
    if(isFull()){
        return false;
    }
    data[tail] = x;
    tail = (tail+1)%count;
    lastAction = IN;

    return true;
}
template<typename Type>
bool Queue<Type>::out(Type *value){
    if(isEmpty()){
        return false;
    }

    *value = data[head];
    head = (head+1)%count;
    lastAction = OUT;

    return true;
}
template<typename Type>
bool Queue<Type>::getHead(Type *value){
    if(isEmpty()){
        return false;
    }
    *value = data[head];

    return true;
}
template<typename Type>
void Queue<Type>::lookAllQueueElem()const{
    int i;

    if(head > tail){
        for(i = head; i < count; i++){
            cout<<data[i]<<" ";
        }
        for(i = 0; i < tail; i++){
            cout<<data[i]<<" ";
        }
    }
    for(i = head; i < tail; i++){
            cout<<data[i]<<" ";
    }
    cout<<endl;
}
#endif

2.2 测试代码

#include<iostream>
#include<stdlib.h>
#include"queue.h"
using namespace std;

int main(void){
    Queue<int> qu;
    int value;

    qu.in(10);
    qu.in(20);
    qu.lookAllQueueElem();
    qu.getHead(&value);
    cout<<value<<endl;
    qu.out(&value);
    cout<<value<<endl;
    qu.lookAllQueueElem();
    return 0;
}

2.3 运行结果

三、链式存储

思路：就是用 head 始终指向头结点，tail 始终指向尾结点，静态的模板变量，单链表实现，入队从尾 tail，出队从头 head；

模型如下：

控制头：

private:
    Type data;
    LinkQueue *next;
    static LinkQueue *head;
    static LinkQueue *tail;
};

3.1 C++代码实现

#ifndef _LINK_QUEUE_H_
#define _LINK_QUEUE_H_

template<typename Type>
class LinkQueue{
public:
    LinkQueue(){
        next = NULL;
    }
    ~LinkQueue(){
        
    }
public:
    bool isEmpty(){
        return head == NULL;
    }
    void in(Type &);
    bool out(Type *);
    bool readHead(Type *);
    void lookAllElem();
private:
    Type data;
    LinkQueue *next;
    static LinkQueue *head;
    static LinkQueue *tail;
};
template<typename Type>
typename LinkQueue<Type>::LinkQueue* LinkQueue<Type>::head = NULL;
template<typename Type>
typename LinkQueue<Type>::LinkQueue* LinkQueue<Type>::tail = NULL;

template<typename Type>
void LinkQueue<Type>::in(Type &x){
    LinkQueue *tmp;

    tmp = new LinkQueue;
    if(head == NULL){
        head = tmp;
        tail = tmp;
    }else{
        tail->next = tmp;
        tail = tmp;
    }
    tail->data = x;
}
template<typename Type>
bool LinkQueue<Type>::out(Type *value){
    if(isEmpty()){
        return false;
    }
    LinkQueue *tmp;
    *value = head->data;
    tmp = head;
    head = head->next;
    delete tmp;

    return true;
}
template<typename Type>
bool LinkQueue<Type>::readHead(Type *x){
    if(isEmpty()){
        return false;
    }
    *x = head->data;

    return true;
}
template<typename Type>
void LinkQueue<Type>::lookAllElem(){
    LinkQueue *tmp;

    for(tmp = head; tmp; tmp = tmp->next){
        cout<<tmp->data<<" "; 
    }
    cout<<endl;

}
#endif

3.2 测试代码

#include<iostream>
#include<stdlib.h>
#include"linkQueue.h"
using namespace std;

int main(void){
    LinkQueue <int>s;
    int value = 10;
    int value1 = 20;

    s.in(value);
    s.in(value1);
    s.lookAllElem();
    s.out(&value);
    cout<<value<<endl;
    s.readHead(&value);
    cout<<value<<endl;

    return 0;
}

3.3 运行结果


静态模板变量的初始化:

private:
    Type data;
    LinkQueue *next;
    static LinkQueue *head;
    static LinkQueue *tail;
};
template<typename Type>
typename LinkQueue<Type>::LinkQueue* LinkQueue<Type>::head = NULL;
template<typename Type>
typename LinkQueue<Type>::LinkQueue* LinkQueue<Type>::tail = NULL;

四、队列的应用

键盘缓冲区，实质上是循环队列；

I/O 缓冲区，在网络环境下，存在着连入网络的节点速度差异；在不进行任何处理的情况下，高速节点向低速节点所发出的数据，在低速节点不能及时处理的情况下会产生“数据淹没”现象（流量失控）。

为进行流量控制，通信双方设置缓冲区；接收方所接到的数据达到缓冲区的临界点时，向发送方发送“暂停发送”信号，等相关数据处理完毕后再向发送方发出“继续发送”的信号，流量控制是通过缓冲区实现的。

五、说明

原创文章链接：从零开始学习数据结构-->队列