重温数据结构之栈与队列

发表于 | 分类于

0x01 栈

  栈是允许在同一端进行插入和删除操作的特殊的数据结构。被允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)。栈底固定，而栈顶浮动。栈中元素个数为零时称为空栈，插入称为进栈(Push)，删除则称为退栈(Pop)。
  栈的一个典型特征就是先进后出。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#define ERROR   -1000
#define SUCCESS 1000

#define STATUS int

// 节点结构
typedef struct _node {
    int val;
    struct _node *next;
}Node;

typedef struct _stack {
    int length;
    struct _node *top;
}StackList;

StackList* Stack_Create() {
    StackList *list = (StackList *)malloc(sizeof(StackList));
    if(list != NULL) {
        list->length = 0;
    }
    return list;
}

void Stack_Destroy(StackList *list) {
    free(list);
}

void Stack_Clear(StackList *list) {
    list->length = 0;
    list->top = NULL;
}

int Stack_Length(StackList *list) {
    return list->length;
}

STATUS Stack_Push(StackList *list, Node *node) {
    bool status = list != NULL && node != NULL;
    if(!status) return ERROR;
    
    Node *currentNode = list->top;
    node->next = currentNode;
    list->top = node;
    list->length++;
    
    return SUCCESS;
}

Node* Stack_Pop(StackList *list) {
    if(list == NULL) return NULL;
    
    Node *currentNode = list->top;
    list->top = currentNode->next;
    list->length--;
    
    return currentNode;
}

@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
   
    StackList *list = Stack_Create();
    
    struct _node n1;
    struct _node n2;
    struct _node n3;
    struct _node n4;
    struct _node n5;
    
    n1.val = 23;
    n2.val = 48;
    n3.val = 76;
    n4.val = 82;
    n5.val = 31;
    
    Stack_Push(list, (Node *)&n1);
    Stack_Push(list, (Node *)&n2);
    Stack_Push(list, (Node *)&n3);
    Stack_Push(list, (Node *)&n4);
    Stack_Push(list, (Node *)&n5);
    
    int total = list->length;
    for (int i = 0; i < total; i++) {
        Node *node = Stack_Pop(list);
        NSLog(@"弹出值：%d", node->val);
    }
    
    Stack_Destroy(list);
}

@end

// 运行结果：
2018-04-24 14:54:22.451612+0800 testData[70524:143447403] 弹出值：31
2018-04-24 14:54:22.451817+0800 testData[70524:143447403] 弹出值：82
2018-04-24 14:54:22.451924+0800 testData[70524:143447403] 弹出值：76
2018-04-24 14:54:22.452086+0800 testData[70524:143447403] 弹出值：48
2018-04-24 14:54:22.452233+0800 testData[70524:143447403] 弹出值：23

  我们通过一个栈的实际应用继续加深理解，现在我们需要实现编译器中的符号成对检测。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
bool isLeft(char c)
{
    bool ret = false;
    switch(c) {
        case '<':
        case '(':
        case '[':
        case '{':
        case '\'':
        case '\"':
            ret = true;
            break;
            
        default:
            ret = false;
            break;
    }
    return ret;
}

bool isRight(char c)
{
    bool ret = false;
    switch(c) {
        case '>':
        case ')':
        case ']':
        case '}':
        case '\'':
        case '\"':
            ret = true;
            break;
        default:
            ret = false;
            break;
    }
    return ret;
}

bool match(char left, char right) {
    bool ret = false;
    
    switch (left) {
        case '<':
            ret = (right == '>');
            break;
        case '(':
            ret = (right == ')');
            break;
        case '[':
            ret = (right == ']');
            break;
        case '{':
            ret = (right == '}');
            break;
        case '\'':
            ret = (right == '\'');
            break;
        case '\"':
            ret = (right == '\"');
            break;
            
        default:
            break;
    }
    
    return ret;
}

bool scanner(const char *code) {
    bool ret = false;
    int i = 0;
    
    StackList *list = Stack_Create();
    while (code[i] != '\0') {
        if (isLeft(code[i])) {
            Node *n = (Node *)malloc(sizeof(Node));
            n->val = code[i];
            Stack_Push(list, n);
        }
        
        if (isRight(code[i])) {
            Node *n = Stack_Pop(list);
            char c = n->val;
            if(n == NULL || !match(c, code[i])) {
                NSLog(@"%c没有匹配的符号", c);
            }
            free(n);
        }
        
        i++;
    }
    
    if (Stack_Empty(list) && code[i] == '\0') {
        NSLog(@"匹配完成");
    }else{
        NSLog(@"代码不合法");
    }
    
    Stack_Destroy(list);
    
    return ret;
}

@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
   
    const char* code1 = "#import<ViewController.h> ";

    const char* code2 = "#import<ViewController.h"; // 把>去掉

    scanner(code1); // 代码运行： 匹配完成
    scanner(code2); // 代码运行： 代码不合法
}

@end

0x01 队列

  队列是一种只允许前端(front)进行删除操作，而在后端(rear)进行插入操作的数据结构。最先插入的元素将是最先被删除的元素，反之最后插入的元素将是最后被删除的元素。因此队列的特性是先进先出。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#define ERROR   -1000
#define SUCCESS 1000

#define STATUS int

// 节点结构
typedef struct _node {
    void *val;
    struct _node *next;
}Node;

typedef struct _queue {
    int length;
    struct _node *front;
    struct _node *rear;
}QueueList;

QueueList* Queue_Create() {
    QueueList *list = (QueueList *)malloc(sizeof(QueueList));
    if(list != NULL) {
        list->length = 0;
        list->front = NULL;
        list->rear = NULL;
    }
    return list;
}

STATUS Queue_Append(QueueList *list, void *val) {
    bool ret = list != NULL && val != NULL;
    if(!ret) return ERROR;
    
    Node *node = (Node *)malloc(sizeof(Node));
    if(!node) return ERROR;
    
    node->val = val;
    
    if(list->length == 0) {
        list->front = node;
        list->rear = node;
    }else{
        list->rear->next = node;
        list->rear = node;
    }
    list->length++;

    return SUCCESS;
}

void* Queue_Retrieve(QueueList *list) {
    if(list == NULL || list->length == 0) return NULL;
    
    void *ret = NULL;
    
    Node *node = list->front;
    ret = node->val;
    list->front = node->next;
    list->length--;
    
    if(list->length == 0) {
        list->front = NULL;
        list->rear = NULL;
    }
    
    return ret;
}

bool Queue_Empty(QueueList *list) {
    return list->length == 0;
}

void Queue_Clear(QueueList *list) {
    while(!Queue_Empty(list)) {
        Queue_Retrieve(list);
    }
}

void Queue_Destroy(QueueList *list) {
    Queue_Clear(list);
    free(list);
}


@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    QueueList *list = Queue_Create();
    
    Queue_Append(list, (void *)12);
    Queue_Append(list, (void *)29);
    Queue_Append(list, (void *)82);
    Queue_Append(list, (void *)35);
    Queue_Append(list, (void *)73);
    
    int total = list->length;
    for (int i = 0; i < total; i++) {
        int n = (int)Queue_Retrieve(list);
        NSLog(@"出队列：%d", n);
    }
    
    Queue_Destroy(list);
}

@end