数据结构与算法(八)：队列

相关文献：
数据结构与算法(一)：基础理论
数据结构与算法(二)：线性表的实现
数据结构与算法(三)：线性表算法设计练习
数据结构与算法(四)：斐波那契数列
数据结构与算法(五)：LRU
数据结构与算法(六)：栈
数据结构与算法(七)：栈/队列的算法解题思想
数据结构与算法(八)：队列
数据结构与算法(九)：二叉树/线索化二叉树
数据结构与算法(十)：哈夫曼树

本章节研究内容：
1.限定性数据结构--栈与队列的特点
2.顺序存储队列的实现（队列结构的顺序存储方式实现）
3.链式存储队列的实现（队列结构的链式存储方式实现）
4.双向队列
5.单调队列
6.翻转字符串里的单词(双向队列实现)
7.滑动窗口最大值

一、栈与队列的特点

栈和队列数据结构的特点：

• 栈：先进后出；
• 队列：先进先出。

它们对插入和删除操作的限定的：

• 栈是限定只能在表的一端进行插入和删除操作的线性表；
• 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

遍历数据速度不同：

• 栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性。
• 队列则不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间。

栈的示意图 队列的示意图

二、顺序存储队列的实现

上文已经说了，我们的队列有一个特点：头进尾出 / 尾进头出。
首先我们需要开辟一段连续的内存空间，使用头指针front和尾指针rear都指向队列首地址，此时的空队列：

此时判断空队列的条件可以是：Q.front == Q.rear;

这里我的指针走向是尾进头出来进行指针移动的增删操作：
（增实际上那块内存原来有数据，直接进行新数据覆盖进去；删实际上并不是把那块内存清空，而是通过front指针移动来达到假删除。）

通过上述的操作之后可以发现rear指针已经无法再往上移动了，说明队列已经满了，但实际上呢，front指针指向内存的下面还有位置可以存的，这个队列并没有满！（假溢出）

为了解决上面这种情况呢，引入一个“环形队列”，而我们的内存实际上并不是环状的，只是我们幻想出来的解决方案而已。

接下来我们把它想象成是一块环形的，那么就不会出现队列未满而体现满的现象：
(使用顺序存储实现循环队列)

想象它是个环形

如果我们继续新增数据，知道这个队列满了，此时两个指针依旧指向同一块内存上：

问题就来了，两个指针都指向同一块内存，那我们怎么知道队列是满队列还是空队列呢？？？
解决这个问题，我们把队列中的其中一块内存空出来，不存储东西，如下：

则可以这样来区分队空/队满：

• 判断队空: Q.front == Q.rear;
• 判断队满: (Q.rear + 1) % MAXSIZE == Q.front

如果你对环形想象不出来，那么可以参考下图：

ps: 当然也可以使用一个flag临时变量去标记是否队列为满。（不建议）

结合上述理论，我们来实现一下顺序队列：

#include "stdio.h"
#include "stdlib.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 QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

/* 循环队列的顺序存储结构 */
typedef struct
{
    QElemType data[MAXSIZE];
    // 这两个是索引，用于访问数组的下标。
    int front;        /* 头指针 */
    int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;


//6.1 初始化一个空队列Q
Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

//6.2 将队列清空
Status ClearQueue(SqQueue *Q){
    Q->front = Q->rear = 0;
    return OK;
}

//6.3 若队列Q为空队列,则返回TRUR,否则返回FALSE;
Status QueueEmpty(SqQueue Q){
    //队空标记
    if (Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}


//6.4 返回Q的元素个数,也就是队列的当前长度
int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}

//6.5 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR;
Status GetHead(SqQueue Q,QElemType *e){
    //队列已空
    if (Q.front == Q.rear)
        return ERROR;
    
    *e = Q.data[Q.front];
    return OK;
    
}

//6.6 若队列未满,则插入元素e为新队尾元素
Status EnQueue(SqQueue *Q,QElemType e){
    //队列已满
    if((Q->rear+1)%MAXSIZE == Q->front)
        return ERROR;
    
    //将元素e赋值给队尾
    Q->data[Q->rear] = e;
    
    //rear指针向后移动一位,若到最后则转到数组头部;
    Q->rear = (Q->rear+1)%MAXSIZE;
    
    return OK;
}

//6.7 若队列不空,则删除Q中队头的元素,用e返回值
Status DeQueue(SqQueue *Q,QElemType *e){
    //判断队列是否为空
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    //将队头元素赋值给e
    *e = Q->data[Q->front];
    
    //front 指针向后移动一位,若到最后则转到数组头部
    Q->front = (Q->front+1)%MAXSIZE;
    
    return OK;
}


//6.8 从队头到队尾依次对队列的每个元素数组
Status QueueTraverse(SqQueue Q){
    int i;
    i = Q.front;
    while ((i+Q.front) != Q.rear) {
        printf("%d   ",Q.data[i]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("001--顺序队列表示与操作实现\n");
    
    Status j;
    int i=0,l;
    QElemType d;
    SqQueue Q;
    InitQueue(&Q);
    printf("初始化队列后，队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
    
    printf("入队:\n");
    while (i < 10) {
        EnQueue(&Q, i);
        i++;
    }
    QueueTraverse(Q);
    printf("队列长度为: %d\n",QueueLength(Q));
    printf("现在队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
    printf("出队:\n");
   
   //出队
    DeQueue(&Q, &d);
    printf("出队的元素:%d\n",d);
    QueueTraverse(Q);

    //获取队头
    j=GetHead(Q,&d);
    if(j)
        printf("现在队头元素为: %d\n",d);
    ClearQueue(&Q);
    printf("清空队列后, 队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
    return 0;
}

ps：代码中入队/出队通过运算实现front和rear的位移，从而实现伪循环队列。

三、链式存储队列的实现

• 1.使用头指针，空队列时front和rear指针都指向头结点；
• 2.新插入的节点要成为新的首元节点；
• 3.要删除的节点，必须从尾结点开始删除(不包含头节点)。

#include <stdio.h>
#include "stdio.h"
#include "stdlib.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 QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

typedef struct QNode    /* 结点结构 */
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct            /* 队列的链表结构 */
{
    QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;


/*6.1 初始化队列*/
Status InitQueue(LinkQueue *Q){
    //1. 头/尾指针都指向新生成的结点
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));

    //2.判断是否创建新结点成功与否
    if (!Q->front) {
        return ERROR;
    }

    //3.头结点的指针域置空
    Q->front->next = NULL;
    
    return OK;
}


/*6.2 销毁队列Q*/
Status DestoryQueue(LinkQueue *Q){
    //遍历整个队列,销毁队列的每个结点
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
    
}

/*6.3 将队列Q置空*/
Status ClearQueue(LinkQueue *Q){
    QueuePtr p,q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    
    while (p) {
        
        q = p;
        p = p->next;
        free(q);
        
    }
    return OK;
}

/*6.4 判断队列Q是否为空*/
Status QueueEmpty(LinkQueue Q){
    if (Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}

/*6.5 获取队列长度*/
int QueueLength(LinkQueue Q){
    int i= 0;
    QueuePtr p;
    p = Q.front;
    while (Q.rear != p) {
        i++;
        p = p->next;
    }
    return i;
}

/*6.6 插入元素e为队列Q的新元素*/
Status EnQueue(LinkQueue *Q,QElemType e){
    //为入队元素分配结点空间,用指针s指向;
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    
    //判断是否分配成功
    if (!s) {
         return ERROR;
    }
    
    //将新结点s指定数据域.
    s->data = e;
    s->next = NULL;
    
    //将新结点插入到队尾
    Q->rear->next = s;
    
    //修改队尾指针
    Q->rear = s;
    
    return OK;
}


/*6.7 出队列*/
Status DeQueue(LinkQueue *Q,QElemType *e){
    QueuePtr p;
    
    //判断队列是否为空;
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    //将要删除的队头结点暂时存储在p
    p = Q->front->next;
    
    //将要删除的队头结点的值赋值给e
    *e = p->data;
    
    //将原队列头结点的后继p->next 赋值给头结点后继
    Q->front->next = p ->next;
    
    //若队头就是队尾,则删除后将rear指向头结点.
    if(Q->rear == p) Q->rear = Q->front;
    
    free(p);
    
    return OK;
}

/*6.8 获取队头元素*/
Status GetHead(LinkQueue Q,QElemType *e){
    //队列非空
    if (Q.front != Q.rear) {
        //返回队头元素的值,队头指针不变
        *e =  Q.front->next->data;
        return TRUE;
    }
    return  FALSE;
}

/*6.9 遍历队列*/
Status QueueTraverse(LinkQueue Q){
    QueuePtr p;
    p = Q.front->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("链队列的表示与操作!\n");
    
    Status iStatus;
    QElemType d;
    LinkQueue q;
    
    //1.初始化队列q
    iStatus = InitQueue(&q);
    
    //2. 判断是否创建成
    if (iStatus) {
        printf("成功地构造了一个空队列\n");
    }
    
    //3.判断队列是否为空
    printf("是否为空队列?%d (1:是 0:否)\n",QueueEmpty(q));
    
    //4.获取队列的长度
    printf("队列的长度为%d\n",QueueLength(q));
    
    //5.插入元素到队列中
    EnQueue(&q, -3);
    EnQueue(&q, 6);
    EnQueue(&q, 12);
    
    printf("队列的长度为%d\n",QueueLength(q));
    printf("是否为空队列?%d (1:是 0:否)\n",QueueEmpty(q));
    
    //6.遍历队列
    printf("队列中的元素如下:\n");
    QueueTraverse(q);

    //7.获取队列头元素
    iStatus = GetHead(q, &d);
    if (iStatus == OK) {
        printf("队头元素是:%d\n",d);
    }
    
    //8.删除队头元素
    iStatus =DeQueue(&q, &d);
    if (iStatus == OK) {
        printf("删除了的队头元素为:%d\n",d);
    }
    
    //9.获取队头元素
    iStatus = GetHead(q, &d);
    if (iStatus == OK) {
        printf("新的队头元素为:%d\n",d);
    }
    
    //10.清空队列
    ClearQueue(&q);
    
    //11.销毁队列
    DestoryQueue(&q);

    return 0;
}

四、双向队列

双向队列(双端队列)就是一个两端都是结尾的对垒。双向队列的入队和出队操作都可以再两端进行。它的数据结构与双向链表十分相似。

Deque.h

#import <Foundation/Foundation.h>

@interface Deque : NSObject
// 初始化
- (instancetype)initWithCapacity:(NSUInteger)numItems;
// 获取第一个数据
- (id)fisrtValue;
// 获取最后一个数据
- (id)lastValue;
// 从头部添加数据
- (void)pushValueToHead:(id)n;
// 从头部删除数据
- (void)popValueFromHead;
// 从尾部添加数据
- (void)pushValueToTail:(id)n;
// 从尾部删除数据
- (void)popValueFromTail;

@end

Deque.m

#import "Deque.h"

// 节点
@interface _DoubleLinkNode : NSObject {
    @package
    _DoubleLinkNode *_prev; // 头指针
    _DoubleLinkNode *_next; // 尾指针
    id _value;
}
@end
@implementation _DoubleLinkNode

@end

// 双端队列 - 类似双向链表
@interface _DoubleLink : NSObject
@end

@interface _DoubleLink() {
    @package
    NSUInteger _count; // 个数
    NSUInteger _capacity; // 容量
    _DoubleLinkNode *_head; // 头结点
    _DoubleLinkNode *_tail; // 尾节点
}

- (void)removeLast;
- (BOOL)isEmpty;
- (id)lastValue;
- (id)fisrtValue;
- (void)addValueToTail:(id)n;

@end

@implementation _DoubleLink
- (instancetype)initWithCapacity:(NSUInteger)numItems {
    self = [super init];
    if (self) {
        _capacity = numItems;
    }
    return self;
}

- (void)addNodeToHead:(_DoubleLinkNode *)node {
    _count++;
    if (_head) {
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    } else {
        _head = _tail = node;
    }
}

- (void)addNodeToTail:(_DoubleLinkNode *)node {
    _count++;
    if (_tail) {
        _tail->_next = node;
        node->_prev = _tail;
        _tail = node;
    } else {
        _head = _tail = node;
    }
}


- (void)moveNodeToHead:(_DoubleLinkNode *)node {
    if (_head == node) return;
    
    if (_tail == node) {
        _tail = node->_prev;
        _tail->_next = nil;
    } else {
        node->_next->_prev = node->_prev;
        node->_prev->_next = node->_next;
    }
    node->_next = _head;
    node->_prev = nil;
    _head->_prev = node;
    _head = node;
}

- (void)removeNode:(_DoubleLinkNode *)node {
    _count--;
    if (node->_next) node->_next->_prev = node->_prev;
    if (node->_prev) node->_prev->_next = node->_next;
    if (_head == node) _head = node->_next;
    if (_tail == node) _tail = node->_prev;
}

- (_DoubleLinkNode *)removeTailNode {
    if (!_tail) return nil;
    _DoubleLinkNode *tail = _tail;
    _count--;
    if (_head == _tail) {
        _head = _tail = nil;
    } else {
        _tail = _tail->_prev;
        _tail->_next = nil;
    }
    return tail;
}

- (BOOL)isEmpty {
    return _count == 0;
}

- (NSNumber *)lastValue {
   return _tail->_value;
}

- (NSNumber *)fisrtValue {
   return _head->_value;
}

- (void)removeLast {
    [self removeTailNode];
}

// 移除双链表首部
- (void)removeFirst {
    [self removeNode:_head];
}

// 双链表首部添加n
- (void)addValueToHead:(id)n {
    _DoubleLinkNode *node = [_DoubleLinkNode new];
    node->_value = n;
    [self addNodeToHead:node];
}
// 双链表尾部添加n
- (void)addValueToTail:(id)n {
    _DoubleLinkNode *node = [_DoubleLinkNode new];
    node->_value = n;
    [self addNodeToTail:node];
}

@end




@interface Deque() {
    _DoubleLink *_dLink;
    NSUInteger _numItems;
}

@end

@implementation Deque

- (instancetype)initWithCapacity:(NSUInteger)numItems {
    self = [super init];
    if (self) {
        _numItems = numItems;
        _dLink = [[_DoubleLink alloc] initWithCapacity:numItems];
    }
    return self;
}

// 获取第一个数据
- (id)fisrtValue {
    return [_dLink fisrtValue];
}
// 获取最后一个数据
- (id)lastValue {
    return [_dLink lastValue];
}

// 从头部添加数据
- (void)pushValueToHead:(id)n {
    [_dLink addValueToHead:n];
}

// 从头部删除数据
- (void)popValueFromHead {
    [_dLink removeFirst];
}

// 从尾部添加数据
- (void)pushValueToTail:(id)n {
    [_dLink addValueToTail:n];
}
// 从尾部删除数据
- (void)popValueFromTail {
    [_dLink removeLast];
}

- (NSString *)description {
    if (_numItems == 0) {
        return @"<empty cache>";
    }
    NSMutableString *all = [NSMutableString stringWithString:@"\n|------------LRUCache----------|\n"];

    _DoubleLinkNode *node = _dLink->_head;
    int index = 0;
    while (node) {
        [all appendString:[NSString stringWithFormat:@"|-%d-|----value:--%@--|\n",index, node->_value]];
        node = node->_next;
        index++;
    }
    return all;
}
@end

main.m
可实现 翻转字符串里的单词

#import <Foundation/Foundation.h>
#import "Deque.h"

int main(int argc, const char * argv[]) {
    NSString *str = @"leetcode is fun";
    Deque *deque = [[Deque alloc] initWithCapacity:100];

    NSArray *array = [str componentsSeparatedByCharactersInSet:[NSCharacterSet whitespaceCharacterSet]];

    [array enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        [deque pushValueToHead:obj];
    }];
    NSLog(@"%@", deque);
    return 0;
}

---

单调队列是双向队列的特殊情况，双向队列里所有的元素全部都是单调递增/递减的(元素有序)，称之为单调队列。

// Deque.h
- (void)enqueue:(NSNumber *)n;
- (void)dequeue:(NSNumber *)n;

// Deque.m
// implementation Deque
// 默认头比尾大(降序)
- (void)enqueue:(NSNumber *)n {
    // 将小于n的元素全部删除
    while (!_dLink.isEmpty && ([_dLink.lastValue compare: n] == NSOrderedAscending)) {
        [_dLink removeTailNode];
    }
    // 然后将 n 加入tail
    [_dLink addValueToTail:n];
}

- (void)dequeue:(NSNumber *)n {
    if ([n compare: _dLink.fisrtValue] == NSOrderedSame) {
        [_dLink removeFirst];
    }
}

面试题：滑动窗口最大值

题目解析

#import <Foundation/Foundation.h>
#import "Deque.h"

/**
 * nums: 要比较的数组
 * numsSize: 数组大小
 * k:  窗口长度
 */
NSArray* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    NSMutableArray *array = @[].mutableCopy;
    Deque *deque = [[Deque alloc] initWithCapacity:100];

    for (int i = 0; i < numsSize; i++) {
        if (i < k - 1) {
            //先填满窗口的前 k - 1
            [deque enqueue:@(nums[i])];
        } else {
            // 窗口向前滑动，加入新数字
            [deque enqueue:@(nums[i])];
            [array addObject:deque.fisrtValue];
            // 队列已经存在的fisrtValue是否超出当前窗口
            [deque dequeue:@(nums[i - k + 1])];
        }
    }
    return array;
}

int main(int argc, const char * argv[]) {
    int nums[] = {1,3,-1,-3,5,3,6,7};
    int returnSize = 0;
    NSArray *r = maxSlidingWindow(nums, 8, 3, &returnSize);
}