栈

栈的概念及结构

栈：栈是一种特殊的线性表，只允许在特定的一段插入和删除元素，进行数据插入和删除的一段称之为栈顶，另一端则称为栈底，栈中的数据元素遵循后进先出，即LIFO（Last in First out）的原则。

压栈：我们把栈的插入操作称之为进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈，出数据也是在栈顶。

所以，无论是压栈还是入栈，无论是入数据还是出数据都是在栈顶进行操作。

栈的这一特点（后进先出）不同于我们之前学过的顺序表，栈只能在一段进行数据的插入和删除操作。而我们可以在顺序表的头或者尾部、甚至是在任意位置进行数据的插入删除操作。

栈的实现

栈的实现可以用数组或者链表来实现，两者相比数组的结构更优一些，因为数组在尾上插入数据的时候代价会比较小。

如果非要说数组栈有什么缺点的话，那就是扩容了，但是即使是扩容的话也是插入好多个数据才扩容一次，扩容的代价也不是很大。

如果用链表实现的话，插入数据的操作问题不是很大；然后再来看删除的操作。如果我们要删除数据的话，即使使用一个尾指针来指向尾的话，我们也是需要遍历这个链表来找到尾指针的前一个节点的，所以删除数据的话不是很容易。当然我们可以这样，请看下图：

所以，栈的话用数据或者链表实现的话（都是O（1）的插入删除），都是可以的。

如果非要选一个的话，数组是一个不错的选择，尽管以数组的方式相比较链表而言没有太大的优势，但是数组的缓存率更高，命中率更高。

关于数组栈的实现，请点击链接：数组栈的实现。

队列

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊的线性表，队列的一大特点就是先进先出，即FIFO（First in First out）。

入队列：进行插入数据的一端称为队尾。

出队列：进行删除数据的一段称为队头。

那么我们应该如何理解队列呢？举个例子，就比如说一个隧道，我们只能在隧道的一端进入这个隧道（这一端就相当于队尾），在另外一端出这个隧道（这一端就相当于队头），当然，先进入这个隧道的也会先离开这个隧道（这就是队列的一大特点先进先出）。

队列的实现

我们知道，队列是一种链式结构，那么队列是如何定义的呢？请看我们能不能这样定义队列：

我们当然可以这样，但是有些麻烦，那为什么麻烦呢？我们来进行逐步分析。

我们知道队列进行插入操作的话是在队尾进行插入数据的，既然是队尾进行插入的话，那么我们每次进行找尾的话就会显得非常麻烦，所以如果我们要进行找尾操作的话不如使用双向带头循环链表（这里是双向循环链表的链接：点击进入）

因为双向带头循环链表是很方便进行找尾节点的。

但我们现在这里是一个单链表，找尾是很麻烦的，所以我们最好再定义一个指针：

typedef struct Queue
{
  QNode* head;
  QNode* tail;
  //int size;
}Queue;

现在我们定义了一个头指针，也定义了一个尾指针（方便我们进行找尾）。这里我们可能稍有疑惑，既然这里可以定义一个尾指针，那为什么单链表不定义一个尾指针呢？我们首先要知道单链表如果要定义一个尾指针的话是不能很好的解决问题的，如果我们给单链表定义了一个尾指针的话，尾插的确方便许多，但是尾删的话定义的尾指针就不能发挥作用了，因为单链表尾删依然需要找到尾节点的前一个节点，既然单链表定义尾指针只能解决一部分问题，那我们还不如不定义尾指针。

现在回到我们这节课的队列这里，这里我们如果定义一个尾指针的话是可以解决问题的，这是由队列的一个特点决定的：我们只能在队列的队尾插入数据，但是我们不可以在队列的队尾删除数据，我们只能在队列的对头进行删除数据（队尾入队头出），所以这里我们如果定义尾指针的话是可以很好的解决问题的。

由于这里既有头指针也有尾指针，等会还要创建其它的节点，所以数据稍多，我们最好再定义一个结构体（多个数据的话我们最好用结构体把它封装起来）：

typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  //int size;
}Queue;

所以我们这里定义了两层结构。

这里head和tail虽然都是指针，但都是Queue结构体中的成员，所以我们如果想要改变Queue结构体中的成员的话，使用结构体指针就可以了，所以尽管结构体中的成员是一个指针，但只要这个指针是这个结构体的成员，我们想要改变这个指针，只需要使用结构体指针就好了。

好了，关于栈和队列的内容就到这里了，一起加油。再见了各位！！！