数据结构与算法之队列(五)

2019-05-14 本文已影响105人路飞_Luck

一简介

队列是一种特殊的线性表，只能在头尾两端进行操作

队尾(rear)：只能从队尾添加元素，一般叫enQueue，入队
队头(front)：只能从队头移除元素，一般叫deQueue，出队
先进先出的原则，First In First Out，FIFO

image.png

二队列的接口设计

- (int)size：元素的数量
- (BOOL)isEmpty：是否为空
- (void)clear：清空
- (void)enQueue:(id)element：入队
- (id)deQueue：出队
- (id)front：获取队列的头元素

队列的内部实现是否可以直接使用之前学过的数据结构？

优先使用双向链表，因为队列主要是往头尾操作元素

核心代码如下

Queue.m

@implementation Queue {
    LinkedList *_linkList;
}

- (instancetype)init {
    self = [super init];
    if (self) {
        _linkList = [[LinkedList alloc] init];
    }
    return self;
}

/// 元素的数量
- (int)size {
    return _linkList.size;
}

/// 是否为空
- (BOOL)isEmpty {
    return [_linkList isEmpty];
}

/// 清空
- (void)clear {
    [_linkList clear];
}

/// 入队
- (void)enQueue:(id)element {
    [_linkList add:element];
}

/// 出队
- (id)deQueue {
    return [_linkList remove:0];
}

/// 获取队列的头元素
- (id)front {
    return [_linkList get:0];
}

测试代码

/// queue test
- (void)queueTest {
    Queue *qu = [[Queue alloc] init];
    [qu enQueue:@(11)];
    [qu enQueue:@(22)];
    [qu enQueue:@(33)];
    [qu enQueue:@(44)];
    
    while (!qu.isEmpty) {
        NSLog(@"%@",[qu deQueue]);
    }
}

运行结果

队列.png

三用栈实现队列

232. 用栈实现队列

思路：
准备两个栈：inStack，outStack

1.入队时，push到inStack中
2.出队时
- 2.1 如果outStack为空，将inStack所有元素逐一弹出，push到outStack，outStack弹出栈顶元素
- 2.2 如果outStack不为空，outStack弹出栈顶元素

image.png

核心代码如下

QueueStack.m

@implementation QueueStack {
    Stack *_inStack;
    Stack *_outStack;
}

- (instancetype)init {
    self = [super init];
    if (self) {
        _inStack = [[Stack alloc] init];
        _outStack = [[Stack alloc] init];
    }
    return self;
}

/// 元素的数量
- (int)size {
    return _inStack.size + _outStack.size;
}

/// 是否为空
- (BOOL)isEmpty {
    return _inStack.isEmpty && _outStack.isEmpty;
}

/// 清空
- (void)clear {
    while (_inStack.top) {
        [_inStack pop];
    }
    while (_outStack.top) {
        [_outStack pop];
    }
}

/// 入队
- (void)enQueue:(id)element {
    [_inStack push:element];
}

/// 出队
- (id)deQueue {
    if (!_outStack.isEmpty) {
        return [_outStack pop];
    }
    while (_inStack.top) {  // 将inStack的元素全部压入outStack
        [_outStack push:[_inStack pop]];
    }
    // 再弹出outStack栈顶元素
    return [_outStack pop];
}

/// 获取队列的头元素
- (id)front {
    if (!_outStack.isEmpty) {
        return _outStack.top;
    }
    while (_inStack.top) {  // 将inStack的元素全部压入outStack
        [_outStack push:[_inStack pop]];
    }
    // 再弹出outStack栈顶元素
    return _outStack.top;
}

@end

测试代码

// 用栈实现队列操作
- (void)queueStackTest {
    Queue *qu = [[Queue alloc] init];
    [qu enQueue:@(11)];
    [qu enQueue:@(22)];
    [qu deQueue];
    [qu enQueue:@(33)];
    [qu deQueue];
    
    while (!qu.isEmpty) {
        NSLog(@"%@",[qu deQueue]);
    }
}

运行结果

栈实现队列.png

四双端队列(double ended queue - Deque)

双端队列是能在头尾两端添加，删除的队列

接口设计

/// 元素的数量
- (int)size;

/// 是否为空
- (BOOL)isEmpty;

/// 清空
- (void)clear;

/// 从后面入队
- (void)enQueueRear:(id)element;

/// 从后面出队
- (id)deQueueRear;

/// 从前面入队
- (void)enQueueFront:(id)element;

/// 从前面出队
- (id)deQueueFront;

/// 获取队列的头元素
- (id)front;

/// 获取队列的尾元素
- (id)rear;

代码实现 Deque.m

@implementation Deque {
    LinkedList *_linkList;
}

- (instancetype)init {
    self = [super init];
    if (self) {
        _linkList = [[LinkedList alloc] init];
    }
    return self;
}

/// 元素的数量
- (int)size {
    return _linkList.size;
}

/// 是否为空
- (BOOL)isEmpty {
    return _linkList.isEmpty;
}

/// 清空
- (void)clear {
    [_linkList clear];
}

/// 从后面入队
- (void)enQueueRear:(id)element {
    [_linkList add:element];
}

/// 从后面出队
- (id)deQueueRear {
    return [_linkList remove:_linkList.size - 1];
}

/// 从前面入队
- (void)enQueueFront:(id)element {
    [_linkList add:0 element:element];
}

/// 从前面出队
- (id)deQueueFront {
    return [_linkList remove:0];
}

/// 获取队列的头元素
- (id)front {
    return [_linkList get:0];
}

/// 获取队列的尾元素
- (id)rear {
    return [_linkList get:_linkList.size - 1];
}

@end

测试代码

//  双端队列
- (void)deQueueTest {
    Deque *qu = [[Deque alloc] init];
    [qu enQueueFront:@(11)];
    [qu enQueueFront:@(22)];
    [qu enQueueRear:@(33)];
    [qu enQueueRear:@(44)];
    
    /**  尾 44 33 11 22 */
    while (!qu.isEmpty) {
        NSLog(@"%@",[qu deQueueRear]);
    }
}

运行结果如下：

双端队列.png

更多详细代码查看Deque类

五循环队列(Circle Queue)

用数组实现并且优化之后的队列称之为循环队列

循环队列.png

循环双端队列:可以进行两端添加，删除操作的循环队列

核心代码实现

static int kDefaultCapacity = 10;   // 默认元素个数

@implementation CircleQueue {
    int _front;
    int _size;
    NSMutableArray *_elements;
}

- (instancetype)init {
    self = [super init];
    if (self) {
        _elements = [NSMutableArray array];
        for (int i = 0; i < kDefaultCapacity; i++) {
            [_elements addObject:@(-1)];
        }
    }
    return self;
}

/// 元素的数量
- (int)size {
    return _size;
}

/// 是否为空
- (BOOL)isEmpty {
    return _size == 0;
}

/// 清空
- (void)clear {
    [_elements removeAllObjects];
    _front = 0;
    _size = 0;
}

/// 入队
- (void)enQueue:(id)element {
    [self ensureCapacity:_size + 1];
    
    int index = [self getIndex:_size];
    _elements[index] = element;
    _size++;
}

/// 出队
- (id)deQueue {
    id frontElement = _elements[_front];
    _elements[_front] = @(-1);    // 头节点位置置空
    _front = [self getIndex:1];
    _size--;
    return frontElement;
}

/// 获取队列的头元素
- (id)front {
    return _elements[_front];
}

- (NSString *)description {
    NSMutableString *strM = [NSMutableString string];
    [strM appendString:[NSString stringWithFormat:@"capcacity = %lu,",(unsigned long)_elements.count]];
    [strM appendString:[NSString stringWithFormat:@"size = %d,",_size]];
    [strM appendString:[NSString stringWithFormat:@"front = %d,",_front]];
    [strM appendString:@", ["];
    
    for (int i = 0; i < _elements.count; i++) {
        if (i != 0) {
            [strM appendString:@","];
        }
        [strM appendFormat:@"%@",_elements[i]];
    }
    [strM appendString:@"]"];
    return strM.copy;
}

#pragma mark - private

- (int)getIndex:(int)index {
    // 因为一直在循环,所以需要取模
    index += _front;    // 先加上头位置索引
    
    // 返回正确插入位置索引
    return index - (index >= _elements.count ? _elements.count : 0);
}

/** 保证要有capacity的容量 */
- (void)ensureCapacity:(int)capacity {
    NSInteger oldCapactity = _elements.count;
    if (oldCapactity >= capacity) {
        return;
    }
    
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapactity + oldCapactity * 0.5;
    NSMutableArray *newElements = [NSMutableArray array];
    for (int i = 0; i < newCapacity; i++) {
        [newElements addObject:@(-1)];
    }
    // 恢复旧值
    for (int i = 0; i < _size; i++) {
        newElements[i] = _elements[i];
    }
    _elements = newElements;
    
    // 重置front
    _front = 0;
}

@end

测试代码

// 循环队列测试
- (void)circleQueueTest {
    CircleQueue *queue = [[CircleQueue alloc] init];
    // 0 1 2 3 4 5 6 7 8 9
    for (int i = 0; i < 10; i++) {
        [queue enQueue:@(i)];
    }
    NSLog(@"%@",[queue description]);
    
    // null null null null null 5 6 7 8 9
    for (int i = 0; i < 5; i++) {
        [queue deQueue];
    }
    NSLog(@"%@",[queue description]);
    
    // 15 16 17 18 19 5 6 7 8 9
    for (int i = 15; i < 20; i++) {
        [queue enQueue:@(i)];
    }
    NSLog(@"%@",[queue description]);
    
    while (!queue.isEmpty) {
        NSLog(@"%@",queue.deQueue);
    }
    
    NSLog(@"%@",[queue description]);
}

运行结果如下：

image.png

注意几个方法的实现

/// 获取真正插入位置的索引
- (int)getIndex:(int)index;

/** 保证要有capacity的容量 */
- (void)ensureCapacity:(int)capacity;

更多详细代码查看CircleQueue类

六循环双端队列

核心代码如下

static int kDefaultCapacity = 10;   // 默认元素个数

@implementation CircleDeque {
    int _front;
    int _size;
    NSMutableArray *_elements;
}

- (instancetype)init {
    self = [super init];
    if (self) {
        _elements = [NSMutableArray array];
        for (int i = 0; i < kDefaultCapacity; i++) {
            [_elements addObject:@(-1)];
        }
    }
    return self;
}

/// 元素的数量
- (int)size {
    return _size;
}

/// 是否为空
- (BOOL)isEmpty {
    return _size == 0;
}

/// 清空
- (void)clear {
    [_elements removeAllObjects];
    _front = 0;
    _size = 0;
}

/// 从后面入队
- (void)enQueueRear:(id)element {
    [self ensureCapacity:_size + 1];
    
    int index = [self getIndex:_size];
    _elements[index] = element;
    _size++;
}

/// 从后面出队
- (id)deQueueRear {
    int rearIndex = [self getIndex:_size - 1];
    id rearElement = _elements[rearIndex];
    _elements[rearIndex] = @(-1);    // 头节点位置置空
    _size--;
    return rearElement;
}

/// 从头部入队
- (void)enQueueFront:(id)element {
    [self ensureCapacity:_size + 1];
    
    _front = [self getIndex:-1];
    _elements[_front] = element;
    _size++;
}

/// 从头部出队
- (id)deQueueFront {
    id frontElement = _elements[_front];
    _elements[_front] = @(-1);    // 头节点位置置空
    _front = [self getIndex:1];
    _size--;
    return frontElement;
}

/// 获取队列的头元素
- (id)front {
    return _elements[_front];
}

/// 获取队列的尾元素
- (id)rear {
    int index = [self getIndex:_size - 1];
    return _elements[index];
}

- (NSString *)description {
    NSMutableString *strM = [NSMutableString string];
    [strM appendString:[NSString stringWithFormat:@"capcacity = %lu,",(unsigned long)_elements.count]];
    [strM appendString:[NSString stringWithFormat:@"size = %d,",_size]];
    [strM appendString:[NSString stringWithFormat:@"front = %d,",_front]];
    [strM appendString:@", ["];
    
    for (int i = 0; i < _elements.count; i++) {
        if (i != 0) {
            [strM appendString:@","];
        }
        [strM appendFormat:@"%@",_elements[i]];
    }
    [strM appendString:@"]"];
    return strM.copy;
}

#pragma mark - private

/// 获取真正插入位置的索引
- (int)getIndex:(int)index {
    // 因为一直在循环,所以需要取模
    index += _front;    // 先加上头位置索引
    if (index < 0) {
        return index + _elements.count;
    }
    
    // 返回正确插入位置索引
    return index - (index >= _elements.count ? _elements.count : 0);
}

/** 保证要有capacity的容量 */
- (void)ensureCapacity:(int)capacity {
    NSInteger oldCapactity = _elements.count;
    if (oldCapactity >= capacity) {
        return;
    }
    
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapactity + oldCapactity * 0.5;
    NSMutableArray *newElements = [NSMutableArray array];
    for (int i = 0; i < newCapacity; i++) {
        [newElements addObject:@(-1)];
    }
    // 恢复旧值
    for (int i = 0; i < _size; i++) {
        newElements[i] = _elements[i];
    }
    _elements = newElements;
    
    // 重置front
    _front = 0;
}
@end

测试代码如下

// 双端循环队列测试
- (void)circleDequeTest {
    CircleDeque *queue = [[CircleDeque alloc] init];
    
    // 头5 4 3 2 1  100 101 102 103 104 105 106 8 7 6 尾
    
    // 头 8 7 6  5 4 3 2 1  100 101 102 103 104 105 106 107 108 109 null null 10 9 尾
    for (int i = 0; i < 10; i++) {
        [queue enQueueFront:@(i + 1)];
        [queue enQueueRear:@(i + 100)];
    }
    NSLog(@"%@",[queue description]);
    
    // 头 null 7 6  5 4 3 2 1  100 101 102 103 104 105 106 null null null null null null null 尾
    for (int i = 0; i < 3; i++) {
        [queue deQueueFront];
        [queue deQueueRear];
    }
    NSLog(@"%@",[queue description]);
    
    // 头 11 7 6  5 4 3 2 1  100 101 102 103 104 105 106 null null null null null null 12 尾
    [queue enQueueFront:@(11)];
    [queue enQueueFront:@(12)];
    NSLog(@"%@",[queue description]);
    
    while (!queue.isEmpty) {
        NSLog(@"%@",queue.deQueueFront);
    }
    
    NSLog(@"%@",[queue description]);
}

运行结果如下:

image.png

更多详细代码参考CircleDeque类

七 %运算符优化

尽量避免使用 乘*，除/，模%，浮点数运算，效率低下

本文会持续更新中，更多精彩内容敬请期待。

本文参考 MJ老师的恋上数据结构与算法

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。

项目连接链接 - 08_Queue

数据结构与算法之队列(五)

目录

一简介

二队列的接口设计

三用栈实现队列

232. 用栈实现队列

四双端队列(double ended queue - Deque)

五循环队列(Circle Queue)

六循环双端队列

七 %运算符优化

猜你喜欢

热点阅读

数据结构与算法之队列(五)

目录

一 简介

二 队列的接口设计

三 用栈实现队列

232. 用栈实现队列

四 双端队列(double ended queue - Deque)

五 循环队列(Circle Queue)

六 循环双端队列

七 %运算符优化

猜你喜欢

热点阅读

一简介

二队列的接口设计

三用栈实现队列

四双端队列(double ended queue - Deque)

五循环队列(Circle Queue)

六循环双端队列