数据结构： 栈和队列_栈和队列的链式存储

• 栈是限定仅在表尾进行插入和删除操作的线性表。
• 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表

一、栈

• 限定仅在表尾进行插入和删除操作的线性表称之为栈

• 把允许插入和删除的一端称为栈顶(top)，另一端称为栈底( bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出( Last In First Out)的线性表，简称LIFO结构。

• 栈的插入操作，叫作进栈，也称压栈、入栈。
  

• 栈的删除操作，叫作出栈，也有的叫作弹栈。
  

1.1 顺序栈

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5
typedef int datatype;
typedef struct
{
	datatype data[MAXSIZE];
	int top;
}sq_stack_t;

//创建
sq_stack_t *sqstack_create(void)
{
    sq_stack_t *s;

    s = (sq_stack_t *)malloc(sizeof(sq_stack_t));
    if (s == NULL)
    	return NULL;

    s->top = -1;    
    return s;
}

//销毁
void sqstack_destroy(sq_stack_t *sq_stack)
{
    free(sq_stack);
}

//判断是否为空
int sqstack_is_empty(sq_stack_t *sq_stack)
{
    return (sq_stack->top == -1);
}

//入栈
int sqstack_push(sq_stack_t *sq_stack, datatype data)
{
    if (sq_stack->top == MAXSIZE-1)
        return -1;
    
    sq_stack->top++;
    sq_stack->data[sq_stack->top] = data;

    return 0;
}

//出栈
int sqstack_pop(sq_stack_t *sq_stack, datatype *data)
{
    if (sqstack_is_empty(sq_stack))
        return -1;
    
    *data = sq_stack->data[sq_stack->top];
    sq_stack->top--;

    return 0;
}


//遍历打印数据
void sqstack_traversal(sq_stack_t *sq_stack)
{
    int i;

    if (sqstack_is_empty(sq_stack))
        return;
    for (i = 0; i <= sq_stack->top; i++)
        printf("%d ", sq_stack->data[i]);
    printf("\n");
}

int main(void)
{
    sq_stack_t *sq_stack = NULL;
    datatype data;
    int i, ret;

    sq_stack = sqstack_create();
    if (sq_stack == NULL) {
        printf("sqstack create failed \n");
        exit(1);
    }

    for (i = 0; i<MAXSIZE; i++) {
        int ret = sqstack_push(sq_stack, i);
        if (ret != 0) {
            printf("sqstack push failed %d\n", ret);
            break;
        }
    }

    sqstack_traversal(sq_stack);

    ret = sqstack_pop(sq_stack, &data);
    if (ret != 0) {
        printf("sqstack_pop failed %d \n", ret);
    }

    sqstack_traversal(sq_stack);

    sqstack_destroy(sq_stack);
}
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

1.2 链栈

• 栈的链式存储结构，简称为链栈

• 链栈本质就是一个链表的首部插入、删除或尾部插入、删除的实现；首部操作用单链表比较好；尾部操作用双环链表更方便实现

• 下面例程用的是单链表首部插入、删除
  

• 进栈操作
  

• 出栈操作
  

• 代码实现

#include <stdio.h>
#include <stdlib.h>

typedef int datatype;

typedef struct _lsnode
{
    datatype data;
    struct _lsnode *next;
}linkstack_t;


linkstack_t *ls_create(void)
{
    linkstack_t *ls = NULL;

    ls = (linkstack_t *)malloc(sizeof(linkstack_t));
    if (ls == NULL)
        return NULL;

    ls->next = NULL;

    return ls;
}

void ls_destroy(linkstack_t *ls)
{
    linkstack_t *p = NULL, *q = NULL;

    for (p=ls->next; p!=NULL; p=p->next) {
        q = p;
        free(q);
    }
    
    free(ls);
}

int ls_push(linkstack_t *ls, datatype data)
{
    linkstack_t *new = NULL;

    new = (linkstack_t *)malloc(sizeof(linkstack_t));
    if (new == NULL)
        return -1;
    
    new->data = data;

    new->next = ls->next;
    ls->next = new;

    return 0;
}


int ls_pop(linkstack_t *ls, datatype *data)
{
    linkstack_t *new = ls->next;

    if (new == NULL)
        return -1;

    *data = new->data;

    ls->next = ls->next->next;

    free(new);

    return 0;
}

void ls_traversal(linkstack_t *ls)
{
    linkstack_t *ptr=ls->next;

    for (ptr = ls->next; ptr != NULL; ptr=ptr->next) {
        printf("%d ", ptr->data);
    }
    printf("\n");
}



int main(void)
{
    linkstack_t *ls=NULL;
    int i, ret;
    datatype data;

    ls = ls_create();
    if (ls == NULL) {
        printf("ls_create failed \n");
        exit(1);
    }

    for (i = 1; i < 16; i++) {
        ret = ls_push(ls, i);
        if (ret != 0) {
            printf("ls_push failed %d\n", ret);
            break;
        }
    }
    ls_traversal(ls);

    ret = ls_pop(ls, &data);
    if (ret != 0) {
        printf("ls_pop failed %d\n", ret);
    }
    printf("data:%d \n",data);
    ls_traversal(ls);

    ret = ls_pop(ls, &data);
    if (ret != 0) {
        printf("ls_pop failed %d\n", ret);
    }
    printf("data:%d \n",data);
    ls_traversal(ls);

    ret = ls_pop(ls, &data);
    if (ret != 0) {
        printf("ls_pop failed %d\n", ret);
    }
    printf("data:%d \n",data);
    ls_traversal(ls);

    ls_destroy(ls);
    ls_traversal(ls);
    
    exit(0);
}

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
123
124
125
126
127
128
129
130

1.3 小结

• 顺序栈和链栈 push和pop的时间复杂度均为O(1)；
• 如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈。
• 栈的应用场景：函数调用，递归…

二、队列

• 只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
• 队列是一种先进先出( First In First Out)的线性表，简称FIFO。
• 允许插入的一端称为队尾，允许删除的一端称为队头。
  
• 队列单向顺序存储的不足：
  ① 每次出队列的时间复杂度都为O(n)
  
  ② 为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦,所以引入两个指针， front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当 front等于rear时，此队列不是还剩一个元素，而是空队列。
  
  当队列总个数固定为5时，队列不断入队和出队，容易产生数组越界，如下图，也叫假溢出
  
• 根据上面两点不足，引入循环队列，

2.1 顺序队列（循环）

头尾相接的顺序存储结构称为循环队列。

• 上面说，frontrear时，为空队列；而现在队列满时，frontrear，如何断定队列是空还是满？
• 方法1：设置一个标志变量flag，当 frontrear,且flag=0时为队列空，当fontrear，且flag=1时为队列满。
• 方法2：当队列空时，条件就是font=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。如下图所示，就不会出现如上右图的情况。
  
• 从上图可以，rear可能大于front，也可能小于front，所以尽管它们只相关一个位置时就是满的情况，也可能是相差整整一圈，所以若队列的最尺寸为QueueSize，那么队满的条件是(rear+1)%QueueSize == front。
• 通用的计算队列长度公式为：(rear-front+QueueSize)%QueueSize

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5
typedef int datatype;
typedef struct
{
	datatype data[MAXSIZE];
	int front; //队列头
    int rear;  //队列尾
}sq_queue_t;

//创建
sq_queue_t *squeue_create(void)
{
    sq_queue_t *queue;

    queue = (sq_queue_t *)malloc(sizeof(sq_queue_t));
    if (queue == NULL)
        return NULL;

    queue->front = queue->rear = 0; //都指向下标为0的空间

    return queue;
}

//销毁
sq_queue_t squeue_destroy(sq_queue_t *queue)
{
    free(queue);
}

//判断是否满
static int squeue_is_fill(sq_queue_t *queue)
{
    return ((queue->rear+1)%MAXSIZE == queue->front); 
}

//判断是否为空
static int squeue_is_empty(sq_queue_t *queue)
{
    return (queue->front == queue->rear);
}

//入队
int squeue_en(sq_queue_t *queue, datatype data)
{
    if (squeue_is_fill(queue))
        return -1;
    
    queue->rear = (queue->rear+1)%MAXSIZE;
    queue->data[queue->rear] = data;
    
    return 0;
}

//出队
int squeue_de(sq_queue_t *queue, datatype *data)
{   
    if (squeue_is_empty(queue))
        return -1;
    
    *data = queue->data[queue->front];
    queue->front = (queue->front+1)%MAXSIZE;

    return 0;
}

//清理队列的数据
void squeue_clear_data(sq_queue_t *queue)
{
    queue->front = queue->rear;
}

//得到队列有效元素个数
static int squeue_get_elemlen(sq_queue_t *queue)
{
    return (queue->rear-queue->front+MAXSIZE)%MAXSIZE;
}

//遍历
void squeue_traversal(sq_queue_t *queue)
{
    int i;
    
    if (squeue_is_empty(queue))
        return;
    
    i = queue->front;

    while (i != queue->rear) {
        printf("%d ", queue->data[i]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
}


int main(void)
{
    sq_queue_t *queue = NULL;
    int i, ret;
    datatype data;

    queue = squeue_create();
    if (queue == NULL) {
        printf("squeue_create failed \n");
        exit(1);
    }

    for (i = 1; i < MAXSIZE; i++) {
        ret = squeue_en(queue, i);
        if (ret != 0) {
            printf("squeue_en failed %d\n", ret);
            break;
        }
    }

    squeue_traversal(queue);

    ret = squeue_de(queue, &data);
    if (ret != 0) {
        printf("squeue_de failed %d\n", ret);
    }
    printf("data:%d, queue_len:%d\n", data, squeue_get_elemlen(queue));
    squeue_traversal(queue);

    ret = squeue_de(queue, &data);
    if (ret != 0) {
        printf("squeue_de failed %d\n", ret);
    }
    printf("data:%d, queue_len:%d\n", data, squeue_get_elemlen(queue));
    squeue_traversal(queue);

    squeue_clear_data(queue);
    printf("queue_len:%d\n", squeue_get_elemlen(queue));
    squeue_destroy(queue);
    exit(0);
}
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

小结：从这一段讲解，大家应该发现，单是顺序存储，若不是循环队列,，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。

2.2 链队列

• 队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。
• 为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点
  
• 空队列时，rear和front都指向头结点
  
• 链队列结构

typedef int QElemType;  
typedef struct QNode //结点结构
{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct  //队列的链表结构
{
	QueuePtr front, rear; //队头、队尾指针
}LinkQueue;
1
2
3
4
5
6
7
8
9
10
11

• 入队操作
  

int en_queue(LinkQueue *Q, QElemType e)
{
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if (!s)
		return -1;
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;  //把拥有元素e新结点s赋值给原队尾结点的后继，见上图①
	Q->rear = s; //把当前的s设置为队尾结点，rear指向s，见上图中②

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 出队操作
  

int de_queue(LinkQueue *Q, QElemType *e)
{
	QueuePtr p;
	if (Q->front == Q->rear)
		return -1;
	p = Q->front->next;  //将欲删除的队头结点暂存给p，见上图中①
	*e = p->data;  //将欲删除的队头结点的值赋值给e
	Q->front->next = p->next;  //将原队头结点后继p->next 赋值给头结点后继，见上图中②

	if (Q->rear == p)  //若队头是队尾，则删除后将rear指向头结点，见上图中③
		Q->rear = Q->front;
	free(p);

	return 0;	
}

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

2.3 小结

• 对于循环队列与链队列的比较，可以从两方面来考虑：

1. 从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。
2. 对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活

• 总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。