链表是一种递归的数据结构，它或者为空(null)，或者只想一个节点(node)的引用，改节点包含了一个对象和执行另外一条链表的引用，节点可能是包含任意数据数据的抽象尸体，包含的只想节点的应用显示了它在链表之中的作用。相比数组来说有更多的灵活性， 本文就简单的用链表实现一下栈，栈的最大的特点就是后进先出，队列是先进先出，两者不太一样，本文将简单的用OC实现栈。
Node定义:
|
1
2
3
4
5
6
7
|
@interface
Node :
NSObject
@property
(strong,
nonatomic
)
NSString
*value;
@property
(strong,
nonatomic
) Node *next;
@end
|
Stack头文件定义:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
@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的实现代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
@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]) {
self
.first=
self
.first.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
|
测试代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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);
|
效果如下:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4558408.html，如需转载请自行联系原作者
