iOS - 栈的实现

序言

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

image.png

因为 OC 中没有栈的概念，所以本文讲解如何使用 OC 代码实现栈。

栈的实现

• Stack.h

/**
 定义block
 @param obj 回调值
 */
typedef void(^StackBlock)(id obj);

/**
 模拟栈实现 - 简单实现
 */
@interface Stack : NSObject

/** 入栈 @param obj 指定入栈对象 */
- (void)push:(id)obj;

/** 出栈 */
- (id)popObj;

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

/** 栈的长度 */
- (NSInteger)stackLength;

/** 从栈底开始遍历 @param block 回调遍历的结果 */
-(void)enumerateObjectsFromBottom:(StackBlock)block;

/** 从顶部开始遍历 */
-(void)enumerateObjectsFromtop:(StackBlock)block;

/** 所有元素出栈，一边出栈一边返回元素 */
-(void)enumerateObjectsPopStack:(StackBlock)block;

/** 清空 */
-(void)removeAllObjects;

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

@end

• Stack.m

@interface Stack ()
// 存储栈数据
@property (nonatomic, strong) NSMutableArray *stackArray;

@end

@implementation Stack

#pragma mark - push

- (void)push:(id)obj {
    [self.stackArray addObject:obj];
}

#pragma mark - get

- (id)popObj {
    if ([self isEmpty]) {
        return nil;
    } else {
        id lastObject = self.stackArray.lastObject;
        [self.stackArray removeLastObject];
        return lastObject;
    }
}

-(id)topObj {
    if ([self isEmpty]) {
        return nil;
    } else {
        return self.stackArray.lastObject;
    }
}

- (BOOL)isEmpty {
    return !self.stackArray.count;
}

- (NSInteger)stackLength {
    return self.stackArray.count;
}

#pragma mark - 遍历

// 从栈底开始遍历
-(void)enumerateObjectsFromBottom:(StackBlock)block {
    [self.stackArray enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        block ? block(obj) : nil;
    }];
}

// 从顶部开始遍历
-(void)enumerateObjectsFromtop:(StackBlock)block {
    [self.stackArray enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        block ? block(obj) : nil;
    }];
}

// 所有元素出栈，一边出栈一边返回元素
-(void)enumerateObjectsPopStack:(StackBlock)block {
    __weak typeof(self) weakSelf = self;
    NSUInteger count = self.stackArray.count;
    for (NSUInteger i = count; i > 0; i --) {
        if (block) {
            block(weakSelf.stackArray.lastObject);
            [self.stackArray removeLastObject];
        }
    }
}

#pragma mark - remove

-(void)removeAllObjects {
    [self.stackArray removeAllObjects];
}

#pragma mark - lazy

- (NSMutableArray *)stackArray {
    if (!_stackArray) {
        _stackArray = [NSMutableArray array];
    }
    return _stackArray;
}

@end

题目描述 从尾到头打印链表

输入链表的第一个节点，从尾到头反过来打印出每个结点的值。

image.png

解题思路

• 使用栈
• 本文还使用到链表的实现，详情参考iOS - 节点,链表的实现

详细代码如下

/** 使用栈 */
+ (NSArray *)printListFromTailToHeadByShed:(NSArray *)numbers {
    LinkedArray *linkedArray = [[LinkedArray alloc] initLiknedArrayWithNunbers:numbers];
    // 第一个节点
    ListNode *listNode = [linkedArray getFirstListNode];
    
    return [self getListFromTailToHead:listNode];
}

// 使用栈
+ (NSArray *)getListFromTailToHead:(ListNode *)listNode {
    // 创建一个栈
    Stack *stack = [[Stack alloc] init];
    
    // 开始从第一个节点依次往后遍历,将数据全部入栈
    while (listNode != nil) {
        [stack push:listNode.content];
        listNode = listNode.next;
    }
    
    NSMutableArray *values = [NSMutableArray array];
    // 依次将栈出列并存储
    while (!stack.isEmpty) {
        [values addObject:stack.popObj];
    }
    
    return values.copy;
}

测试案例代码

// 1.使用栈
NSArray *arr = [PrintListFromTailToHead_06 printListFromTailToHeadByShed:@[@1,@2,@3]];
NSLog(@"arr = %@",arr);

运行结果

链表反转.png

---

如有错误，欢迎指正，多多点赞，打赏更佳，您的支持是我写作的动力。

---

项目连接地址 - ArithmeticDemo