Objective-C实现双向链表、栈和队列 – Objective-C开发教程 _objective-c栈和队列

上一章Objective-C开发教程请查看：Objective-C类和对象?
在上一章中我们讨论了OC的类和对象的基本使用，这一章给出类和对象的一个具体使用：实现双向链表，同时实现栈和队列，这是我们开发中最常用的数据结构。
首先因为OC是有头文件的，头文件.h用来声明，然后.m是实现文件，但是要注意，如果每个类都使用两个文件，那么整个项目的文件看起来眼花缭乱。因此我们可以遵循一个约定：如果一个类是不公开给其它两个以上的类使用的，那么这个类可以直接在使用到该类的声明文件中同时声明。
接下来我们讨论双向链表的实现，下面是一个单向链表和一个双向链表的示例：

文章图片
【Objective-C实现双向链表、栈和队列 – Objective-C开发教程】如需关于链表、栈和队列更详细的解释，可以查看：线性表、栈和队列详解。
在这里我们是使用一个双向链表同时实现栈和队列，下面是栈的示例：

文章图片
下面是队列的示例：

文章图片
第一步，我们先看List.h的头文件声明：

#import < Foundation/Foundation.h>@interface LNode : NSObject@property(nonatomic, copy)NSObject *obj; // 数据 @property(nonatomic)LNode *prev; // 前一个结点指针 @property(nonatomic)LNode *next; // 下一个结点指针-(instancetype)initWith: (NSObject*)obj prev: (LNode*)prev next: (LNode*)next; @end@interface List : NSObject@property(nonatomic)int size; // 结点数量 @property(nonatomic)LNode *head; // 头指针 @property(nonatomic)LNode *tail; // 尾指针-(BOOL)isEmpty; // 判断链表是否为空 -(void)pushFront: (NSObject*)obj; // 在表头插入数据 -(void)pushBack: (NSObject*)obj; // 在表尾插入数据 -(NSObject*)popFront; // 从表头删除数据 -(NSObject*)popBack; // 从表尾删除数据 -(void)traverse; // 遍历链表@end

以上的代码中，LNode类用于封装结点，obj是结点数据，prev是前驱指针，next是下一个结点的指针。List是实际的双向链表，size是链表结点数，head是头指针，tail是尾指针，这是一个双向循环链表。声明的方法是基本的操作方法。
接着是实现代码，如下：

#import "List.h"@implementation LNode-(instancetype)initWith: (NSObject*)obj prev: (LNode*)prev next: (LNode*)next{ if(self = [super init]){ _obj = obj; _next = next; } return self; }@end@implementation List-(instancetype)init{ if(self = [super init]){ _size = 0; _head = _tail = nil; } return self; }-(BOOL)isEmpty{ return _size == 0; }-(void)pushFront: (NSObject*)obj{ LNode *node = [[LNode alloc]initWith:obj prev: nil next:nil]; if (_size == 0) { node.prev = node; node.next = node; _head = _tail = node; _size++; } else{ LNode *head = _head; head.prev = node; node.prev = _tail; node.next = head; _tail.next = node; _head = node; _size++; } }-(void)pushBack: (NSObject*)obj{ LNode *node = [[LNode alloc]initWith:obj prev: nil next:nil]; if (_size == 0) { node.prev = node; node.next = node; _head = _tail = node; _size++; } else{ LNode *tail = _tail; tail.next = node; node.prev = _tail; node.next = _head; _head.prev = node; _tail = node; _size++; } }-(NSObject*)popFront{ if(_size == 0) return nil; LNode *head = _head; NSObject *obj = head.obj; head.prev.next = head.next; head.next.prev = head.prev; _size--; _head = head.next; head = nil; return obj; }-(NSObject*)popBack{ if(_size == 0) return nil; LNode *tail = _tail; NSObject *obj = tail.obj; tail.prev.next = _head; _head.prev = tail.prev; _size--; _tail = tail.prev; tail = nil; return obj; }-(void)traverse{ if(_size == 0) return; LNode *node = _head; do { NSLog(@"%@", node.obj); node = node.next; } while (node != _head); }@end

最后是链表的使用，包括基本的动态数组式的使用、栈的使用和队列的使用，下面是使用代码实例：

void list(void){ // list List *list = [[List alloc]init]; [list pushBack:@"iOS"]; [list pushBack:@"macOS"]; [list pushBack:@"Linux"]; [list pushBack:@"UNIX"]; [list pushBack:@"Windows"]; [list pushBack:@"Android"]; [list traverse]; NSLog(@""); // stack List *stack = [[List alloc]init]; [stack pushFront:@"Objective-C"]; [stack pushFront:@"C++"]; [stack pushFront:@"C"]; [stack pushFront:@"Java"]; [stack pushFront:@"Python"]; while (![stack isEmpty]) { NSLog(@"%@", [stack popFront]); } NSLog(@""); // queue List *queue = [[List alloc]init]; [queue pushBack:@"Objective-C"]; [queue pushBack:@"C++"]; [queue pushBack:@"C"]; [queue pushBack:@"Java"]; [queue pushBack:@"Python"]; while (![queue isEmpty]) { NSLog(@"%@", [queue popFront]); } }int main(int argc, const char * argv[]) { list(); return 0; }