数据结构与算法之栈(四)

作者: 路飞_Luck | 来源:发表于2019-05-12 15:55 被阅读24次

Android面试题总结（题目+复习链接）
100天iOS数据结构与算法实战 Day02 - 栈
数据结构与算法（栈实现篇）
数据结构与算法
2019-07-11—栈
数据结构与算法之栈(四)
100天iOS数据结构与算法实战 Day04 - 栈的算法实战
栈
集合相关数据结构与算法
数据结构与算法学习开篇

一目录

栈的介绍
栈的接口设计
栈的应用 - 浏览器前进后退
栈的使用 - 匹配有效括号
栈相关面试题

二简介

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

名词介绍
入栈：往栈中添加元素的操作，一般叫push，入栈
出栈：从栈中移除元素的操作，一般叫pop，出栈，只能移除栈顶元素，也叫弹出栈顶元素
后进先出的原则，Last In First Out， LIFO

栈.png

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

三栈的接口设计

- (NSUInteger)size：元素的数量
- (bool)isEmpt：是否为空
- (void)push:(id)element;：入栈
- (id)pop：出栈
- (id)top：获取栈顶元素

核心代码如下

Stack.h

@interface Stack : NSObject

/// 长度
- (int)size;

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

/// 入栈
- (void)push:(id)element;

/// 出栈
- (id)pop;

/// 返回栈顶元素
- (id)top;

@end

Stack.m

@implementation Stack {
    ArrayList *_arrayList;
}

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

/// 长度
- (int)size {
    return [_arrayList size];
}

/// 是否为空
- (bool)isEmpty {
    return [_arrayList isEmpty];
}

/// 入栈
- (void)push:(id)element {
    [_arrayList add:element];
}

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

/// 返回栈顶元素
- (id)top {
    return [_arrayList get:_arrayList.size - 1];
}

代码测试

- (void)stackTest {
    Stack *stack = [[Stack alloc] init];
    [stack push:@11];
    [stack push:@12];
    [stack push:@13];
    [stack push:@14];
    
    while (!stack.isEmpty) {
        NSLog(@"%@",stack.pop);
    }
}

运行结果

image.png

四栈的应用 - 浏览器的前进与后退

image.png

使用了两个栈来存储数据

五栈的使用

5.1 有效的括号

我们这个问题中将要处理的表达式可以包含以下三种不同类型的括号：

()
{}
[]

image.png

算法

初始化栈 S。
一次处理表达式的每个括号。
如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的子表达式。
如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个相同类型的左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

核心代码如下

// 括号有效性匹配
- (bool)bracketValid:(NSString *)bracket {
    Stack *sta = [[Stack alloc] init];
    
    for (int i = 0; i < bracket.length; i++) {
        NSString *bra = [bracket substringWithRange:NSMakeRange(i, 1)];
        if ([self.map.allKeys containsObject:bra]) {    // 左括号
            [sta push:bra];
        } else {    // 右括号
            if (sta.isEmpty) {
                return false;
            }
            NSString *left = sta.pop;
            if (![bra isEqualToString:[self.map objectForKey:left]]) {
                return false;
            }
        }
    }
    
    // 是否为空
    return sta.isEmpty;
}

- (NSDictionary *)map {
    if (_map == nil) {
        _map = @{@"(":@")",
                 @"{":@"}",
                 @"[":@"]"
                 };
    }
    return _map;
}

测试代码如下

// 括号有效性匹配
NSArray *strs = @[@"{{({[]})}}",
                  @"{[}",
                  @"}()[]"];
for (NSString *str in strs) {
    NSLog(@"%@ is valid %d",str,[self bracketValid:str]);
}

运行结果如下: