IT虾米网

算法-链表实现栈详解

xmjava 2018年06月24日 手机开发 374 0


链表是一种递归的数据结构,它或者为空(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);

效果如下:

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

iOS图片处理,截图,缩放,存储详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。