转载

算法-链表实现栈

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

测试代码:

Stack  *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);

效果如下:

算法-链表实现栈