第三讲 栈和队列

栈(Stack)是一种先进后出的数据结构，队列(Queue)是一种先进先出的数据结构。
如下图所示：

栈和队列.png

接下来我们用数组的方式实现栈和队列的操作

栈

XSYStack.h

@interface XSYStack : NSObject
// 栈中元素个数
@property (nonatomic, assign, readonly) NSInteger length;
- (instancetype)xsy_initWithLength:(NSInteger)length;
+ (instancetype)xsy_stackWithLength:(NSInteger)length;
+ (instancetype)stack;
// 入栈
- (void)push:(id)obj;
// 出栈
- (void)pop;
// 是否为空
- (BOOL)isEmpty;
// 是否满了
- (BOOL)isFull;
@end

XSYStack.m

@interface XSYStack ()
@property (nonatomic, strong) NSMutableArray * stack;
@property (nonatomic, assign) NSInteger top;
@property (nonatomic, assign) NSInteger stackLength;
@end

@implementation XSYStack
+ (instancetype)stack{
    return [self xsy_stackWithLength:30];
}

+ (instancetype)xsy_stackWithLength:(NSInteger)length{
    return [[XSYStack alloc] xsy_initWithLength:length];
}

- (instancetype)xsy_initWithLength:(NSInteger)length{
    if (self == [super init]) {
        self.top = -1;
        self.stackLength = length;
    }
    return self;
}

- (void)push:(id)obj{
    // 判断是否溢出
    if(self.stackLength == self.stack.count) {
        NSLog(@"This stack is full！");
        return;
    }
    if (obj) {
        [self.stack addObject:obj];
    }
    self.top++;
    NSLog(@"stack push ---> %@",obj);
}

- (void)pop{
    if (self.top == -1) return;
    NSLog(@"stack pop ---> %@",self.stack[self.top]);
    [self.stack removeObjectAtIndex:self.top];
    self.top--;
    
}

- (BOOL)isEmpty{
    return self.stack.count > 0?NO:YES;
}

- (BOOL)isFull{
    return self.stack.count == self.stackLength?YES:NO;
}

- (NSInteger)length{
    return self.stack.count;
}

- (NSMutableArray *)stack{
    if(!_stack){
        _stack = [NSMutableArray array];
    }
    return _stack;
}

测试：

   XSYStack * stack = [XSYStack xsy_stackWithLength:20];
    [stack push:@"1"];
    [stack push:@"2"];
    [stack push:@"3"];
    NSInteger stackL = stack.length;
    for (int i = 0; i < stackL; i ++) {
        [stack pop];
    }

打印结果：

stack push ---> 1
stack push ---> 2
stack push ---> 3
stack pop ---> 3
stack pop ---> 2
stack pop ---> 1

队列

XSYQueue.h

@interface XSYQueue : NSObject
// 队列中元素个数
@property (nonatomic, assign, readonly) NSInteger length;
+ (instancetype)xsy_queue;
- (void)insert:(id)obj;
- (void)pop;
// 是否为空
- (BOOL)isEmpty;
@end

XSYQueue.m

@interface XSYQueue ()
@property (nonatomic, strong) NSMutableArray * queue;
// 对头
@property (nonatomic, assign) NSInteger front;
// 对尾
@property (nonatomic, assign) NSInteger end;
@end

@implementation XSYQueue
+ (instancetype)xsy_queue{
    return [[self alloc] init];
}

- (instancetype)init{
    if (self == [super init]) {
        self.front = 0;
        self.end = -1;
    }
    return self;
}

- (NSMutableArray *)queue{
    if (!_queue) {
        _queue = [NSMutableArray array];
    }
    return _queue;
}

- (void)insert:(id)obj{
    if (obj) {
        [self.queue addObject:obj];
        self.end++;
        NSLog(@"queue insert ---> %@",obj);
    }
}

- (void)pop{
    NSLog(@"queue pop ---> %@",self.queue[self.front]);
    [self.queue removeObjectAtIndex:self.front];
    self.end--;
    if(self.end == 0) self.end = -1;
}

- (BOOL)isEmpty{
    return self.queue.count > 0?NO:YES;
}

- (NSInteger)length{
    return self.queue.count;
}
@end

测试：

 XSYQueue * queue = [XSYQueue xsy_queue];
    [queue insert:@"a"];
    [queue insert:@"b"];
    [queue insert:@"c"];
    NSInteger queueL = queue.length;
    for (int i = 0; i < queueL; i ++) {
        [queue pop];
    }

打印结果：

queue insert ---> a
queue insert ---> b
queue insert ---> c
queue pop ---> a
queue pop ---> b
queue pop ---> c