栈与队列都是特殊的线性表，它们也是线性结构。用户可以采用顺序存储结构和链式存储结构两种方式来存储。栈和队列结构是各种系统软件和应用软件中使用最为广泛的数据结构。

栈的主要操作特点是，元素的插入和删除操作只能在栈顶进行。

队列的主要操作特点是，元素的插入操作在队尾进行，删除操作在队头进行。

栈和队列主要用来在程序中存放临时使用的数据。

栈

栈也称为堆栈，是一种仅允许在表的一端（栈顶）进行插入和删除运算的线性表，遵循后进先出的原则。

栈顶：指栈中可以进行插入和删除的那一端，即线性表的表尾。

栈顶：指栈中不可以进行插入和删除的那一端，即线性表的表尾。

进栈：向栈中插入新元素怒称为进栈，也称为入栈或压栈。此时，新进栈的元素存放在栈顶，成为新的栈顶元素。

出栈：从栈中删除元素称为出栈，也称为退栈或弹栈。即把栈顶元素删除，使其下面相邻的元素成为新的栈顶元素

栈的数据元素集合可以表示为序列，数据元素可以是任意类型的。在java中，可以是任意类型的数据。

栈的存储结构有两种：一种是顺序存储结构，另一种是链式存储结构

栈的链式存储结构

链式栈其实就是一个单链表，其中head为链表的头指针，在这里也是链式栈的栈顶指针。当栈中数据发生变化时，栈顶head所发生的变化如下。

当栈顶为空时，也就是链表为空，此时head=null。

进栈一个元素就是在链表的头部插入一个节点

出栈一个元素就是删除链表头部的节点

队列

队列是一种允许在一端进行插入，而在另一端进行删除运算的线性表，遵循先进先出的原则。

队头：队列中可以进行删除的那一端，即线性表的表头

队尾：队列中可以进行插入的那一端，即线性表的表尾。

进队：也称入队。向一个队列中插入新元素，即把新元素放到对尾，使其成为新的对尾元素。

出队：在一个队列中删除元素，即把队头元素删除掉，使其下面相邻的元素成为新的队头元素。

队列的存储结构有顺序存储结构和链式存储结构。使用顺序存储结构存储的对列称为顺序队列，而使用链式存储结构存储的对列称为链式队列。

顺序对列的存储结构

使用顺序存储结构存储数据的队列称为顺序队列。在java中，使用数组来实现顺序存储

其中，front和rear是数组的下 标，用来作为顺序队列的队头指针和对尾指针。当队列为空时，front=raer=0。进队一个元素后，队尾指针rear加1，队头指针不变；而当出队一个元素后，队头指针加1，并指向新的队头元素，队尾指针不变队尾指针所代表的位置是当前队列中可以进队的位置。当队位指针rear=n（数组的长度）时，顺序队列会发生溢出异常。注意：这个溢出可能是“假溢出”。

顺序队列的假溢出问题

假设用来存储一个顺序队列的数组的长度n=5，则当数据datal1，datal2，datal3进队后，将datal1、datal2依次出队，然后将datal4、datal5入队，此时当队尾指针rear=5。如果此时有一个数据元素data想进入队列，则会发生假溢出现象

这种溢出并不是因为队列中没有存储空间可用，而是数组的下标越界造成的。其实，此时队列中只有三个元素，应该还可以进队两个元素。

顺序队列因多次入队和出队操作而出现的现有存储空间但不能进行入队操作的溢出称为假溢出。

顺序循环队列

顺序队列的假溢出是因为队头指针front和队尾指针rear没能及时地随数组上下界值的变化而进行变化，因此，解决的办法是将顺序队列所使用的存储空间构造成一个逻辑上首位相接的循环队列，即最后一个存储单元相邻的下一个存储位置是数组的第一个存储单元。也就是说，当rear和front的值达到n-1（数组的末尾）时，就使其等于0，这样就可以避免顺序队列头部空出很多存储单元，而队尾却因数组下标越界出现假溢出的状况，

对于循环队列，在进行进队或者出队操作时，要对队列是否为空或队列是否已满进行判断，当队空或队满是，front=rear=0，因此，不能简单地通过front和rear来判断队空或队满。通常情况下，可设置一个计数器count来配合队头front、队尾rear一起来使用。每当成功进队一个元素时，count就加1，每当出队操作成功是，count就减1.这样，当count=0时队列为空；而当count>0且front=rear时，队列为满。

由于顺序队列存在假溢出问题，所以，在实际应用中通常使用顺序循环队列。

链式队列

使用链式存储结构的队列称为链式队列，在Java中，使用链表来实现链式存储。

链式队列其实就是一个单链表。其中，front为链表的头指针，在这里也是链式队列的队头指针；rear是队尾指针，指向链表的尾结点。

当队列为空时，也就是链表为空，此时head=rear=null。进队一个元素就是在链表的尾部插入一个结点，出队一个元素就是在链头删除一个结点。