閱讀目錄
- 什么是棧
- 棧的存儲結(jié)構(gòu)
- 棧的常見操作及實(shí)現(xiàn)代碼
1.什么是棧
首先棧是一種特殊的線性表。那它的特殊性表現(xiàn)在哪里呢裆蒸？棧是限定在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，因此，棧也稱為后進(jìn)先出(LIFO)的線性表郊艘。
它有很多應(yīng)用場景，比如食堂中的一疊盤子唯咬，我們只能從頂端一個一個地取纱注。
1.棧的存儲結(jié)構(gòu)
棧.jpg
1.棧的常見操作及實(shí)現(xiàn)代碼
1，初始化
實(shí)現(xiàn)思路：用指定大小的length實(shí)例化一個SeqStack<T>胆胰，然后使top指針指向-1狞贱。
2，進(jìn)棧
實(shí)現(xiàn)思路：將top指針加1蜀涨，然后將新結(jié)點(diǎn)插入到top指針指向的位置瞎嬉。
3，出棧
實(shí)現(xiàn)思路：消滅top指向的結(jié)點(diǎn)厚柳，并使top指針減1氧枣。
4，獲取棧頂元素
實(shí)現(xiàn)思路：與出棧相似别垮，只是不改變棧的狀態(tài)而已便监。
5，判斷是否椞枷耄空
實(shí)現(xiàn)思路：如果top指針是否等于-1烧董，如果是則返為空棧。
6胧奔，判斷是否棧滿
實(shí)現(xiàn)思路：檢查top指針的值是否等于數(shù)組的長度逊移，如果是則為棧滿。
OC版代碼：
SeqStack.h:
#import <Foundation/Foundation.h>
@class Student;
#pragma mark 順序棧的封裝
@interface SeqStack : NSObject
@property (nonatomic,strong)NSMutableArray *data; //使用數(shù)組來存放結(jié)點(diǎn)
@property (nonatomic,assign)NSInteger top; //棧頂指針
@end
@interface SeqStackHelper:NSObject
//初始化
+(SeqStack*)initSeqStack:(NSInteger)length;
//進(jìn)棧
+(void)Push:(SeqStack *)stack elem:(Student *)data;
//出棧
+(Student *)Pop:(SeqStack *)stack;
//獲取棧頂?shù)脑?+(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;
}
//進(jìn)棧
+(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];
}
//獲取棧中元素個數(shù)
+(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];
//進(jìn)棧
[SeqStackHelper Push:seqStack elem:stu];
[SeqStackHelper Push:seqStack elem:stu1];
[SeqStackHelper Push:seqStack elem:stu2];
//出棧
// [SeqStackHelper Pop:seqStack];
//獲取棧頂元素
Student *s = [SeqStackHelper GetTop:seqStack];
//獲取棧中元素個數(shù)
NSLog(@"當(dāng)前棧中有%ld個元素",[SeqStackHelper GetLength:seqStack]);
}
return 0;
}
