栈是一种先进后出的数据结构。怎么理解先进后出呢，我们将栈理解为堆积木。我们放积木，都是从最底下一层一层开始堆，而拿的时候从最上层开始拿，这样越早堆的积木拿的也就越晚，这样实际上就是先进后出了。
栈的结构可以参考上图。我们看到，有一个栈顶指针TOP始终指着最上方的位置。栈顶指针是始 终指向栈的最上方元素的一个标记。假如我们的栈使用数组来实现，TOP就是一个int型的变量，它记录着数组最后一个元素(也就是栈顶元素)的下标位置。而当栈空时，TOP的值等于-1，标志着没有元素。
我们用数组实现的栈是顺序栈，实现的方法也很简单：定义一个足够长的数组用来存放元素，再定义栈顶指针TOP，并初始化TOP=-1表示栈空。我们接下来来看顺序栈的基本操作，包括：清空栈、获取栈的大小、判断栈是否空、元素进栈、元素出栈、获取栈顶元素。
（1）清空(clear)
栈的清空操作将TOP的值置为-1，表示栈中空。
void clear() {
TOP=-1;
}
（2）获取栈内元素个数(size)
TOP始终指向栈顶元素，数组下标从0开始，因此元素个数为TOP+1。
int size() {
return TOP+1;
}
（3）判断栈是否空(empty)
只有TOP=-1时为空，其他情况为否。
bool empty() {
if(TOP==-1)
return true;
else
return false;
}
（4）进栈(push)
TOP指向当前栈顶的位置，我们只需将TOP加一即可找到空位放入元素，这样新元素就成了栈 顶。
void push(int x) {
st[TOP++]=x;
}
（5）出栈(pop)
出栈的过程和入栈相反，TOP指向栈顶元素，我们只需将TOP减1并不需要对这个元素有什么操作。因为在我们的栈看来，它的size已经减1，最上面的那个元素已经被“移”出栈。
void pop() {
TOP--;
}
（6）访问栈顶元素(top)
st[TOP]即为栈顶元素。
int top() {
return st[TOP];
}
实际上，我们上面简单的实现了一个存放int型数据的定长顺序栈，只是为了让读者理解栈的一些基本原理。而要实现一个高效并且实用的栈容器，情况是比上面的过程复杂不少的。
因此在C++STL中，已经为我们准备stack栈容器，我们可以在编程中使用栈，而不用将精力花在栈的实现上。stack的用法可以参考博客c++ stl栈容器stack用法介绍_lyj2014211626的博客-CSDN博客。
7.1.2队列的应用队列是一种先进先出的数据结构。这比栈更容易理解，我们将其看成排队打饭：每个来的人都要排到队伍最后面，而最前面的人则打饭出队，先来的人一定先出队。这就是一种先进先出。
我们注意到，队列总是从队尾加入元素，从队首移除元素。一般来说，需要一个队首指针front来指向队首元素的前一个位置，使用一个队尾指针rear来指向队尾元素。和栈类似，当用数组来实现队列时front和rear为int型变量，记录着下标。
下面使用数组q[]来实现队列，front记录队列第一个元素的前一个下标，rear记录队列最后一个元素的下标，它们的初始值都置为-1。我们来看队列的基本操作，包括清空、获取队列元素个数、判空、入队、出队、取队首元素、取队尾元素。
（1）清空(clear)
根据定义，当front=rear=-1时，队列为初始化状态。因此我们把队首队尾两个指针置为-1即可。
void clear() {
front=rear=-1;
}
（2）获取队列元素(size)
我们通过具几个特例就可以发现，队内元素个数=rear-front。
int size() {
return rear-front;
}
（3）入队(push)
入队从队尾，而队尾指针rear始终指向队列最后一个元素。因此把rear+1，然后在对应位置赋值即可。
void push(int x) {
q[++rear]=x;
}
（4）出队(pop)
和出栈类似，直接将队首指针加1，这样队首元素就被“移除”出队列了。
void pop() {
front++;
}
（5）判空(empty)
显然，当front=rear=-1时（也就是初始状态），队列为空。但随着不断有元素入队出队，front和rear也在不断移动。当front=rear但不等于-1时，队列也为空。
bool empty() {
if(front==rear)
return true;
else
return false;
}
（6）取队首元素(get_front)
front表示着队首元素的前一个下标位置，因此front+1才是队首元素的位置。
int get_front() {
return q[front+1];
}
（7）取队尾元素(get_rear)
rear表示着队尾元素所在的位置。
int get_rear() {
return q[rear];
}
同样地，我们简单地实现了一个队列，是为了介绍队列的一些基本原理。在C++STL中，已经有queue队列容器供我们使用，使用方法可以参考博客C++ STL--queue 的使用方法 - 程序员修练之路 - 博客园 (cnblogs.com) 。
