读书笔记: 链表队列(link Queue)和链表栈(link Stack)

1. 队列 Link Queue

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct{
    int key;
}element;
typedef struct queue *queue_pointer;
typedef struct queue{
    element item;
    queue_pointer link;
}queue;
queue_pointer front,rear;

void addq(queue_pointer *front, queue_pointer *rear, element item);
element deleteq(queue_pointer *front);

1.1 Add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void addq(queue_pointer *front,queue_pointer *rear,element item){
    queue_pointer temp = (queue_pointer) malloc(sizeof(queue));
    //    if(IS_FULL(temp)){
    //        fprintf(stderr, "full");
    //        exit(1);
    //    }
    temp->item = item;
    temp->link = NULL;
    if(*front){
        (*rear)->link = temp;
    } else {
        *front = temp;
    }
    *rear = temp;
    
}

1.2 Delete

1
2
3
4
5
6
7
8
9
10
11
12
13

element deleteq(queue_pointer *front){
    queue_pointer temp = *front;
    //    if(IS_EMPTY(temp)){
    //        fprintf(stderr, "temp");
    //        exit(1);
    //    }
    element temp_item;
    temp_item=temp->item;
    
    *front = (*front)->link;
    free(temp);
    return temp_item;
}

1.3 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int main (int argc, const char * argv[])
{
    element temp1= {1024};
    element temp2= {2048};
    addq(&front, &rear, temp1);
    addq(&front, &rear, temp2);
    
    printf("%d \n",front->item.key);
    
    deleteq(&front);
    printf("%d \n",front->item.key);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int main (int argc, const char * argv[])
{
     element *temp1 = (element *) malloc(sizeof(element));
     element *temp2 = (element *) malloc(sizeof(element));
     temp1->key = 1024;
     temp2->key = 2048;
     addq(&front, &rear, *temp1);
     addq(&front, &rear, *temp2);
     free(temp1);
     free(temp2);

    printf("%d \n",front->item.key);
    
    deleteq(&front);
    printf("%d \n",front->item.key);
    
    return 0;
}

2. 栈 Link Stack

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct {
    int key;
}element;
typedef struct stack *stack_pointer;
typedef struct stack{
    element item;
    stack_pointer link;
}stack;
stack_pointer top;

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

2.1 Add

1
2
3
4
5
6
7
8
9
10

void add(stack_pointer *top,element item){
    stack_pointer temp = (stack_pointer) malloc(sizeof(struct stack));
    if (IS_FULL(temp)){
        fprintf(stderr, "is full");
        exit(1);
    }
    temp->item = item;
    temp->link = *top;
    *top = temp;
}

2.2 Delete

1
2
3
4
5
6
7
8
9
10
11
12

element delete(stack_pointer *top){
    stack_pointer temp = *top;
    element item;
    //    if(IS_EMPTY(temp)){
    //        fprintf(stderr, "is empty");
    //        exit(1);
    //    }
    item = temp->item;
    *top = temp->link;
    free(temp);
    return item;
}

2.3 Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int main(void)
{
    top = (stack_pointer) malloc(sizeof(stack));
    element i1,i2,i3;
    i1.key = 1024;
    i2.key = 2048;
    i3.key = 4096;
    
    printf("Add three stack element,and the top is: ");
    add(&top,i1);
    add(&top,i2);
    add(&top,i3);
    printf("%d \n",top->item.key);
    
    printf("Delete top,Then");
    element temp;
    temp = delete(&top);
    
    printf("The current top: %d \n",top->item.key);
    printf("被删除的元素值: %d \n",temp.key);
    
    return 0;
}