数据结构与算法二: (1)桟

这是我参与8月更文挑战的第5天

关注我,以下内容持续更新

数据结构与算法(一):时间复杂度和空间复杂度

数据结构与算法(二):桟

数据结构与算法(三):队列

数据结构与算法(四):单链表

数据结构与算法(五):双向链表

数据结构与算法(六):哈希表

数据结构与算法(七):树

数据结构与算法(八):排序算法

数据结构与算法(九):经典算法面试题

桟的介绍

桟(stack)是一种受限的线性结构,它是后进先出(LIFO)的有序列表,桟只能在同一端进行插入和删除,这一端称为栈顶,另一端称为桟底。最先放入的元素在桟底,最后放入的元素在栈顶.

关于出栈(pop)和入栈(push)的说明请看图解

栈的应用场景

1. 子程序的调用:在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以 回到原来的程序中。

2. 处理递归调用:和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区

3. 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。

4. 二叉树的遍历。

5. 图形的深度优先(depth一first)搜索法。

自定义栈的增删改查

栈的常用操作

s=Stack()           创建栈
s.push(item)        将数据item放在栈的顶部
s.pop()             返回栈顶部数据，并从栈中移除该数据
s.peek()            返回栈顶部数据，但不移除
s.size()            返回栈的大小
s.isEmpty()         返回栈是否为空 
复制代码

由于栈是一种有序列表,所以可以用数组模拟栈的增删改查,实现如下

MyStack.h 文件

@interface MyStack : NSObject

//是否空

-(BOOL)isEmpty;

//插入

-(void)push:(NSObject*)e;

//删除并返回

-(Student*)pop;

//查看栈顶元素

-(Student*)peek;

//元素总数

-(int)size;

//打印桟

-(void)showStack;

@end
复制代码

MyStack.m 文件

#import "MyStack.h"

@interface MyStack()

/**用数组模拟队列,data可以是任意类型*/
@property (nonatomic,strong) NSMutableArray<Student*> * data;

/**最大值*/
@property (nonatomic,assign) int maxSize;

@end

@implementation MyStack

- (instancetype)init

{

    self = [super init];

    if (self) {

        self.data = [NSMutableArray array];

    }

    return self;

}

//是否空

-(BOOL)isEmpty{
    return self.data.count == 0;
}

//插入
-(void)push:(Student*)e{

    [self.data addObject:e];

}

//删除并返回
-(Student*)pop{

    if ([self isEmpty]) {

        printf("桟为空\n");

        return NULL;

    }

    Student*ele = [self.data lastObject];

    [self.data removeLastObject];

    return ele;
}

//查看栈顶元素
-(Student*)peek{
    if ([self isEmpty]) {
        printf("桟为空\n");
        return NULL;
    }
    return [self.data lastObject];
}

-(int)size{
    return (int)self.data.count;
}

//打印桟
-(void)showStack{
    printf("打印桟\n");
    if ([self isEmpty]) {
        printf("桟为空\n");
        return;
    }

    for (int i = (int)self.data.count - 1; i>=0; i--) {
        printf("%s-->",self.data[i].ID.UTF8String);
    }
    printf("\n");
}

@end

复制代码

桟的实际应用

1. 判断单个括号是否平衡

如下图中的左括号和右括号是否依次匹配

思路:

返回YES代表匹配,返回NO代表不匹配

 遍历字符串进行入栈和出桟操作

 1.只入栈左括号,其他符号不处理;

 2.当遇到右括号时,先判断栈顶元素是否为空,为空提前返回NO,如果不为空就把栈顶元素出桟

 3.遍历完成后,判断桟内元素是否为空,为空则匹配,不为空说明不匹配

-(BOOL)matchOneBrackets{
    NSString*brackets = @"((((()))))"; // //@"((((((())"
    Stack*stack = [Stack new];
    for (int i = 0; i<brackets.length; i++) {
        char c = [brackets characterAtIndex:i];
        if (c == '(') {
            [stack push:[NSString stringWithFormat:@"%c",c]];
        } else if(c == ')') {
            if (![stack isEmpty]) {
               [stack pop];
            }else{
                printf("不匹配\n");
                return NO;
            }
        }
    }
    return [stack isEmpty];
}
复制代码

2. 判断多种括号是否平衡

{ [ ( 和 ) ] }应依次匹配

平衡示例

不平衡示例

思路:

返回YES代表匹配,返回NO代表不匹配

 遍历字符串进行入栈和出桟操作:

 1.只入栈左括号,其他符号不处理;

 2.当遇到右括号时,先判断栈顶元素是否为空,为空提前返回NO,如果不为空继续判断桟顶元素是否为其对应的左括号,如果不对应则返回 NO,如果对应则出桟;

 3.遍历完成后,判断桟内元素是否为空,为空则匹配,不为空说明不匹配

-(BOOL)matchManyBrackets{

    NSString*brackets = @"{{{ { ( [ ] [ ] ) } ( ) }"; //@"{ { ( [ ] [ ] ) } ( ) }"

    NSDictionary*dict = @{@")":@"(",@"]":@"[",@"}":@"{"};

    Stack*stack = [Stack new];

    for (int i = 0; i<brackets.length; i++) {
        char c = [brackets characterAtIndex:i];
        if (c == '(' || c == '[' || c == '{' ) {
            [stack push:[NSString stringWithFormat:@"%c",c]];
        } else if(c == ')' || c == ']' || c == '}') {
            if (![stack isEmpty]) {
                NSString* top = [stack peek];
                if ([top isEqualToString:[dict objectForKey:[NSString stringWithFormat:@"%c",c]]]) {
                    [stack pop];
                }else{
                    printf("不匹配\n");
                    return NO;
                }
            }else{
                printf("不匹配\n");
                return NO;
            }
        }
    }
    return [stack isEmpty];
}
复制代码

3.1 将十进制数转化为二进制数

思路

十进制整数转换为二进制整数十进制整数转换为二进制整数采用”除2取余，逆序排列”法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

/**
 十进制整数转换为二进制整数十进制整数转换为二进制整数采用"除2取余，逆序排列"法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。
 */
//十进制转二进制 1000-->1111101000
-(void)switch10To2:(int)decNumber{

    Stack*stack = [Stack new];

    int remainder = 0;//余数

    while (decNumber>0) {

        remainder = decNumber % 2;

        decNumber = decNumber / 2;

        [stack push:[NSString stringWithFormat:@"%d",remainder]];

    }

    NSString*result = @"";
    while ([stack size]) {
        result = [result stringByAppendingString:[stack pop]];
    }
    printf("十进制转二进制的结果为-->%s \n",result.UTF8String);
    [stack showStack];
}
复制代码

3.2 将十进制数转化为二进制/八进制/十六进制数

思路和十进制转二进制一样,只需要在代码中替换转化的进制数即可.

比如十进制转八进制:1000–>1750

//十进制转任意进制

//思路与十进制整数转换为二进制一样,只需要在代码中替换转化的进制数即可

//比如十进制转 8 进制:1000-->1750

-(void)switch10ToOther:(int)decNumber base:(int)base{

    Stack*stack = [Stack new];
    int remainder = 0;//余数

    while (decNumber>0) {
        remainder = decNumber % base;
        decNumber = decNumber / base;
        [stack push:[NSString stringWithFormat:@"%d",remainder]];
    } 

    NSString*result = @"";
    while ([stack size]) {
        result = [result stringByAppendingString:[stack pop]];
    }
    printf("十进制转%d进制的结果为-->%s \n",base,result.UTF8String);
}
复制代码

3.3 将二进制数转化为十进制

//二进制转十进制 1111101000--->1000
-(void)switch2To10:(NSString*)decNumber{
    int result = 0;
    Stack*stack = [Stack new];
    for (int i = 0; i<decNumber.length; i++) {
        [stack push:[NSString stringWithFormat:@"%c",[decNumber characterAtIndex:i]]];
    }

    int index = 1;
    while ([stack size]) {
        int a = [[stack pop] intValue];
        result += a*index;
        index = index*2;
    }
    printf("二进制转十进制的结果为-->%d \n",result);
}
复制代码

4. 算术表达式的转换

比如中缀表达式转为前缀表达式或者后缀表达式(逆波兰式),这个地方比较复杂,下篇文章详细讲解