【基础】6、栈与队列

2014-02-06 | 阅读：

栈

一、简介

栈是一种特殊的线性表，只能在一端进行操作

往栈中添加元素的操作，一般叫做 push，入栈

从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）

后进先出的原则，Last In First Out，LIFO

注意：这里说的“栈”与内存中的“栈空间”是两个不同的概念

二、栈的接口设计与实现

1、接口设计

/// 获取栈中元素的数量
-(int)size;

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


/// 入栈
/// @param element 入栈元素
-(void)push:(nonnull id)element;


/// 出栈
-(id)pop;


/// 获取栈顶元素
-(id)top;


/// 清空
-(void)clear;

2、栈的内部实现是否可以直接利用以前学过的数据结构？动态数组/链表

@interface LCStack()
//@property(nonatomic,strong)LCLinkArray* linkArray;    //单向链表
//@property(nonatomic,strong)LCLinkArray2* linkArray;   //带头结点的单向链表
//@property(nonatomic,strong)LCLinkArray3* linkArray;   //双向链表
//@property(nonatomic,strong)LCSigleCycleLinkArray* linkArray;  //单向循环链表
@property(nonatomic,strong)LCBothCycleLinkArray * linkArray;    //双向循环链表
@end



@implementation LCStack

-(instancetype)init{
    self = [super init];
    if (self) {
        self.linkArray = [[LCBothCycleLinkArray alloc] init];
    }
    return self;
}


/// 获取栈中元素的数量
-(int)size{
    return self.linkArray.size;
}

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


/// 入栈
/// @param element 入栈元素
-(void)push:(nonnull id)element{
    
    [self.linkArray add:element];
}


/// 出栈
-(id)pop{
    return [self.linkArray remove:self.linkArray.size-1];
}


/// 获取栈顶元素
-(id)top{
    return [self.linkArray get:self.linkArray.size-1];
}


/// 清空
-(void)clear{
    [self.linkArray clear];
}


-(NSString *)description{
    NSMutableString * mString = [[NSMutableString alloc] init];
    [mString appendString:@"["];
    
    for (int i=0; i<self.linkArray.size; i++) {
        if (i !=0) {
            [mString appendString:@","];
        }
        
        id element = [self.linkArray get:i];
        [mString appendFormat:@"%@",element];
    }
    
    [mString appendString:@"]"];
    return mString;
}

三、栈的应用

1、浏览器的前进和后退

-(LCStack *)stack1{
    if (!_stack1) {
        _stack1 = [[LCStack alloc] init];
    }
    return _stack1;
}

-(LCStack *)stack2{
    if (!_stack2) {
        _stack2 = [[LCStack alloc] init];
    }
    return _stack2;
}


-(void)__inputWebSite:(NSString*)string{
    
    //只要有输入就清空stack2
    [self.stack2 clear];
    
    //入栈stack1
    [self.stack1 push:string];
    
    NSLog(@"element = %@",self.stack1.top);

}


-(void)__front{
    if (self.stack2.size == 0) {
        NSLog(@"无法再前进了");
        return;
    }
    
    //出栈stack2
    id element = self.stack2.pop;
    
    //入栈stack1
    [self.stack1 push:element];
    
    NSLog(@"element = %@",self.stack1.top);
}

-(void)__back{
    if (self.stack1.size == 1) {
        NSLog(@"无法再后退了");
        return;
    }

    //出栈stack1
    id element = self.stack1.pop;
    
    //入栈stack2
    [self.stack2 push:element];
    
    NSLog(@"element = %@",self.stack1.top);

}

2、类似的回退和撤销操作都可以使用该逻辑实现

队列

一、介绍

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

队尾（rear）：只能从队尾添加元素，一般叫做 enQueue，入队

队头（front）：只能从队头移除元素，一般叫做 deQueue，出队

先进先出的原则，First In First Out，FIFO

二、接口设计与实现

1、接口设计

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

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

/// 清空
-(void)clear;

/// 入队
/// @param element 入队元素
-(void)enQueue:(nonnull id)element;

/// 出队
-(id)deQueue;

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

2、队列的内部实现是否可以直接利用以前学过的数据结构？
动态数组、链表
优先使用双向链表，因为队列主要是往头尾操作元素

@interface LCQueue()
//@property(nonatomic,strong)LCLinkArray* linkArray;    //单向链表
//@property(nonatomic,strong)LCLinkArray2* linkArray;   //带头结点的单向链表
//@property(nonatomic,strong)LCLinkArray3* linkArray;   //双向链表
//@property(nonatomic,strong)LCSigleCycleLinkArray* linkArray;  //单向循环链表
@property(nonatomic,strong)LCBothCycleLinkArray * linkArray;    //双向循环链表
@end

@implementation LCQueue

-(instancetype)init{
    self = [super init];
    if (self) {
//        self.linkArray = [[LCLinkArray alloc] init];
//        self.linkArray = [[LCLinkArray2 alloc] init];
//        self.linkArray = [[LCLinkArray3 alloc] init];
//        self.linkArray = [[LCSigleCycleLinkArray alloc] init];

        self.linkArray = [[LCBothCycleLinkArray alloc] init];
    }
    return self;
}


/// 元素数量
-(int)size{
    return self.linkArray.size;
}


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


/// 清空
-(void)clear{
    [self.linkArray clear];
}


/// 入队
/// @param element 入队元素
-(void)enQueue:(nonnull id)element{
    [self.linkArray add:element];
}


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


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

-(NSString *)description{
    NSMutableString * mString = [[NSMutableString alloc] init];
    [mString appendString:@"["];
    
    //从队尾开始打印
    for (int i=self.linkArray.size-1; i>=0; i--) {
        id element = [self.linkArray get:i];
        [mString appendFormat:@"%@",element];
        
        if (i !=0) {
            [mString appendString:@","];
        }
    }
    
    [mString appendString:@"]"];
    return mString;
}
@end

三、双端队列

◼ 双端队列是能在头尾两端添加、删除的队列
英文 deque 是 double ended queue 的简称

双端队列的接口设计如下

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

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

/// 清空
-(void)clear;

/// 从队尾入队
/// @param element 入队元素
-(void)enQueueRear:(nonnull id)element;

/// 从队头出队，返回出队元素
-(id)deQueueFront;

/// 从队头入队
/// @param element 入队元素
-(void)enQueueFront:(nonnull id)element;

/// 从队尾出队，返回出队元素
-(id)deQueueRear;

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

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

四、循环队列

◼ 其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度

◼ 这个用数组实现并且优化之后的队列也叫做：循环队列

五、循环双端队列

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

栈与队列的相互实现

一、用队列实现一个栈

#import "LCStackByQueue.h"

#include <queue>
#include <iostream>
using namespace std;


@interface LCStackByQueue()<NSMutableCopying,NSCopying>

@end



@implementation LCStackByQueue{
    queue<id>* _queue;
}

-(queue<id>*)queue{
    if (_queue == nullptr) {
        _queue = new queue<id>();
    }
    return _queue;
}

-(void)setQueue:(queue<id>*)queue{
    if (_queue) {
        delete _queue;
    }
    _queue = queue;
}




/// 获取栈中元素的数量
-(int)size{
    return (int)self.queue->size();
}

/// 是否为空
-(BOOL)isEmpty{
    return self.queue->empty();
}


/// 入栈
/// @param element 入栈元素
-(void)push:(nonnull id)element{
    //从队尾添加元素
    self.queue->push(element);
}


/// 出栈
-(id)pop{
    
    //取出队尾元素
    id val = self.queue->back();
    
    //pop队尾元素
    for (int i=0; i<self.queue->size()-1; i++) {
        self.queue->push(self.queue->front());
        self.queue->pop();
    }
    self.queue->pop();
    
    //返回队尾元素
    return val;
}


/// 获取栈顶元素
-(id)top{
    return self.queue->back();
}


/// 清空
-(void)clear{
    while (self.queue->size()) {
        self.queue->pop();
    }
}


-(id)copyWithZone:(NSZone *)zone{
    return [self mutableCopy];
}


-(id)mutableCopyWithZone:(NSZone *)zone{
   
    LCStackByQueue * copyStack = [[LCStackByQueue alloc] init];
    
    for (int i=0; i<self.queue->size(); i++) {
        id element = self.queue->front();
        [copyStack  push:element];
        self.queue->push(element);
        self.queue->pop();
    }
    
    return copyStack;
}


-(NSString *)description{
    NSMutableString * mString = [[NSMutableString alloc] init];
    [mString appendString:@"栈底["];


    for (int i=0; i<self.queue->size(); i++) {
        if (i !=0) {
            [mString appendString:@","];
        }
        NSString * element = [NSString stringWithFormat:@"%@" ,self.queue->front()];
        [mString appendString:element];
        self.queue->push(self.queue->front());
        self.queue->pop();
    }

    [mString appendString:@"]栈顶"];
    return mString;
}


-(void)dealloc{
    self.queue = nil;
}
@end

二、用栈来实现一个队列

◼ 准备2个栈：inStack、outStack
入队时，
push 到 inStack 中

出队时
✓ 如果 outStack 为空，将 inStack 所有元素逐一弹出，push 到 outStack，outStack 弹出栈顶元素
✓ 如果 outStack 不为空， outStack 弹出栈顶元素

#import "LCQueueByStack.h"
#import "LCStack.h"
@interface LCQueueByStack()
//可以用C++提供的 #include <stack>;来实现，我们就用自己实现的LCStack来实现
@property(nonatomic,strong)LCStack * inStack;
@property(nonatomic,strong)LCStack * outStack;
@end

@implementation LCQueueByStack

-(instancetype)init{
    self = [super init];
    if (self) {
        self.inStack = [[LCStack alloc] init];
        self.outStack = [[LCStack alloc] init];
    }
    return self;
}


/// 元素数量
-(int)size{
    return self.inStack.size + self.outStack.size;
}


/// 是否为空
-(BOOL)isEmpty{
    return self.inStack.isEmpty&&self.outStack.isEmpty;
}


/// 清空
-(void)clear{
    [self.inStack clear];
    [self.outStack clear];

}


/// 入队
/// @param element 入队元素
-(void)enQueue:(nonnull id)element{
    [self.inStack push:element];
}


/// 出队
-(id)deQueue{
    if (self.outStack.isEmpty) {
        while (!self.inStack.isEmpty) {
            [self.outStack push:[self.inStack pop]];
        }
    }
    return [self.outStack pop];
}


/// 获取队列的头元素
-(id)front{
    if (self.outStack.isEmpty) {
        while (!self.inStack.isEmpty) {
            [self.outStack push:[self.inStack pop]];
        }
    }
    return [self.outStack top];
}


-(NSString *)description{
    
    LCStack * newinStack = [self.inStack copy];
    LCStack * newoutStack = [self.outStack copy];
    
    NSMutableString * mString = [[NSMutableString alloc] init];
    [mString appendString:@"["];
    
    
    int insize  = newinStack.size;
    int outSize = newoutStack.size;

    for (int i=0; i<insize+outSize; i++) {
        if (i!=0) {
            [mString appendString:@","];
        }
        
        //从队尾开始打印
//        if (i<insize) {
//            id element = [newinStack pop];
//            [mString appendFormat:@"%@",element];
//        }else{
//            while (!newoutStack.isEmpty) {
//                [newinStack push:[newoutStack pop]];
//            }
//
//            id element = [newinStack pop];
//            [mString appendFormat:@"%@",element];
//        }
        
        if (i==insize){
            while (!newoutStack.isEmpty) {
                [newinStack push:[newoutStack pop]];
            }
        }
        id element = [newinStack pop];
        [mString appendFormat:@"%@",element];

    }
        
    
    [mString appendString:@"]"];
    return mString;
}
@end

行者常至，为者常成！

JHHK

JHHK

【基础】6、栈与队列

目录

栈

队列

栈与队列的相互实现