| 注册
请输入搜索内容

热门搜索

Java Linux MySQL PHP JavaScript Hibernate jQuery Nginx
jopen
9年前发布

算法-链表实现栈

原文  http://www.cnblogs.com/xiaofeixiang/p/4558408.html


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

效果如下: