阅读目录
- 什么是栈
- 栈的存储结构
- 栈的常见操作及实现代码
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;
}
