转载

数据结构-栈

序言

链表、栈和队列是非常基本的数据结构,万丈高楼平地起,让我们一起来打好基础。本篇文章专门来学习栈的特性及如何用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和开源组件
关于我 进一步了解标哥 如果觉得文章对您很有帮助,可捐助我!
原文  http://www.henishuo.com/data-struct-stack/
正文到此结束
Loading...