算法-鏈表實現棧

鏈表是一種遞歸的數據結構，它或者為空(null)，或者只想一個節點(node)的引用，改節點包含了一個對象和執行另外一條鏈表的引用，節點 可能是包含任意數據數據的抽象尸體，包含的只想節點的應用顯示了它在鏈表之中的作用。相比數組來說有更多的靈活性， 本文就簡單的用鏈表實現一下棧，棧的最大的特點就是后進先出，隊列是先進先出，兩者不太一樣，本文將簡單的用OC實現棧。

Node定義:

@interface Node : NSObject

@property  (strong,nonatomic)  NSString  *value;

@property  (strong,nonatomic)  Node  *next;

@end

@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);

效果如下: