读书笔记: 顺序队列和顺序栈 SqQueue and SqStack

SqQueue

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
#include <stdio.h>
#define MAX_QUEUE_SIZE 100

typedef struct{
    int key;
}element;
element queue[MAX_QUEUE_SIZE];
int top = -1;
int rear = -1;

void qadd(int *rear, element item);
element qdelete(int *front,int rear);

int main (int argc, const char * argv[])
{
    element i1={1},i2={2},i3={3},i4={4};
    qadd(&rear,i1);
    qadd(&rear,i2);
    qadd(&rear,i3);
    qadd(&rear,i4);

    element temp = qdelete(&top, rear);
    printf("%d \n",temp.key);
    return 0;
}

void qadd(int *rear, element item){
    if (*rear == MAX_QUEUE_SIZE){
//        queue_full();
//        return;
    }
    *rear = (*rear + 1) % MAX_QUEUE_SIZE;
    queue[++(*rear)] = item;
}

element qdelete(int *front,int rear){
    if(*front == rear){
//        return queue_empty();
    }
    *front = (*front + 1) % MAX_QUEUE_SIZE;
    return queue[++(*front)];
}

SqStack

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
#include <stdio.h>
#define MAX_STACK_SIZE 100
typedef struct {
    int key;
}element;
element stack[MAX_STACK_SIZE];
int top=-1;

void add(int *top,element item);
element delete(int *top);

int main (int argc, const char * argv[])
{
    element i1={1},i2={2},i3={3},i4={4};
    add(&top,i1);
    add(&top,i2);
    add(&top,i3);
    add(&top,i4);

    printf("%d \n",stack[top].key);

    element temp;
    temp = delete(&top);
    printf("%d \n",stack[top].key);
    printf("%d \n",temp.key);

    return 0;
}

void add(int *top,element item){
    if(*top >= MAX_STACK_SIZE){
//        stack_full();
//        return;
    }
    stack[++(*top)] = item;
}

element delete(int *top){
    if(*top == -1){
//        return stack_empty();
    }
    return stack[(*top)--];
}
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
#define MAX_STACK_SIZE 100
#define MAX_QUEUE_SIZE 100

typedef struct tree_node *tree_pointer;
typedef struct tree_node{
    char *data;
    tree_pointer left_child,right_child;
}tree_node;

tree_pointer create_tree_pointer(char *data){
    tree_pointer temp;
    temp = (tree_pointer) malloc (sizeof(tree_node));
    temp->data = data;
    return temp;
}

typedef struct{
    tree_pointer *base;
    tree_pointer *top;
}SqStack;

void InitSqStack(SqStack *S){
    S->base = (tree_pointer) malloc(MAX_STACK_SIZE * sizeof(tree_node));
    S->top = S->base;
}

void SqStack_push(SqStack *S, tree_pointer node){
    if(S->top - S->base >= MAX_STACK_SIZE) exit(1);
    *(S->top)++ = node;
}

tree_pointer SqStack_pop(SqStack *S){
    if(S->top == S->base) exit(1);
    return *(--S->top);
}


int main(){
    tree_pointer a1,a2,a3;
    a1 = create_tree_pointer("a1");
    a2 = create_tree_pointer("a2");

    SqStack S;
    InitSqStack(&S);
    SqStack_push(&S, a1);
    SqStack_push(&S, a2);

    a3= SqStack_pop(&S);

    printf("%s \n",a3->data);
    printf("%s \n",(*S.top)->data);

    return 0;
}