转载

数据结构-栈

序言

链表、栈和队列是非常基本的数据结构，万丈高楼平地起，让我们一起来打好基础。本篇文章专门来学习栈的特性及如何用ObjC和Swift设计封装一个栈类。虽然在iOS开发中，几乎没有使用到栈这种数据结构，但是，我们还是要好好地学习栈的特性，通过学习栈的相关思想来提高个人对算法的基本理解。

栈（Stack）的特性

栈是非常典型的ADT（抽象数据类型），在使用栈时通常是需要明确指定数据类型的。

栈的特性：后进先出（First-in-last-out）

常用的栈操作：

empty – 判空
push – 入栈
peek – 查看栈顶
pop – 弹出栈顶元素。在栈为空的时候执行pop，会导致underflow（下溢）

栈的实现方式：

数组实现：需要一个变量来标记栈顶位置
链表实现：插入元素时对表头操作需要注意

关于数组实现栈的push、pop如下图：

数据结构-栈

常见的栈应用题目：

括号匹配
翻转字符串
模拟递归（N皇后问题）

封装抽象类的原则

Understand it Abstractly：理解它的抽象
Write a Specification：写好规格说明。每个方法应该有明确的前置条件和后置条件及输出。
Write Applications：根据规格说明使用我们设计的数据结构
Select, Design, Implement：选择、设计和实现数据结构
Analyze the Implementation：分析实现

ObjC尝试封装栈类

  @interfaceHYBStack: NSObject   - (id)pop; - (BOOL)push:(id)t; - (id)peek; - (BOOL)isEmpty;   @end   // //  HYBStack.m //  DataAgorithmDemos // //  Created by huangyibiao on 16/3/9. //  Copyright © 2016年 huangyibiao. All rights reserved. //   #import "HYBStack.h"   #define kMaxStackCount 10   @interface HYBStack ()   // 通过数组来实现栈 @property (nonatomic, strong) NSMutableArray *list; // 指向栈顶的索引 @property (nonatomic, assign) NSInteger top;   @end   @implementation HYBStack   - (instancetype)init {   if (self = [super init]) {     self.top = -1;   }      return self; }   - (BOOL)isEmpty {   return self.top == -1; }   - (BOOL)push:(id)t {   if (self.top + 1 >= kMaxStackCount) {     // 上溢     NSException *exception = [NSExceptionexceptionWithName:@"push stack"                                                      reason:@"Overflow"                                                    userInfo:nil];     @throw exception;   }      self.list[++self.top] = t;      return YES; }   - (id)pop {   if ([self isEmpty]) {     // 下溢     NSException *exception = [NSExceptionexceptionWithName:@"pop stack"                                                      reason:@"Underflow"                                                    userInfo:nil];     @throw exception;   }      return self.list[self.top--]; }   - (id)peek {   if ([self isEmpty]) {     NSException *exception = [NSExceptionexceptionWithName:@"pop stack"                                                      reason:@"Underflow"                                                    userInfo:nil];     @throw exception;   }      return self.list[self.top]; }   - (NSMutableArray *)list {   if (_list == nil) {     _list = [[NSMutableArray alloc]initWithCapacity:kMaxStackCount];   }      return _list; }   @end

在下溢、上溢时，都抛出异常，以确保程序的健壮性。

Swft尝试封装栈

由于Swift中的数组可以是可变的，因此这里没有使用top来标识指向栈顶：

  publicstruct Stack<Element> {   privatevaritems = [Element]()      publicfuncisEmpty() ->Bool {     return items.isEmpty;   }      publicinit() {        }      mutatingpublicfuncpush(item: Element)  {     items.append(item)   }      mutatingpublicfuncpop() ->Element? {     if isEmpty() {       return nil     }          return items.removeLast()   }      publicfuncpeek() ->Element? {     return items.last   } }

如果要更深入地学习栈，还得使用纯C语言来实现。因为高级一些的语言，提供了可变的数组，没有必要像C语言那样操作。Swift版与OC版本实现上有一点点不同，就是OC版尝试抛异常。而Swift版没有抛出异常，而是通过判断是否为nil代表成功与失败。

参考

基本数据结构与算法

关注我

关注	账号	备注
标哥博客iOS交流群一	324400294（满）	群一若已满，请申请群二
标哥博客iOS交流群二	494669518（满）	群二若已满，请申请群三
标哥博客iOS交流群三	461252383（满）	群三若已满，请申请群四
标哥博客iOS交流群四	250351140	群四若已满，会有提示信息
关注微信公众号	iOSDevShares	关注微信公众号，会定期地推送好文章
关注新浪微博账号	标哥的技术博客	关注微博，每次发布文章都会分享到新浪微博
关注标哥的GitHub	CoderJackyHuang	这里有很多的Demo和开源组件
关于我	进一步了解标哥	如果觉得文章对您很有帮助，可捐助我！