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

一 目录

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

二 简介

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

名词介绍
入栈：往栈中添加元素的操作，一般叫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 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]);
}

运行结果如下:

image.png

六 相关面试题如下

856. 括号的分数

150. 逆波兰表达式求值

224. 基本计算器

---

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

---

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

---

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

---

项目连接链接 - 07_Stack