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

上一章Objective-C开发教程请查看：Objective-C类和对象

在上一章中我们讨论了OC的类和对象的基本使用，这一章给出类和对象的一个具体使用：实现双向链表，同时实现栈和队列，这是我们开发中最常用的数据结构。

首先因为OC是有头文件的，头文件.h用来声明，然后.m是实现文件，但是要注意，如果每个类都使用两个文件，那么整个项目的文件看起来眼花缭乱。因此我们可以遵循一个约定：如果一个类是不公开给其它两个以上的类使用的，那么这个类可以直接在使用到该类的声明文件中同时声明。

接下来我们讨论双向链表的实现，下面是一个单向链表和一个双向链表的示例：

如需关于链表、栈和队列更详细的解释，可以查看：线性表、栈和队列详解。

在这里我们是使用一个双向链表同时实现栈和队列，下面是栈的示例：

下面是队列的示例：

第一步，我们先看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;
}