第三章总结

第三章

在第三章我们学习了栈和队列的有关知识，队列是先进先出，栈是后进先出，这只是运算规则，没什么好谈的。

但他们的价值应体现在实际问题中，什么时候用他们会更有利于我们的思维，就拿老师在课堂上的题举例，进制转换，取模得出来那个数要倒着输出，最普通的话可以用数组，多个变量记下标就好，但这样我们的思维只局限于一层，但如果用栈的话，栈就像一个黑箱子（当然我们也要自己实现），我们只需注意栈的规则：后进先出就可以了，就只关心入栈和出栈，代码就很有层次，对问题的思考也很有帮助，简单来说就是多了几个工具，帮你更快地解决问题。

当然存储结构我们还是要抠细节的，顺序栈和顺序队列就是数组加变量记下标就好，没啥可说的，重点就是链栈和链队列了。

先说说链栈，第一个问题自然是带不带头结点，先看看栈的操作：入栈和出栈，都是在栈顶操作，也就是链式存储结构头部，如果带头结点就是对头结点之后的结点进行操作，也就是说头结点的next等于不带头结点的链栈的头指针，并且，两种情况的边界处理是一样的，我们自然选择更简单的不带头结点的链栈。

那么链对呢，我们一个一个看：

初始化：

1 Q.front = NULL; Q.rear = NULL;//不带头(都指向null)
2 Q.front = new LNode; Q.front->next = NULL; Q.rear = Q.front;//带头（都指向头结点）

判断队空：

1 Q.front==NULL 或者：Q.rear==NULL//不带头：
2 Q.front->next==NULL 或者：Q.front==Q.rear//带头

入队（没头）：

 1 {//空队列的时候
 2     p = new LNode;
 3     cin >> p->data;
 4     p->next = NULL;
 5     Q.rear = p;
 6     Q.front = Q.rear; 
 7 }
 8 {//1个结点：
 9      p = new LNode;
10     cin >> p->data;
11     p->next = NULL;
12     Q.rear->next = p; 
13     Q.rear = p;
14 }

有头：

p = new LNode;
cin >> p->data;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;

这里可以停一下，可以看出优劣了，不带头结点初始化的时候real指向空，所以在入队第一个的时候要特别一点，因为real没有next，而有头的不同，real初始化指的是头结点，它有next，所以入队操作都是一样的，无需特判。

出队（没头）：

 1 {//只剩一个节点的时候
 2     p = Q.front;
 3     Q.front = Q.front->next;
 4     e = p->data;
 5     delete p;
 6     Q.rear = NULL; 
 7 }
 8 {
 9     //还有很多个
10     p = Q.front;
11     Q.front = Q.front->next;
12     e = p->data;
13     delete p;
14 
15 }

有头：

 1 {//只剩一个
 2     p = Q.front->next;
 3     e = p->data;
 4     Q.front->next = p->next;
 5     delete p;
 6     Q.rear = Q.front; //要对real初始化
 7 }
 8              
 9 {//有很多个
10     p = Q.front->next;
11     Q.front->next = p->next; //Q.front->next被赋值为NULL
12     e = p->data;
13     delete p;
14 }

出队两个都要特判呢，因为两个都要对real初始化操作。这样总体看来，带头是更不错的，因为在入队的时候不用特判。

最后，记录一下昨天的天体赛，敲笨钟第一次找不到bug，马上换了种方法a过了，表扬一下自己，1-8太自闭了，就应该跟榜单做进阶的，只有铜就很可惜，接下来是省赛，以及各种算法，感觉不能浪了qaq，还有和大佬fcm一队就很棒。

第三章总结

第三章

推荐阅读