栈

---

阅读目录

• 什么是栈
• 栈的存储结构
• 栈的常见操作及实现代码

---

1.什么是栈

首先栈是一种特殊的线性表。那它的特殊性表现在哪里呢？栈是限定在表的一端进行插入和删除运算的线性表，因此，栈也称为后进先出(LIFO)的线性表。

它有很多应用场景，比如食堂中的一叠盘子，我们只能从顶端一个一个地取。

1.栈的存储结构

栈.jpg

1.栈的常见操作及实现代码

1，初始化
实现思路：用指定大小的length实例化一个SeqStack<T>，然后使top指针指向-1。

2，进栈
实现思路：将top指针加1，然后将新结点插入到top指针指向的位置。

3，出栈
实现思路：消灭top指向的结点，并使top指针减1。

4，获取栈顶元素
实现思路：与出栈相似，只是不改变栈的状态而已。

5，判断是否栈空
实现思路：如果top指针是否等于-1，如果是则返为空栈。

6，判断是否栈满
实现思路：检查top指针的值是否等于数组的长度，如果是则为栈满。

OC版代码：
SeqStack.h:

#import <Foundation/Foundation.h>
@class Student;
#pragma mark 顺序栈的封装
@interface SeqStack : NSObject
@property (nonatomic,strong)NSMutableArray *data; //使用数组来存放结点
@property (nonatomic,assign)NSInteger top;        //栈顶指针

@end

@interface SeqStackHelper:NSObject
//初始化
+(SeqStack*)initSeqStack:(NSInteger)length;
//进栈
+(void)Push:(SeqStack *)stack elem:(Student *)data;
//出栈
+(Student *)Pop:(SeqStack *)stack;
//获取栈顶的元素
+(Student *)GetTop:(SeqStack *)stack;
//获取栈的长度
+(NSInteger)GetLength:(SeqStack *)stack;
@end

SeqStack.m:

#import "SeqStack.h"
#import "Student.h"

@implementation SeqStack

-(instancetype)initWithLength:(NSInteger)len
{
    if (self = [super init]) {
        _data = [NSMutableArray arrayWithCapacity:len];
    }
    return self;
}
@end

@implementation SeqStackHelper
 //初始化
+(SeqStack*)initSeqStack:(NSInteger)length
{
    SeqStack *stack = [[SeqStack alloc]initWithLength:10];
    stack.top = -1;
    return stack;
}
//进栈
+(void)Push:(SeqStack *)stack elem:(Student *)data
{
    if ([self IsFull:stack]) {
        return;
    }
    stack.data[stack.top+1] = data;
    stack.top++;
}
//出栈
+(Student *)Pop:(SeqStack *)stack
{
    if (stack.top == -1) {
        return nil;
    }
    Student *data = stack.data[stack.top];
    [stack.data removeObjectAtIndex:stack.top];
    stack.top --;
    return data;
}

//获取栈顶元素
+(Student *)GetTop:(SeqStack *)stack
{
    if (!stack) {
        return nil;
    }
    return stack.data[stack.top];
}

//获取栈中元素个数
+(NSInteger)GetLength:(SeqStack *)stack
{
    return stack.top+1;
}

//判断是否栈满
+(BOOL)IsFull:(SeqStack *)stack
{
    return stack.top == stack.data.count;
}
@end

main.m:

#import <Foundation/Foundation.h>
#import "Student.h"
#import "SeqStack.h"

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Student *stu = [[Student alloc]init];
        stu.name = @"小明";
        stu.age = 22;
        Student *stu1 = [[Student alloc]init];
        stu1.name = @"小丽";
        stu1.age = 25;
        Student *stu2 = [[Student alloc]init];
        stu2.name = @"小王";
        stu2.age = 34;
        Student *stu3 = [[Student alloc]init];
        stu3.name = @"小涨";
        stu3.age = 34;
        SeqStack *seqStack ;
        //初始化栈
        seqStack = [SeqStackHelper initSeqStack:10];
        //进栈
        [SeqStackHelper Push:seqStack elem:stu];
        [SeqStackHelper Push:seqStack elem:stu1];
        [SeqStackHelper Push:seqStack elem:stu2];
        //出栈
//        [SeqStackHelper Pop:seqStack];
        //获取栈顶元素
        Student *s = [SeqStackHelper GetTop:seqStack];
        //获取栈中元素个数        
        NSLog(@"当前栈中有%ld个元素",[SeqStackHelper GetLength:seqStack]);
    }
    return 0;
}