用OC实现一个栈：结合单链表创建动态栈

一、介绍

栈是一种数据存储结构，存储的数据具有先进后出的特点。栈一般分为动态栈和静态栈。

静态栈比较好理解，例如用数组实现的栈。动态栈可以用链表来实现。

方式：固定base指针，每次更改top指向入栈的节点，遍历时从top节点遍历即可。

判空：s.top == s.base && s.top == nil && s.base == nil

栈满：s.top - s.base >= s.stackSize

三、图示

初始状态：s.top = s.base = nil，栈顶和栈底指针指向空，分配栈大小为s.stackSize = 4;

入栈状态：s.base不变，s.top = node，栈底指针不变，栈顶指针指向新节点

栈满状态：s.top - s.base >= s.stackSize, 遍历链表，链表的长度等于或大于栈大小

出栈状态：s.base不变，s.top = node->next, node节点从链表断裂取出，top指针指向node下一个节点

栈空状态：s.top=nil，并将s.base=s.stop。

三、代码

node:

//  Node.h

//  运行时

//

//  Created by 夏远全 on 2019/10/16.

//

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface Node : NSObject

@property (nonatomic, assign) int data;

@property (nonatomic, strong, nullable) Node *next;

-(instancetype)initWithData:(int)data;

@end

NS_ASSUME_NONNULL_END

//  Node.m

//  运行时

//

//  Created by 夏远全 on 2019/10/16.

#import "Node.h"

@implementation Node

-(instancetype)initWithData:(int)data {

    self = [super init];

    if (self) {

        self.data = data;

        self.next = nil;

    }

    return self;

}

@end

stack:

//

//  Stack.h

//  运行时

//

//  Created by 夏远全 on 2019/10/16.

//

#import <Foundation/Foundation.h>

#import "Node.h"

NS_ASSUME_NONNULL_BEGIN

/*

特点：栈是先进后出的特点，采用链表实现一个动态栈（静态栈可以用数组实现）。固定base指针，每次更改top指向入栈的节点，遍历时从top节点遍历即可。

链表栈

判空：s.top == s.base && s.top == nil && s.base == nil

栈满：s.top - s.base >= s.stackSize

*/

@interface Stack : NSObject

/**

 构造一个栈

 @return 栈

 */

+(instancetype)constructStack;

/**

 推入一个节点

 @param node 节点

 */

-(void)pushNode:(Node *)node;

/**

 推出一个节点

 */

-(void)pop;

@end

NS_ASSUME_NONNULL_END

//

//  Stack.m

//  运行时

//

//  Created by 夏远全 on 2019/10/16.

//

#import "Stack.h"

@interface Stack ()

@property (nonatomic, strong) Node *top;       //栈顶指针

@property (nonatomic, strong) Node *base;      //栈底指针

@property (nonatomic, assign) int  stackSize;  //栈初始大小

@end

@implementation Stack

+(instancetype)constructStack

{

    Stack *stack = [[Stack alloc] init];

    stack.top = stack.base;

    stack.stackSize = ;

    return stack;

}

-(void)pushNode:(Node *)node {

    //空节点

    if (!node) {

        NSLog(@"------不能push一个空的节点-------");

        return;

    }

    //栈满

    if ([self isFull]) {

        NSLog(@"------栈已满-------，当前节点node值: %d不能被push", node.data);

        [self printStack];

        return;

    }

    //修改栈顶指针，确定栈底指针，不会再改变

    if ([self isEmpty]) {

        self.top = self.base = node;

    }

    else{

        node.next = self.top;

        self.top = node;

    }

    NSLog(@"push入栈的节点：data = %d", node.data);

}

-(void)pop {

    //栈为空

    if ([self isEmpty]) {

        NSLog(@"------栈已空-------");

        return;

    }

    //删除节点，并修改栈顶指针

    Node *popNode = self.top;

    self.top = popNode.next;

    NSLog(@"pop出栈的节点：data = %d",popNode.data);

    //节点pop完毕

    if (self.top == nil) {

        self.base = self.top;

        NSLog(@"------栈已空-------");

    }

}

-(BOOL)isEmpty {

    return (self.top == self.base && self.top == nil && self.base == nil);

}

-(BOOL)isFull {

    //遍历长度

    int size = ;

    Node *p = self.top;

    while (p != nil) {

        size ++;

        p = p.next;

    }

    return size >= self.stackSize;

}

-(void)printStack {

    NSMutableArray *nodes = [NSMutableArray array];

    Node *p = self.top;

    while (p != nil) {

        [nodes addObject:@(p.data)];

        p = p.next;

    }

    NSLog(@"当前栈的所有节点为：%@",[nodes componentsJoinedByString:@"->"]);

}

@end

四、打印

-(void)test_DataStructure_Stack {

    /// 构造栈

    Stack *stack = [Stack constructStack];

    /// 构造元素

    Node *node1 = [[Node alloc] initWithData:];

    Node *node2 = [[Node alloc] initWithData:];

    Node *node3 = [[Node alloc] initWithData:];

    Node *node4 = [[Node alloc] initWithData:];

    Node *node5 = [[Node alloc] initWithData:];

    Node *node6 = [[Node alloc] initWithData:];

    /// push时，进去的顺序为: 1、2、3、4、5

    [stack pushNode:node1];

    [stack pushNode:node2];

    [stack pushNode:node3];

    [stack pushNode:node4];

    [stack pushNode:node5];

    [stack pushNode:node6];//node6不能被push进去，栈已满

    /// pop时，出来的顺序为: 5、4、3、2、1

    [stack pop];

    [stack pop];

    [stack pop];

    [stack pop];

    [stack pop];//最后一个节点被pop出来，栈已空

}

-- ::03.214331+ 运行时[:] push入栈的节点：data =

-- ::03.214513+ 运行时[:] push入栈的节点：data =

-- ::03.214620+ 运行时[:] push入栈的节点：data =

-- ::03.214715+ 运行时[:] push入栈的节点：data =

-- ::03.214796+ 运行时[:] push入栈的节点：data =

-- ::03.214878+ 运行时[:] ------栈已满-------，当前节点node值: 6不能被push

-- ::03.215023+ 运行时[:] 当前栈的所有节点为：->->->->

-- ::03.215111+ 运行时[:] pop出栈的节点：data =

-- ::03.215208+ 运行时[:] pop出栈的节点：data =

-- ::03.215508+ 运行时[:] pop出栈的节点：data =

-- ::03.215845+ 运行时[:] pop出栈的节点：data =

-- ::03.216101+ 运行时[:] pop出栈的节点：data =

-- ::03.216429+ 运行时[:] ------栈已空-------

巴特西

用OC实现一个栈：结合单链表创建动态栈

最新文章

热门文章