题目:

输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

思路:

解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。

判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

代码:

自定义栈:

#import <Foundation/Foundation.h>

// 只要参数是一个id类型的block
typedef void (^StackBlock)(id objc);

@interface NSCustomStack : NSObject
// 入栈
-(void)push:(id)objet;
// 出栈
-(id)popTopElement;
// 返回栈顶元素
-(id)TopElement;
// 是否为空
-(BOOL)isEmpty;
// 栈的长度
-(NSInteger)stackLength;
// 遍历，从栈底开始遍历
-(void)traversalElementFromBottom:(StackBlock)block;
// 从顶部开始遍历
-(void)traversalElementFromtop:(StackBlock)block;
// 所有元素出栈，一边出栈一边返回元素
-(void)traversalElementPopStack:(StackBlock)block;
// 清空
-(void)removeAllObjects;
// 返回栈顶元素
-(id)topElemet;
@end

#import "NSCustomStack.h"

@interface NSCustomStack()

// 有入栈就有出栈的时候，使用强引用，就要记得释放引用
/** NSMutableArray */
@property (nonatomic,strong)NSMutableArray *stackArray;

/** top of stack */
@property (nonatomic,assign)NSInteger top;

@end
@implementation NSCustomStack

#pragma mark --------------- Public Methods

// 入栈
-(void)push:(id)objet{
    [self.stackArray addObject:objet];
}

// 出栈
-(id)popTopElement{
    id objc = [self.stackArray lastObject];
    [self.stackArray removeLastObject];
    return objc;
}

// 返回栈顶元素
-(id)TopElement{
    return [self.stackArray lastObject];
}

// 是否为空
-(BOOL)isEmpty{
    return !self.stackArray.count;
}

// 栈的长度
-(NSInteger)stackLength{
    return self.stackArray.count;
}

// 从底部开始遍历
-(void)traversalElementFromBottom:(StackBlock)block{
    NSEnumerator *objc = [self.stackArray objectEnumerator];
    for (id element in objc) {
        block(element);
    }
}

// 从顶部开始遍历
-(void)traversalElementFromtop:(StackBlock)block{
    // 先获取存储元素的个数
    NSInteger count = self.stackArray.count;
    for (NSInteger i = count - 1; i >= 0; i --) {
        // 处理最后一个元素
        block([self.stackArray objectAtIndex:i]);
    }
}

// 所有元素出栈，同时遍历
-(void)traversalElementPopStack:(StackBlock)block{
    // 先获取存储元素的个数
    NSInteger count = self.stackArray.count;
    for (NSInteger i = count - 1; i >= 0; i --) {
        // 处理最后一个元素
        block(self.stackArray.lastObject);
        [self.stackArray removeLastObject];
    }
}

// 返回栈顶元素
-(id)topElemet{
    return self.stackArray.lastObject;
}

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

#pragma mark - 懒加载

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

-(NSInteger)top{
    _top = self.stackArray.count;
    return _top;
}

#pragma mark - 不存在该对象的时候，自动清空
- (void)dealloc{
    if (_stackArray) {
        [_stackArray removeAllObjects];
    }
}
@end

** 实现: **

#import "NSCustomStack.h"
#import <Foundation/Foundation.h>


/**
 判断 popArray 是否 为 入栈数组 的 一种 出栈 顺序

 @param pushArray 入栈 数组
 @param popArray 出栈 数组
 @return 返回 是否 是一直 出栈 顺序
 */
BOOL isCorrectPopOrder (int *pushArray, int *popArray, int arrayLength) {
    if(pushArray == NULL || popArray == NULL) {
        return NO;
    }
    
    if (arrayLength == 0) {
        return NO;
    }
    
    if (sizeof(pushArray) != sizeof(popArray)) {
        return NO;
    }
    
    // 辅助栈
    NSCustomStack *customStack = [[NSCustomStack alloc] init];
    int popIndex = 0;
    int pushIndex = 0;
    
    while (popIndex < arrayLength) {
        while (pushIndex < arrayLength && (customStack.isEmpty || popArray[popIndex] != ((NSNumber *)customStack.topElemet).intValue)) {
            [customStack push:@(pushArray[pushIndex])];
            pushIndex++;
        }
        
        if (popArray[popIndex] == ((NSNumber *)customStack.topElemet).intValue) {
            [customStack popTopElement];
            popIndex ++;
        }else {
            return NO;
        }
        
    }
    return YES;
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int push[]  = {1, 2, 3, 4, 5};
        int pop1[]  = {4, 5, 3, 2, 1};
        int pop2[]  = {3, 5, 4, 2, 1};
        int pop3[]  = {4, 3, 5, 1, 2};
        int pop4[]  = {3, 5, 4, 1, 2};
        
        NSLog(@"%d", isCorrectPopOrder(push, pop1, 5));
        NSLog(@"%d", isCorrectPopOrder(push, pop2, 5));
        NSLog(@"%d", isCorrectPopOrder(push, pop3, 5));
        NSLog(@"%d", isCorrectPopOrder(push, pop4, 5));
    }
    return 0;
}