算法-链表实现栈
链表是一种递归的数据结构,它或者为空(null),或者只想一个节点(node)的引用,改节点包含了一个对象和执行另外一条链表的引用,节点 可能是包含任意数据数据的抽象尸体,包含的只想节点的应用显示了它在链表之中的作用。相比数组来说有更多的灵活性, 本文就简单的用链表实现一下栈,栈的最大的特点就是后进先出,队列是先进先出,两者不太一样,本文将简单的用OC实现栈。
Node定义:
@interface Node : NSObject @property (strong,nonatomic) NSString *value; @property (strong,nonatomic) Node *next; @end
Stack头文件定义:
@interface Stack : NSObject //栈顶的元素 @property (strong,nonatomic) Node *first; @property (assign,nonatomic) NSInteger count; -(BOOL)isEmpty; -(NSInteger)size; -(void)push:(NSString *)value; -(NSString *)pop; -(void)remove:(NSString *)value; @end
其中有三个主要的实现方法,入栈(push),出栈(pop),删除(remove),需要注意的是本文中的删除是单向链表的删除,如果删除最后一个,时间复杂度和链表的长度有关系,我们可以采用双向链表,有兴趣的可以研究一下。
Stack.m的实现代码:
@implementation Stack -(BOOL)isEmpty{ return self.count==0; } -(NSInteger)size{ return self.count; } -(void)push:(NSString *)value{ Node *oldFirst=self.first; self.first=[[Node alloc]init]; self.first.value=value; self.first.next=oldFirst; self.count=self.count+1; } -(NSString *)pop{ if (!self.first) { return [NSString stringWithFormat:@"-1"]; } NSString *value=self.first.value; self.first=self.first.next; self.count=self.count-1; return value; } -(void)remove:(NSString *)value{ if ([self.first.value isEqualToString:value]) { Node *node=self.first; Node *nextNode=node.next; node.value=nextNode.value; node.next=nextNode.next; self.count=self.count-1; }else{ Node *node=self.first; while (node.next) { if ([node.next.value isEqualToString:value]){ if (node.next.next) { Node *tempNode=node.next.next; node.next=tempNode; }else{ node.next=NULL; } self.count=self.count-1; break; }else{ node=node.next; } } } } @end
测试代码:
tack *stack=[[Stack alloc]init]; Node *first=[[Node alloc]init]; first.value=@"iOS技术交流群:228407086"; first.next=NULL; stack.first=first; [stack push:@"FlyElephant"]; [stack push:@"博客园"]; [stack push:@"keso"]; [stack remove:@"FlyElephant"]; NSLog(@"出栈:%@",stack.pop); NSLog(@"出栈:%@",stack.pop); NSLog(@"出栈:%@",stack.pop); NSLog(@"出栈:%@",stack.pop);
效果如下: