Java中实际上提供了java.util.Stack来实现栈结构,但官方目前已不推荐使用,而是使用java.util.Deque双端队列来实现队列与栈的各种需求.如下图所示java.util.Deque的实现子类有java.util.LinkedList和java.util.ArrayDeque.顾名思义前者是基于链表,后者基于数据实现的双端队列.



总体介绍

要讲栈和队列，首先要讲Deque接口。Deque的含义是“double ended queue”，即双端队列，它既可以当作栈使用，也可以当作队列使用。下表列出了Deque与Queue相对应的接口：



下表列出了Deque与Stack对应的接口：



上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值（false或null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了这一点讲解起来就会非常简单。

ArrayDeque

从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。



上图中我们看到，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。

addFirst()

针对首端插入实际需要考虑：1.空间是否够用，以及2.下标是否越界的问题。上图中，如果head为0之后接着调用addFirst()，虽然空余空间还够用，但head为-1，下标越界了。下列代码很好的解决了这两个问题。

  public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    //下标越界问题解决方案
    elements[head = (head - 1) & (elements.length - 1)] = e;
    //容量问题解决方案
    if (head == tail)
        doubleCapacity();
}

上述代码我们看到，空间问题是在插入之后解决的，因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。

下标越界的处理解决起来非常简单，head = (head - 1) & (elements.length - 1)就可以了，这段代码相当于取余，同时解决了head为负值的情况。因为elements.length必需是2的指数倍(构造函数初始化逻辑保证)，elements - 1就是二进制低位全1，跟head - 1相与之后就起到了取模的作用，如果head - 1为负数（其实只可能是-1），则相当于对其取相对于elements.length的补码。

下面再说说扩容函数doubleCapacity()，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。过程如下图所示：



 

图中我们看到，复制分两次进行，第一次复制head右边的元素，第二次复制head左边的元素。

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

addLast()

addLast(E e)的作用是在Deque的尾端插入元素，也就是在tail的位置插入元素，由于tail总是指向下一个可以插入的空位，因此只需要elements[tail] = e;即可。插入完成后再检查空间，如果空间已经用光，则调用doubleCapacity()进行扩容。与first比较类似就不多分析了.



其他操作也是差不多的方式,唯一麻烦的head与tail位置转换也用取余巧妙的化解了.

LinkedList

LinkedList实现了Deque接口,因此其具备双端队列的特性,由于其是链表结构,因此不像ArrayDeque要考虑越界问题,容量问题,那么对应操作就很简单了,另外当需要使用栈和队列是官方推荐的是ArrayDeque,因此这里不做多的分析.

3.1  栈
​    3.1.1 抽象数据类型栈的定义
​    3.1.2 栈的表示和实现
3.2   栈的应用举例
​    3.3.1 数制转换
​    3.3.2 括号匹配的检验
​    3.3.4  行编辑程序
​    3.3.5  迷宫求解
​    3.3.5  表达式求值
3.4  队列
​    3.4.1 抽象数据类型栈的定义
​    3.4.2 链队列—队列的链式表示和实现
​    3.4.3 循环队列—队列的顺序表示和实现
3.1  栈(Stack)
3.1.1 栈(stack)的定义
栈：限定仅在表尾进行插入和删除操作的线性表。
空栈：不含任何数据元素的栈。
允许插入和删除的一端称为栈顶，另一端称为栈底。

栈是一种后进先出(Last  In  First  Out)的线性表，简称为LIFO表。

栈的操作特性：后进先出
栈的概念及实现
例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？


注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。
堆栈的基本操作


插入（ 进栈、入栈）


删除 （出栈、退栈）


测试堆栈是否为空


测试堆栈是否已满


检索当前栈顶元素


特殊性


其操作是一般线性表的操作的一个子集。 "


插入和删除操作的位置受到限制。


栈的基本操作
(1) 初始化栈  initstack(S) : 将栈S置为一个空栈(不含任何元素)。
(2) 求栈长操作 getlen(S) : 求栈中元素的个数。
(3) 取栈顶元素 gettop(S,x) : 取栈S中栈顶元素。
(4) 入栈 push(S,x) : 将元素x插入到栈S中，也称为 “入栈”、“插入”、 “压入”。
(5) 出栈 pop(S,x) : 删除栈S中的栈顶元素，赋给x。也称为“退栈”、 “删除”、 “弹出”。
(6) 判栈空  emptystack (S) : 判断栈S是否为空，若为空，返回值为true，否则返回值为false。
(7)  输出栈操作  list(S) : 依次输出栈S中所有元素
例1：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。
A进 A出 B进 B出 C进 C出         ABC
A进 A出 B进 C进 C出 B出         ACB
A进 B进 B出 A出 C进 C出         BAC
A进 B进 B出 C进 C出 A出         BCA
A进 B进 C进 C出 B出 A出         CBA
不可能产生输出序列CAB
例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？
43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。
例3：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？
435612中到了12顺序不能实现；
135426可以实现。
3.1.2 栈的表示和实现
栈的顺序存储结构及实现
顺序栈——栈的顺序存储结构
如何改造数组实现栈的顺序存储？

确定用数组的哪一端表示栈底。
附设指针top指示栈顶元素在数组中的位置。
一、栈的顺序存储
栈是运算受限的线性表，线性表的存储结构对栈也适用。
1、顺序栈
​       栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。即：用一组连续的存储单元(数组)依次存放栈中的每个数据元素。栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点。
约定：用下标变量记录栈顶的位置，栈顶指针始终指向栈顶元素的上一个单元，用top(栈顶指针)表示。用base(栈底指针)记录栈底位置，为栈空间的起始位置。

栈的顺序存储表示：
#define INITSIZE  100   //栈的存储空间初始分配量
    typedef int ElemType;
    typedef struct
    {   int  top;                      //栈顶指针
         ElemType   *base;    //栈底指针，存放空间起始地址
         int  stacksize;            //当前栈空间的长度
     }sqstack;

顺序栈中“上溢”和“下溢”的概念。
设S是sqstack类型的变量。若栈底位置在向量的低端，即S.base[0]是栈底元素，那么栈顶指针S.top是正向增加的，即进栈时需将S.top加1，退栈时需将S.top 减1。
S.top == 0时表示空栈， S.top == stacksize表示栈满。
当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;
当栈空时再做退栈运算也将产生溢出，简称“下溢”。
上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象。

2、顺序栈上的基本操作实现
(1)  初始化栈S   (创建一个空栈S)
void initstack(sqstack *S)     
{     S->base=(ElemType *)malloc(INITSIZE*sizeof(ElemType));  
 
      S->top=0;          /*空栈标志*/
      S->stacksize = INITSIZE;     
}  

(2) 获取栈顶元素
int  gettop(sqstack S,ElemType *e)
{
      if ( S.top==0 )        /* 栈空 */
         {  printf(“Stack is empty!\n”);
             return 0;
          }
      *e= S.base[top-1]; 
      return 1;
}

(3)  进栈    (在栈顶插入新的元素x)
int  push ( sqstack *S , ElemType x )

{    if (S->top == S->stacksize)

​       { S->base=(ElemType *)realloc(S->base,

​                            (S->stacksize+1)*sizeof(ElemType)); 

​          if(!S->base) exit(-1);

​          S->stacksize++; 

​        }

​     S->base[S->top++] = x;   

​     return 1 ;

}

(4) 出栈  (取出S栈顶的元素值交给e)
int pop(sqstack *S, ElemType *e)
{
      if (S.top==0)  
      {  printf(“Stack is empty”);
          return 0;
       }
      *e=S->base [-- S->top ] ;
      return 1;
}


(5) 判断栈S是否为空
int stackempty(sqstack S)
    {   if (S.top==0) 
                  return  1 ;
         else   
                  return  0 ;
     }


结论：
由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。
二、 栈的链式存储
1、链栈
​        当栈中元素的数目变化范围较大或不清楚栈元素的数目时，应该考虑使用链式存储结构。
​        栈的链式存储结构称为“链栈” ，是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。
栈的链接存储结构及实现
链栈：栈的链接存储结构
如何改造链表实现栈的链接存储？

将哪一端作为栈顶？
将链头作为栈顶，方便操作。
链栈需要加头结点吗？
链栈不需要附设头结点。
•链式栈无栈满问题，空间可随意扩充
•插入与删除仅在栈顶处执行
•链栈的栈顶在链头
栈的链式存储结构实现：
typedef  int  ElemType;    
typedef struct node      //栈的结点类型
{  ElemType   data;       //栈的数据元素类型
    struct node *next;    //指向后继结点的指针
}linkstack; 
typedef struct stack
{
    linkstack   *top;    /*链栈的头指针*/
}STACK;


2、链栈的部分基本操作实现
(1)  初始化栈S  (创建一个不带头结点的空栈S )

void  initstack(STACK  *S)
 {     
       S->top=NULL;
 }


(2)   入栈
void push ( STACK *S , ElemType  e )
{   linkstack *p;
    p=( linkstack *) malloc( sizeof ( linkstack ) );
    if ( !p )  exit(0) ;
    p->data = e; 
    p->next = S->top;
    S->top = p;
}


(3)  出栈
void pop(STACK *S, ElemType *e)
{
      if ( S->top==NULL ) 
      {   printf(“Stack is empty”);
          exit(0); }
      else 
       {  *e=S->top->data;
           p=S->top;
           S->top= p -> next; 
           free(p);
        }
}

(4)  获取栈顶元素内容
void gettop(STACK S , ElemType *e)
{    if ( S.top==NULL ) 
      {   printf(“Stack is empty”);
           exit(0);
       }
       else *e=S.top->data ;
}


(5)   判断栈S是否空
int stackempty(STACK S)
{
         if (S.top==NULL) return 1;
         else return  0;
} 


两种实现方式的比较
v(1)顺序栈:入栈必须判断栈是否满了(上溢)
v(2)出栈和读栈顶元素操作,先判断是否为空。
v(3)链栈不须判断是否栈满。
顺序栈和链栈的比较
时间性能：相同，都是常数时间O(1)。
空间性能：
Ø顺序栈：有元素个数的限制和空间浪费的问题。
Ø链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。
总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。
3.2  栈的应用举例
【例1】将从键盘输入的字符序列逆置输出
比如，从键盘上输入：“tset a si sihT”，算法将输出：“This is a test”
以下是解决这个问题的完整算法。
#include “stdio.h”
typedef char SElemType;
void ReverseRead( )
             {STACK S; //定义一个栈结构S
                char ch;
                initstack(&S);             //初始化栈
       while ((ch=getchar())!=’\n’) 
               //从键盘输入字符，直到输入换行符为止 
         push(&S,ch);        //将输入的每个字符入栈
   while (!stackempty(S))   
                       //依次退栈并输出退出的字符
         {pop( &S , ch ) ; putchar ( ch ) ;         }
    putchar(‘\n’);}


【例2】数制转换
使用辗转相除法可将一个十进制数值转换成非十进制数值。即用该十进制数值除以非十进制数的基数(R进制数的基数为R)，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的非十进制数值。
该算法基于下列原理:
N = ( N / d ) * d + N % d
( 其中:  / 为整除运算,  % 为求余运算)
例如 (1348)10=(2504)8，其运算过程如下：
​                N         N/8(整除)       N%8(取余)
​           1348               168                   4
​             168                 21                   0
​               21                   2                   5
​                 2                   0                   2
我们看到所转换的8进制数按低位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。
算法思想如下：当N>0时重复1，2
​       1. 若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束。

用N / r 代替 N

以下是解决这个问题的完整算法: m
void Decimal_Binary ( )
{     int N;      STACK S;        //定义栈结构S
      initstack ( &S ) ;    //初始化栈S
      scanf(“%d”,&N);  //输入十进制正整数
      scanf(“%d”,&r);  //输入 正整数r (进制)
      while (N>0) 
        {    push( &S , N%r );     //余数入栈
             N /= r; //被除数整除以r，得到新的被除数
         }
     while ( !stackempty(S) ) 
              //依次从栈中弹出每一个余数，并输出之
       {   pop( &S , N );       
            printf(“%d”, N );       }
}


【例3】检验表达式中的括号匹配情况
​         假设在一个算术表达式中，可以包含三种括号：圆括号“(”和“)”，方括号“[”和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用。比如 ，[ { } [ ] ] [ ] ( ) 。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。
​        算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。
可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
(1) 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
​    (2) 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；
​    (3) 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
以下是解决这个问题的完整算法。
            typedef char ElemType;
            int Check( )
            {STACK S;        //定义栈结构S
             char ch;
            initstack(&S);      //初始化栈S
while ((ch=getchar())!=’\n’) //以字符序列的形式输入表达式
   if  ( ch==‘(’ || ch== ‘[’ || ch== ‘{’ ) 
           push(&S,ch); //遇左括号入栈
else  if( ch== ‘)’ )   
                 //在遇到右括号时，分别检测匹配情况
                if (stackempty ( S ) )  retrun 0;     
                else {  pop(&S,&ch);
                            if ( ch!= ‘(’  )  return 0; 
                         }
            else if (ch== ‘]’) 
                        if ( stackempty(S) ) retrun0;
                        else {  pop( &S,&ch) ;
                                    if ( ch!= ‘[’ ) return 0;  
                                 }
else if ( ch== ‘}’ ) 
                          if (stackempty(S) ) retrun 0;
                          else {  pop(&S,&ch); 
                                      if ( ch!= ‘{’ ) return 0; 
                                   }
                       else continue;
  if ( stackempty(S) ) return 1;
  else return 0;
}


【例4】表达式求值( 这是栈应用的典型例子 )
例如：3*（7 – 2 ）
（1）要正确求值，首先了解算术四则运算的规则：
​         a.  从左算到右
​         b.  先乘除，后加减
​         c.  先括号内，后括号外
​      由此，此表达式的计算顺序为：
​               3*（7 – 2 ）= 3 * 5 = 15
v（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符q1和q2 ，都要比较优先权关系。
v算符优先法所依据的算符间的优先关系
​                 见教材P53表3.1
v（是提供给计算机用的表！）
（3）算法思想：
•设定两栈：操作符栈 OPTR ，操作数栈 OPND
•栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 ‘#’；
•依次读入字符：操作数入OPND栈，操作符则判断：
​      栈顶元素<操作符：压入OPTR栈。
​      栈顶元素 =操作符且不为‘#’：弹出左括号；
​      栈顶元素>操作符：退栈、计算，将结果压入
​                                           OPND栈；
求解表达式  3*(7-2)  的求值过程如下：

算法如下：
Status    EvaluateExpression( OperandType  &result)   {
  InitStack(OPND); InitStack(OPTR);    
  Push(OPTR ,’#’);c=getchar();
  while( (c!=‘#’) ||(GetTop(OPTR)!=‘#’) )
   {   if (!In(c,OP)  {    Push(OPND,c);   c=getchar();}  
       else   switch(compare(GetTop(OPTR) ,c))
                 {case ‘<’ :    Push(OPTR , c); c=getchar();break; 
                   case ‘=’:   Pop(OPTR);c=getchar();break;
                  case ‘>’ : temat=Pop(OPTR); b=Pop();a=Pop();
                                  result=Operate(a,temat,b);  
                                  Push(OPND,result);
                                  break;  
                } //switch  
     }//while   
  result=GetTop(OPND);}//EvaluateExpression

3.3 　栈与递归
n递归的定义  若一个对象部分地包含它自己,  或用它自己给自己定义,  则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。
当多个函数构成嵌套调用时, 遵循 后调用先返回
以下三种情况常常用到递归方法
Ø递归定义的数学函数
Ø具有递归特性的数据结构
Ø可递归求解的问题
1，递归定义的数学函数:
•阶乘函数: 
•2阶Fibonaci数列: 

具有递归特性的数据结构 
可递归求解的问题:

迷宫问题　Hanoi塔问题
用分治法求解递归问题
分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
必备的三个条件
•1、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
•2、可以通过上述转化而使问题简化
•3、必须有一个明确的递归出口，或称递归的边界
【举例5】栈与递归的实现
在高级语言编制的程序中，调用函数与被调用函数之间的链接和信息交换必须通过栈进行。在一个函数的运行期间调用另一个函数时，运行被调用函数之前，系统需先完成三件事:
1)将所有的实在参数、返回地址等信息传递给被调用函数保存;
2)为被调用函数的局部变量分配存储区;
3)将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该完成:
1)保存被调函数的计算结果;
2)释放被调函数的数据区;
3)依照被调函数保存的返回地址将控制转移到调用函数。
​    多个函数嵌套调用的规则是:后调用先返回，此时的内存管理实行“栈式管理”
【例】栈与递归
​       栈的一个重要应用是在程序设计语言中实现递归过程。现实中，有许多实际问题是递归定义的，这时用递归方法可以使许多问题的结果大大简化，以 n!为例：
n!的定义为：

根据定义可以很自然的写出相应的递归函数:
        int fact (int n) 

         {   if (n==0)  return 1 ;

              else return  (n* fact (n-1) ) ;

         }

分治法求解递归问题算法的一般形式：
void   p (参数表) {
​        if   （递归结束条件）可直接求解步骤；-----基本项
​        else  p（较小的参数）；------归纳项
​       }
long Fact ( long n ) {
    if ( n == 0) return 1;//基本项
    else return n * Fact (n-1); //归纳项}

非递归算法:
long fac(int n)
{  
     long f=1;
      ElemType x;sqstack S;
      initstack(&S);
     while(n>0)   {   push(&S,n); n-- ;    }
     while(S.top!=0)   {   pop(&S,&x);  f=f*x;   }
      return f;
}

栈和递归的应用
​     —— 汉诺（ Hanoi）塔
​    传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。
移动时的规则：
•  每次只能移动一个盘子；
•  只能小盘子在大盘子上面；
•  可以使用任一柱子。
Hanoi塔问题 
n = 1，则直接从 A 移到 C。否则
(1)用 C 柱做过渡，将 A 的(n-1)个移到 B
(2)将 A 最后一个直接移到 C
(3)用 A 做过渡，将 B 的 (n-1) 个移到 C
分析：
​    设三根柱子分别为 x，y, z , 盘子在 x 柱上，要移到 z 柱上。
1、当 n=1 时，盘子直接从 x 柱移到 z 柱上；
2、当 n>1 时, 则
①设法将前n–1个盘子借助 z ，从 x 移到 y 柱上，把 盘子  n  从 x  移到z柱上；
② 把n –1 个盘子 从  y 移到  z 柱上。
算法如下：
Void    Hanoi  (  int  n,   char  x,  char  y,  char  z  )
1{  //将 n 个 编号从上到下为 1…n 的盘子从 x 柱，借助 y 柱移到 z 柱
2   if (  n  = = 1   )
3        move ( x , 1 , z  ) ;
​             //将编号为 1 的盘子从 x 柱移到 z 柱
4 else {
​              //将 n -1个 编号从上到下为1到n-1的盘子从 x 柱,借助 z 柱移到 y 柱
5    Hanoi (  n-1 ,  x ,  z  ,  y  )  ;
6move ( x ,   n,    z) ;
​                //将编号为  n 的盘子从 x 柱移到 z 柱
7    Hanoi ( n-1 , y , x , z );
​       //将 n -1个 编号从上到下为 1…n-1的盘子从 y 柱，借助 x 柱移到 z 柱    }} //Hanoi
递归的优缺点
优点：结构清晰，程序易读
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。
3.4   队列（Queue）
3.4.1  队列的定义及基本操作
v例1：排队购物。
v例2：操作系统中的作业排队。
v例3：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。
​        队列(Queue)也是一种运算受限的线性表。
队列的逻辑结构
队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。 a
空队列：不含任何数据元素的队列。
允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。
队列的逻辑结构

队列的操作特性：先进先出
练习
设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。
A）2     （B）3         （C）4    （D）6
队列的基本运算：
1.初始化队列  initqueue(Q) :将队列Q设置成一个空队列。
3.求队列长度 getlen(Q) : 返回队列的元素个数。
3.取队头元素 gettop(Q, e) :得到队列Q的队头元素之值，并用e返回其值。
4.入队列 enqueue(Q,x) :将元素x插入到队尾中，也称“进队” ，“插入”。
5.出队列 dequeue(Q,e) :将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。
6.判队空  emptyqueue(Q) :判断队列Q是否为空，若为空返回1，否则返回0。
7.输出队列   list(Q) :依次输出从队头到队尾的所有元素
3.4.2 链队列的表示和实现
链队列概念
队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。
​      显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。即：一个链队列由头指针和尾指针唯一确定。
队头指针即为链表的头指针
队列的链接存储结构及实现
非空链队列 
空链队列 
链队列示意图
非空队列

空队列	Q.front==Q.rear

将这两个指针封装在一起，链队列的类型linkqueue定义为一个结构类型： *
typedef int ElemType;
typedef  struct  node
     {    ElemType  data;
           struct node  *next;
     }qlink;  //链队列的结点的类型
typedef struct
     {   qlink  *front;   //队头指针
          qlink  *rear;    //队尾指针
     }linkqueue;  //队列类型


链队列上基本运算的实现
(1)初始化操作
void initqueue(linkqueue  *LQ)
{
    LQ->front=LQ->rear=(qlink *) malloc(sizeof(qlink));
    if(!LQ->front)  exit (0); 
    LQ->front->next=LQ->rear->next=NULL;  //初始化队头队尾指针
}


(2)队列的判空
int emptyqueue (linkqueue  LQ)
{
   return(LQ.front->next==NULL&&LQ.rear->next==NULL);
}


如果没有头结点会怎样？
front=rear=NULL
算法描述：
p->next=NULL;

rear=p; 

front=p;

(3)入队操作
void enqueue(linkqueue *LQ, ElemType  x)
{    qlink *p;
      p=(qlink * )malloc(sizeof(qlink));
      p–>data=x;
      p–>next=NULL;
     LQ->rear–>next=p;
     LQ->rear=p;
}


注：入队只需修改队尾指针。
链队列的实现——出队 lue
算法描述：
p=front->next; 

front->next=p->next

如何判断边界情况？ tml> ����*@(zN�}N
算法描述：
if (p->nextNULL)（或者rearp）
​    rear=front;
(4)出队操作
int  dequeue ( linkqueue *LQ, ElemType *e)
  {   linkqueue *p;
       if( emptyqueue(LQ)  )   return 0;
       p=LQ->front->next;
       *e=p–>data;
       LQ->front->next=p–>next;
       if( LQ->rear == p )
            LQ->rear=LQ->front;
       free(p);
       return OK;
    }


注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
3.4.3  队列的顺序表示和实现
1、顺序队列和循环队列
​       队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。
​
队列的顺序存储结构及实现
顺序队列：队列的顺序存储结构
如何改造数组实现队列的顺序存储？
例：a1a2a3a4依次入队

入队操作时间性能为O(1)
例：a1a2依次出队

出队操作时间性能为O(n）
如何改进出队的时间性能？
放宽队列的所有元素必须存储在数组的前n个单元这一条件 ，只要求队列的元素存储在数组中连续的位置
设置队头、队尾两个指针
头指针始终指向队头元素
尾指针始终指向队尾元素的下一位置。
v入队：将新元素插入所指的位置，然后尾指针加１。
v出队：删去所指的元素，队头指针加１并返回被删元素。
由此可见，当头尾指针相等时队列为空。

队列的顺序存储结构定义：
#define MAXQSIZE 100  //队列的最大长度
typedef int ElemType;
typedef  struct
{
  ElemType *base;  //队列空间的起始位置
   int front;   //队头指针,即头元素在数组中的位序
   int rear;    //队尾指针,指向队尾元素的下一位置
}cqueue;    


顺序队列
队空：Q.front==Q.rear
队满：Q.rear=MAXQSIZE（有假溢出）
求队长： Q.rear-Q.front
入队：新元素按 rear 指示位置加入，再将队尾指针加一 ，即 rear = rear + 1
出队：将front指示的元素取出，再将队头指针加一，即front = front + 1，
继续入队会出现什么情况？

假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。
因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。
因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
如何解决假溢出？

循环队列：将存储队列的数组头尾相接。
   为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。 


在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MAXQSIZE-1）时，其加1操作的结果是指向向量的下界0。
​      由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。 无法通过Q.front=Q.rear  来判断队列“空”还是“满”。
循环队列
队空：Q.front =Q. rear
队满：Q.front =(Q.rear + 1) % MAXCSIZE
入队:   Q.rear = (Q.rear + 1) % MAXCSIZE
出队:   Q.front = (front + 1) % MAXCSIZE
求队长: (Q.rear-Q.front+ MAXCSIZE)% MAXCSIZE
循环队列的基本运算实现
1、进队列
1）检查队列是否已满，若队满，则进行溢出错误处理；
2）将新元素赋给队尾指针所指单元；
3）将队尾指针后移一个位置(即加1)，指向下一单元。
int enqueue (cqueue *cq, ElemType  x)
     { if((cq->rear+1)%MAXCSIZE == cq->front)  return 0;
        cq->base[cq->rear]=x;  //插入x值到队尾
        cq->rear=(cq->rear+1)%MAXCSIZE;  //队尾


出队列

(1) 检查队列是否为空，若队空，进行下溢错误处理；
(2) 取队首元素的值。
(3) 将队首指针后移一个位置(即加1)；
int dequeue (cqueue *cq, ElemType *e)
{   if ( cq->rear== cq->front )  return 0 ; //队空
     *e=cq->base[cq->front] ;  //e值带回出队元素的值
     cq->front=(cq->front+1)%MAXCSIZE; //队头指针循环后移
     return 1 ; } 


循环队列和链队列的比较
时间性能:
循环队列和链队列的基本操作都需要常数时间
空间性能:
循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。
链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。
双端队列
v限定插入和删除操作在表的两端进行的线性表。也可以限定为输出受限（输入受限）的双端队列。
3.5 队列的应用举例
【举例1】模拟打印机缓冲区。
​        在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【举例2】CPU分时系统
​        在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。
【举例3】汽车加油站
​          随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。
小结
线性表、栈与队的异同点
相同点：
逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。
不同点：
① 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。
假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？
答：线性表是随机存储，可以实现，靠循环变量（j–）从表尾开始打印输出；
堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；
队列是先进先出，不易实现。
哪种方式最好，要具体情况具体分析。
(1)若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用出栈操作实现。
若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。
写出下列程序段的输出结果（栈的元素类型SElem Type为char）。
void main( ){
Stack S;   Char x,y;
InitStack(S);  x=’c’;y=’k’;
Push(S,x); Push(S,’a’);  Push(S,y);
Pop(S,x); Push(S,’t’); Push(S,x);
Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){ Pop(S,y);printf(y); };
Printf(x);}


答：输出为“stack”。
如果用一个循环数组q[0…m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。
编写实现队列的三个基本运算：
判空、入队、出队
判空：
int Empty(cqnode  cq)   //cq是cqnode类型的变量  
{if(cq.count==0) return(1)；
     else return(0);  //空队列}


入队:
int EnQueue(cqnode cq，elemtp x)
{if(count==m){printf(“队满\n”)；exit(0); }
             cq.q[(cq.front+count)%m]=x;    //x入队
             count++; return(1);   
                  //队列中元素个数增加1,入队成功。
}

出队:
int DelQueue(cqnode cq)
{if (count==0){printf(“队空\n”)；return(0);}
 printf(“出队元素”，cq.q[cq.front]);
x=cq.q[cq.front];
cq.front=(cq.front+1)%m;  //计算新的队头指针。
return(x)
}

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，不设头指针，请写出相应的入队列和出队列算法。
void EnQueue (LinkedList rear, ElemType x)
// rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。
{ s= (LinkedList) malloc (sizeof(LNode)); 
                                         //申请结点空间
 s->data=x;  s->next=rear->next;         
                                          //将s结点链入队尾
  rear->next=s;  rear=s;                 
   
   //rear指向新队尾
   void DeQueue (LinkedList  rear)
     // rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。
     { if (rear->next==rear)  { printf(“队空\n”); exit(0);}
       s=rear->next->next;        //s指向队头元素
       rear->next->next=s->next;    //队头元素出队。
       printf (“出队元素是”，s->data);
       if (s==rear) rear=rear->next;   //空队列
      free(s);
     }

已知一个带有表头结点的单链表，结点结构为： data|link
假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第K个位置上的结点 （K为正整数），若查找成功，算法输出该结点的data域的值，并返回1；否则只返回0。要求：
（1）描述算法的基本设计思想；
（2）描述算法的详细实现步骤，关键之处请给出简要注释。
基本设计思想：
增加P和P1两个指针变量和一个整型变量K。
从链表头向后遍历，其中指针p指向当前遍历的结点，指针p1指向p所指向结点的前k个结点，如果p之前没有k个结点，那么p1指向表头结点。用整型变量i表示当前遍历了多少个结点，当i>k时，p1随着每次的遍历，也向后移动一个结点。则遍历完成时，p1或者指向表头结点，或者指向链表中倒数第k个位置上的结点。
算法：
算法1:空间3，时间n
p=list->link;p1=list;i=1;
while(p)
{    p=p->link;
    i++;
    if (i> k) p1=p1->next;//保证了p1指向从p开始倒数的第k个结点
}
if (p1==list) return 0;//p之前没有k个结点
else 
{    printf("%d\n", p1->data);
    return 1;
}


算法2：空间3，时间n
p=list->link;   p1=list;  i=1;
while(p&&i<k)
{    p=p->link;
    i++;}
if (!p) return 0;//没有k 个结点
while(p)
{
    p=p->link;
    p1=p1->next;//保证了p1指向从p开始倒数的第k个结点

}
printf("%d\n", p1->data);
return 1;


算法3：首先遍历整个链表，获取链表的长度n。再重新遍历到链表的第n-k+1个结点，即为所求。
p=list->link;i=0;
while(p)
{    p=p->link;    i++;}    //i统计结点总数n
if (i<k) return 0;   //倒数也没有第k个节点
p=list->link
while(i>k)
{    p=p->link;       i--;} //刚好走过了n-k+1个结点
printf("%d\n", p->data);
return 1;


比较：
空间复杂度：算法3最好。
时间复杂度：算法2最好

文章目录
第一章——褚论
第二章——线性表
第三章——栈与队列
第四章——字符串
第五章——树与二叉树
第六章——图
第七章——排序
第八章——检索
判断题
单选题
程序填空题



第一章——褚论
第二章——线性表
第三章——栈与队列
第四章——字符串
第五章——树与二叉树
第六章——图
第七章——排序
第八章——检索

判断题


所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。

F错误。将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）



An algorithm to check for balancing symbols in an expression uses a stack to store the symbols.

T


balancing symbols 指的是一组匹配的符号，类似于圆括号，花括号，方括号。

可见这道题的意思是求解逆波兰表达式，使用stack。对。



在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。

T



n个元素通过一个栈产生n个元素的出栈序列，其中进栈和出栈操作的次数总是相等的。

T



通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。

F 231



在用数组表示的循环队列中，front值一定小于等于rear值。

F



"Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array.

F 中文版即是第一个题。



n个元素进队的顺序和出队的顺序总是一致的。

T 队列即为FIFO（先进先出，故一致）



栈底元素是不能删除的元素。

F 可以删除



顺序栈中元素值的大小是有序的。

这里顺序的意思是顺序存储结构，而不代表存储元素一定有序。



栈顶元素和栈底元素有可能是冋一个元素。

T



栈是一种对进栈、出栈操作总次数做了限制的线性表。

F 没有限制



对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。

T



环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。

T 公式为(rear-front+maxsize)%maxsize



若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。

T



栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。

F



两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。

T



不论是入队还是入栈操作，在顺序存储结构下都应考虑溢出现象。

T



可以通过少用一个存储空间的方法解决循环队列假溢出现象

F


少用一个存储空间的方法是为了解决无法判别队列满还是空。

而克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。


单选题


设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？

3 2 1 5 4

5 1 2 3 4

4 5 1 3 2

4 3 1 2 5



下列关于栈的叙述中，错误的是：

1采用非递归方式重写递归程序时必须使用栈

2函数调用时，系统要用栈保存必要的信息

3只要确定了入栈次序，即可确定出栈次序

4栈是一种受限的线性表，允许在其两端进行操作

仅 1

仅 1、2、3

仅 1、3、4

仅 2、3、4



循环顺序队列中是否可以插入下一个元素（）。

与队头指针和队尾指针的值有关

只与队尾指针的值有关，与队头指针的值无关

只与数组大小有关，与队首指针和队尾指针的值无关

与曾经进行过多少次插入操作有关



设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是：

1

3

5

1或者5

5要是在1出栈前入栈，则最后一个出栈的元素就是1。也可以在4321的顺序出栈完毕后，5入栈，再出栈，即最后一个出栈的元素是5.

综上，最后一个出栈的元素是1或5.



设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：

1

2

3

=4



若借助堆栈将中缀表达式a+bc+(de+f)g转换为后缀表达式，当读入f时，堆栈里的内容是什么(按堆栈自底向上顺序)

+(*+

+(+

++(+

abcde



表达式a(b+c)-d的后缀表达式是:

a b c + * d -

a b c d * + -

a b c * + d -

-+* a b c d


转换方法：

1)先按照运算符的优先级对中缀表达式加括号，变成

((a*(b+c))-d)

2)将运算符移到括号的后面，变成((a(bc)+)* d)-

3)去掉括号，得到abc+*d-



若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？

将链表头设为top

将链表尾设为top

随便哪端作为top都可以

链表头、尾都不适合作为top

这里头尾指针是链表的，和栈没关系，即头指针≠栈底，尾指针≠栈顶。

出栈入栈都是针对栈顶元素进行的操作，考虑到这个链表是单项的（从前往后不能从后往前），所以把头指针设成top，这样出栈入栈就是对表头操作，时间上快很多。



利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行:

top=0

top++

top–

top不变



若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：

1->2->3

2->3->4

4->1->2

答案不唯一



若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。

1和5

2和4

4和2

5和1

这里注意队列是FIFO，删除一个元素时，从队头出队，即front+=1，front=4，加入两个元素，rear+=2，rear=2；



判断一个循环队列QU（最多元素为MaxSize）为空的条件是（）。

QU.front  ==  QU.rear

QU.front  !=  QU.rear

QU.front  == (QU.rear + 1) % MaxSize

QU.front != (QU.rear + 1) % MaxSize

判断一个循环队列QU为满队列的条件是

QU.front == (QU.rear+1)%MaxSize


Suppose that all the integer operands are stored in the stack S1, and all the operators in the other stack S2​​ . The function F() does the following operations sequentially:
(1) Pop two operands a and b from S​1​​ ;

(2) Pop one operator op from S​2​​ ;

(3) Calculate b op a; and

(4) Push the result back to S​1 .

Now given { 5, 8, 3, 2 } in S1 (where 2 is at the top), and { *, -, + } in S2 (where + is at the top). What is remained at the top of S1 after F() is executed 3 times?

-15

15

-20

20

第一次执行F（），弹出a=2，b=3，弹出op为+，计算3+2=5并把5重新压回栈S1中。

第二次执行，弹出a=5，b=8，op为-，计算8-5=3，把3压回栈中。

第三次执行，弹出a=3，b=5，op为 * ，计算5 *3=15，并把15压回栈中


假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（　）。

a[–top]=x

a[top–]=x

a[++top]=x

a[top++]=x



经过以下栈的操作后，变量x的值为（　）。

InitStack(st);Push(st,a);Push(st,b);Pop(st,x);Top(st,x);

a

b

NULL

FALSE



若已知一个栈的入栈序列是1，2，3，4，其出栈序列为P1，P2,P3,P4,则P2，P4不可能是（ ）

2,4

2,1

4,3

3,4

4先出栈的情况下，3必须在它后一个出栈，而中间不可能是别的元素出栈



设有一个顺序共享栈Share[0:n-1]，其中第一个栈顶指针top1的初值为－1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是（　）。

top2-top1==1

top1-top21

top1top2

以上都不对



循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（　）。

队空：end1== end2;队满：end1==(end2+1)mod M

队空：end1== end2;队满：end2==(end1+1)mod (M-1)

队空：end2==(end1+1) mod M;队满：end1==(end2+1) mod M

队空：end1==(end2+1) mod M;队满：end2==(end1+1)mod (M-1)



下列说法中，正确的是（　）。

消除递归不一定需要使用栈

对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同

通常使用队列来处理函数或过程调用

队列和栈都是运算受限的线性表，只允许在表的两端进行运算



数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。

r-f

(n+f-r)%n

n+r-f

（n+r-f)%n



设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n * fact(n-1);

} 则计算fact(n)需要调用该函数的次数为（ ）。

n+1

n-1

n

n+2

直接假设代入，假设n=1，易得fact调用了两次。故选n+1。



若一个栈以向量V[1…n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。

top++; V[top]=x;

V[top]=x; top++;

top–; V[top]=x;

V[top]=x; top–;



下列与队列结构有关联的是

函数的递归调用

数组元素的引用

多重循环的执行

先到先服务的作业调度


程序填空题


本题要求求出不带头结点的单链表中的最大值并返回。

/* 求单链表值最大的结点 */
int getMaxNode(LinkNode* head)
{
	if (head == NULL)
		return INT_MIN;
	int first = head->data;
	int m = 
getMaxNode(head->next)
;
	if (m > first)return m;
	else return first;
}

getMaxNode(head->next)


本题要求采用递归方式求不带头结点的单链表的长度。

其中, 单链表结点类型定义如下:

typedef struct LNode {
	int data;
	struct LNode* next;
} LinkNode;
///求单链表长度
int getLength(LinkNode* L) {
	if (L == NULL)
		return 0;
	return 
1 + getLength(L->next)
;
}

1 + getLength(L->next)

已知循环队列的结构定义如下：
typedef struct
{
    int size, front, rear;
    int *element;
} AQUEUE;

说明：element 为存储队列数据元素的动态数组，size 为动态数组的尺寸，front 为队首元素的下标，rear 为队尾元素下一位置的下标。
假设有以下定义：

AQUEUE *queue;

判断 queue 所指队列为空的条件是：

queue->front == queue->rear

判断 queue 所指队列为满的条件是：

(queue->rear + 1) % queue->size == queue->front

queue 所指队列的长度是：

(queue->rear - queue->front + queue->size) % queue->size

【版权申明】未经博主同意，谢绝转载！（请尊重原创，博主保留追究权）
http://blog.csdn.net/javazejian/article/details/77410889

出自【zejian的博客】 

关联文章：
深入理解Java类型信息(Class对象)与反射机制
深入理解Java枚举类型(enum)
深入理解Java注解类型(@Annotation)
深入理解Java类加载器(ClassLoader)
深入理解Java并发之synchronized实现原理
Java并发编程-无锁CAS与Unsafe类及其并发包Atomic
深入理解Java内存模型(JMM)及volatile关键字
剖析基于并发AQS的重入锁(ReetrantLock)及其Condition实现原理
剖析基于并发AQS的共享锁的实现(基于信号量Semaphore)
并发之阻塞队列LinkedBlockingQueue与ArrayBlockingQueue
本篇主要是对Java并发中阻塞队列的LinkedBlockingQueue与ArrayBlockingQueue进行深入分析，以下是主要内容
文章目录
阻塞队列概要

阻塞队列概要
阻塞队列与我们平常接触的普通队列(LinkedList或ArrayList等)的最大不同点，在于阻塞队列支出阻塞添加和阻塞删除方法。

阻塞添加

所谓的阻塞添加是指当阻塞队列元素已满时，队列会阻塞加入元素的线程，直队列元素不满时才重新唤醒线程执行元素加入操作。


阻塞删除

阻塞删除是指在队列元素为空时，删除队列元素的线程将被阻塞，直到队列不为空再执行删除操作(一般都会返回被删除的元素)

由于Java中的阻塞队列接口BlockingQueue继承自Queue接口，因此先来看看阻塞队列接口为我们提供的主要方法
public interface BlockingQueue<E> extends Queue<E> {

	//将指定的元素插入到此队列的尾部（如果立即可行且不会超过该队列的容量）
	//在成功时返回 true，如果此队列已满，则抛IllegalStateException。 
	boolean add(E e); 
	
	//将指定的元素插入到此队列的尾部（如果立即可行且不会超过该队列的容量） 
	// 将指定的元素插入此队列的尾部，如果该队列已满， 
	//则在到达指定的等待时间之前等待可用的空间,该方法可中断 
	boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException; 
	
	//将指定的元素插入此队列的尾部，如果该队列已满，则一直等到（阻塞）。 
	void put(E e) throws InterruptedException; 
	
	//获取并移除此队列的头部，如果没有元素则等待（阻塞）， 
	//直到有元素将唤醒等待线程执行该操作 
	E take() throws InterruptedException; 
	
	//获取并移除此队列的头部，在指定的等待时间前一直等到获取元素， //超过时间方法将结束
	E poll(long timeout, TimeUnit unit) throws InterruptedException; 
	
	//从此队列中移除指定元素的单个实例（如果存在）。 
	boolean remove(Object o); 
}

	//除了上述方法还有继承自Queue接口的方法 
	//获取但不移除此队列的头元素,没有则跑异常NoSuchElementException 
	E element(); 
	
	//获取但不移除此队列的头；如果此队列为空，则返回 null。 
	E peek(); 
	
	//获取并移除此队列的头，如果此队列为空，则返回 null。 
	E poll();

这里我们把上述操作进行分类

插入方法：
add(E e) : 添加成功返回true，失败抛IllegalStateException异常
offer(E e) : 成功返回 true，如果此队列已满，则返回 false。
put(E e) :将元素插入此队列的尾部，如果该队列已满，则一直阻塞


删除方法:
remove(Object o) :移除指定元素,成功返回true，失败返回false
poll() : 获取并移除此队列的头元素，若队列为空，则返回 null
take()：获取并移除此队列头元素，若没有元素则一直阻塞。


检查方法
element() ：获取但不移除此队列的头元素，没有元素则抛异常
peek() :获取但不移除此队列的头；若队列为空，则返回 null。

阻塞队列的对元素的增删查操作主要就是上述的三类方法，通常情况下我们都是通过这3类方法操作阻塞队列，了解完阻塞队列的基本方法后，下面我们将分析阻塞队列中的两个实现类ArrayBlockingQueue和LinkedBlockingQueue的简单使用和实现原理，其中实现原理是这篇文章重点分析的内容。

#ArrayBlockingQueue的基本使用

ArrayBlockingQueue 是一个用数组实现的有界阻塞队列，其内部按先进先出的原则对元素进行排序，其中put方法和take方法为添加和删除的阻塞方法，下面我们通过ArrayBlockingQueue队列实现一个生产者消费者的案例，通过该案例简单了解其使用方式
这里写代码片

代码比较简单， Consumer 消费者和 Producer 生产者，通过ArrayBlockingQueue 队列获取和添加元素，其中消费者调用了take()方法获取元素当队列没有元素就阻塞，生产者调用put()方法添加元素，当队列满时就阻塞，通过这种方式便实现生产者消费者模式。比直接使用等待唤醒机制或者Condition条件队列来得更加简单。执行代码，打印部分Log如下
package com.zejian.concurrencys.Queue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.TimeUnit;

/**
 * Created by wuzejian on 2017/8/13
 */
public class ArrayBlockingQueueDemo {
    private final static ArrayBlockingQueue<Apple> queue= new ArrayBlockingQueue<>(1);
    public static void main(String[] args){
        new Thread(new Producer(queue)).start();
        new Thread(new Producer(queue)).start();
        new Thread(new Consumer(queue)).start();
        new Thread(new Consumer(queue)).start();
    }
}

 class Apple {
    public Apple(){
    }
 }

/**
 * 生产者线程
 */
class Producer implements Runnable{
    private final ArrayBlockingQueue<Apple> mAbq;
    Producer(ArrayBlockingQueue<Apple> arrayBlockingQueue){
        this.mAbq = arrayBlockingQueue;
    }

    @Override
    public void run() {
        while (true) {
            Produce();
        }
    }

    private void Produce(){
        try {
            Apple apple = new Apple();
            mAbq.put(apple);
            System.out.println("生产:"+apple);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

/**
 * 消费者线程
 */
class Consumer implements Runnable{

    private ArrayBlockingQueue<Apple> mAbq;
    Consumer(ArrayBlockingQueue<Apple> arrayBlockingQueue){
        this.mAbq = arrayBlockingQueue;
    }

    @Override
    public void run() {
        while (true){
            try {
                TimeUnit.MILLISECONDS.sleep(1000);
                comsume();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    private void comsume() throws InterruptedException {
        Apple apple = mAbq.take();
        System.out.println("消费Apple="+apple);
    }
}

生产:com.zejian.concurrencys.Queue.Apple@109967f
消费Apple=com.zejian.concurrencys.Queue.Apple@109967f
生产:com.zejian.concurrencys.Queue.Apple@269a77
生产:com.zejian.concurrencys.Queue.Apple@1ce746e
消费Apple=com.zejian.concurrencys.Queue.Apple@269a77
消费Apple=com.zejian.concurrencys.Queue.Apple@1ce746e
........

有点需要注意的是ArrayBlockingQueue内部的阻塞队列是通过重入锁ReenterLock和Condition条件队列实现的，所以ArrayBlockingQueue中的元素存在公平访问与非公平访问的区别，对于公平访问队列，被阻塞的线程可以按照阻塞的先后顺序访问队列，即先阻塞的线程先访问队列。而非公平队列，当队列可用时，阻塞的线程将进入争夺访问资源的竞争中，也就是说谁先抢到谁就执行，没有固定的先后顺序。创建公平与非公平阻塞队列代码如下：
//默认非公平阻塞队列
ArrayBlockingQueue queue = new ArrayBlockingQueue(2);
//公平阻塞队列
ArrayBlockingQueue queue1 = new ArrayBlockingQueue(2,true);

//构造方法源码
public ArrayBlockingQueue(int capacity) {
     this(capacity, false);
 }

public ArrayBlockingQueue(int capacity, boolean fair) {
     if (capacity <= 0)
         throw new IllegalArgumentException();
     this.items = new Object[capacity];
     lock = new ReentrantLock(fair);
     notEmpty = lock.newCondition();
     notFull =  lock.newCondition();
 }

其他方法如下：
//自动移除此队列中的所有元素。
void clear() 

//如果此队列包含指定的元素，则返回 true。          
boolean contains(Object o) 

//移除此队列中所有可用的元素，并将它们添加到给定collection中。           
int drainTo(Collection<? super E> c) 

//最多从此队列中移除给定数量的可用元素，并将这些元素添加到给定collection 中。       
int drainTo(Collection<? super E> c, int maxElements) 

//返回在此队列中的元素上按适当顺序进行迭代的迭代器。         
Iterator<E> iterator() 

//返回队列还能添加元素的数量
int remainingCapacity() 

//返回此队列中元素的数量。      
int size() 

//返回一个按适当顺序包含此队列中所有元素的数组。
Object[] toArray() 

//返回一个按适当顺序包含此队列中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。      
<T> T[] toArray(T[] a)

#ArrayBlockingQueue的实现原理剖析

##ArrayBlockingQueue原理概要

ArrayBlockingQueue的内部是通过一个可重入锁ReentrantLock和两个Condition条件对象来实现阻塞，这里先看看其内部成员变量
public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    /** 存储数据的数组 */
    final Object[] items;

    /**获取数据的索引，主要用于take，poll，peek，remove方法 */
    int takeIndex;

    /**添加数据的索引，主要用于 put, offer, or add 方法*/
    int putIndex;

    /** 队列元素的个数 */
    int count;


    /** 控制并非访问的锁 */
    final ReentrantLock lock;

    /**notEmpty条件对象，用于通知take方法队列已有元素，可执行获取操作 */
    private final Condition notEmpty;

    /**notFull条件对象，用于通知put方法队列未满，可执行添加操作 */
    private final Condition notFull;

    /**
       迭代器
     */
    transient Itrs itrs = null;

}

从成员变量可看出，ArrayBlockingQueue内部确实是通过数组对象items来存储所有的数据，值得注意的是ArrayBlockingQueue通过一个ReentrantLock来同时控制添加线程与移除线程的并非访问，这点与LinkedBlockingQueue区别很大(稍后会分析)。而对于notEmpty条件对象则是用于存放等待或唤醒调用take方法的线程，告诉他们队列已有元素，可以执行获取操作。同理notFull条件对象是用于等待或唤醒调用put方法的线程，告诉它们，队列未满，可以执行添加元素的操作。takeIndex代表的是下一个方法(take，poll，peek，remove)被调用时获取数组元素的索引，putIndex则代表下一个方法（put, offer, or add）被调用时元素添加到数组中的索引。图示如下

##ArrayBlockingQueue的(阻塞)添加的实现原理
//add方法实现，间接调用了offer(e)
public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }

//offer方法
public boolean offer(E e) {
     checkNotNull(e);//检查元素是否为null
     final ReentrantLock lock = this.lock;
     lock.lock();//加锁
     try {
         if (count == items.length)//判断队列是否满
             return false;
         else {
             enqueue(e);//添加元素到队列
             return true;
         }
     } finally {
         lock.unlock();
     }
 }

//入队操作
private void enqueue(E x) {
    //获取当前数组
    final Object[] items = this.items;
    //通过putIndex索引对数组进行赋值
    items[putIndex] = x;
    //索引自增，如果已是最后一个位置，重新设置 putIndex = 0;
    if (++putIndex == items.length)
        putIndex = 0;
    count++;//队列中元素数量加1
    //唤醒调用take()方法的线程，执行元素获取操作。
    notEmpty.signal();
}

这里的add方法和offer方法实现比较简单，其中需要注意的是enqueue(E x)方法，其方法内部通过putIndex索引直接将元素添加到数组items中，这里可能会疑惑的是当putIndex索引大小等于数组长度时，需要将putIndex重新设置为0，这是因为当前队列执行元素获取时总是从队列头部获取，而添加元素从中从队列尾部获取所以当队列索引（从0开始）与数组长度相等时，下次我们就需要从数组头部开始添加了，如下图演示

ok~,接着看put方法，它是一个阻塞添加的方法，
//put方法，阻塞时可中断
 public void put(E e) throws InterruptedException {
     checkNotNull(e);
      final ReentrantLock lock = this.lock;
      lock.lockInterruptibly();//该方法可中断
      try {
          //当队列元素个数与数组长度相等时，无法添加元素
          while (count == items.length)
              //将当前调用线程挂起，添加到notFull条件队列中等待唤醒
              notFull.await();
          enqueue(e);//如果队列没有满直接添加。。
      } finally {
          lock.unlock();
      }
  }

put方法是一个阻塞的方法，如果队列元素已满，那么当前线程将会被notFull条件对象挂起加到等待队列中，直到队列有空档才会唤醒执行添加操作。但如果队列没有满，那么就直接调用enqueue(e)方法将元素加入到数组队列中。到此我们对三个添加方法即put，offer，add都分析完毕，其中offer，add在正常情况下都是无阻塞的添加，而put方法是阻塞添加。这就是阻塞队列的添加过程。说白了就是当队列满时通过条件对象Condtion来阻塞当前调用put方法的线程，直到线程又再次被唤醒执行。总得来说添加线程的执行存在以下两种情况，一是，队列已满，那么新到来的put线程将添加到notFull的条件队列中等待，二是，有移除线程执行移除操作，移除成功同时唤醒put线程，如下图所示

##ArrayBlockingQueue的(阻塞)移除实现原理

关于删除先看poll方法，该方法获取并移除此队列的头元素，若队列为空，则返回 null
public E poll() {
      final ReentrantLock lock = this.lock;
       lock.lock();
       try {
           //判断队列是否为null，不为null执行dequeue()方法，否则返回null
           return (count == 0) ? null : dequeue();
       } finally {
           lock.unlock();
       }
    }
 //删除队列头元素并返回
 private E dequeue() {
     //拿到当前数组的数据
     final Object[] items = this.items;
      @SuppressWarnings("unchecked")
      //获取要删除的对象
      E x = (E) items[takeIndex];
      将数组中takeIndex索引位置设置为null
      items[takeIndex] = null;
      //takeIndex索引加1并判断是否与数组长度相等，
      //如果相等说明已到尽头，恢复为0
      if (++takeIndex == items.length)
          takeIndex = 0;
      count--;//队列个数减1
      if (itrs != null)
          itrs.elementDequeued();//同时更新迭代器中的元素数据
      //删除了元素说明队列有空位，唤醒notFull条件对象添加线程，执行添加操作
      notFull.signal();
      return x;
    }

poll()，获取并删除队列头元素，队列没有数据就返回null，内部通过dequeue()方法删除头元素，注释很清晰，这里不重复了。接着看remove(Object o)方法
public boolean remove(Object o) {
    if (o == null) return false;
    //获取数组数据
    final Object[] items = this.items;
    final ReentrantLock lock = this.lock;
    lock.lock();//加锁
    try {
        //如果此时队列不为null，这里是为了防止并发情况
        if (count > 0) {
            //获取下一个要添加元素时的索引
            final int putIndex = this.putIndex;
            //获取当前要被删除元素的索引
            int i = takeIndex;
            //执行循环查找要删除的元素
            do {
                //找到要删除的元素
                if (o.equals(items[i])) {
                    removeAt(i);//执行删除
                    return true;//删除成功返回true
                }
                //当前删除索引执行加1后判断是否与数组长度相等
                //若为true，说明索引已到数组尽头，将i设置为0
                if (++i == items.length)
                    i = 0; 
            } while (i != putIndex);//继承查找
        }
        return false;
    } finally {
        lock.unlock();
    }
}

//根据索引删除元素，实际上是把删除索引之后的元素往前移动一个位置
void removeAt(final int removeIndex) {

     final Object[] items = this.items;
      //先判断要删除的元素是否为当前队列头元素
      if (removeIndex == takeIndex) {
          //如果是直接删除
          items[takeIndex] = null;
          //当前队列头元素加1并判断是否与数组长度相等，若为true设置为0
          if (++takeIndex == items.length)
              takeIndex = 0;
          count--;//队列元素减1
          if (itrs != null)
              itrs.elementDequeued();//更新迭代器中的数据
      } else {
      //如果要删除的元素不在队列头部，
      //那么只需循环迭代把删除元素后面的所有元素往前移动一个位置
          //获取下一个要被添加的元素的索引，作为循环判断结束条件
          final int putIndex = this.putIndex;
          //执行循环
          for (int i = removeIndex;;) {
              //获取要删除节点索引的下一个索引
              int next = i + 1;
              //判断是否已为数组长度，如果是从数组头部（索引为0）开始找
              if (next == items.length)
                  next = 0;
               //如果查找的索引不等于要添加元素的索引，说明元素可以再移动
              if (next != putIndex) {
                  items[i] = items[next];//把后一个元素前移覆盖要删除的元
                  i = next;
              } else {
              //在removeIndex索引之后的元素都往前移动完毕后清空最后一个元素
                  items[i] = null;
                  this.putIndex = i;
                  break;//结束循环
              }
          }
          count--;//队列元素减1
          if (itrs != null)
              itrs.removedAt(removeIndex);//更新迭代器数据
      }
      notFull.signal();//唤醒添加线程
    }

remove(Object o)方法的删除过程相对复杂些，因为该方法并不是直接从队列头部删除元素。首先线程先获取锁，再一步判断队列count>0,这点是保证并发情况下删除操作安全执行。接着获取下一个要添加源的索引putIndex以及takeIndex索引 ，作为后续循环的结束判断，因为只要putIndex与takeIndex不相等就说明队列没有结束。然后通过while循环找到要删除的元素索引，执行removeAt(i)方法删除，在removeAt(i)方法中实际上做了两件事，一是首先判断队列头部元素是否为删除元素，如果是直接删除，并唤醒添加线程，二是如果要删除的元素并不是队列头元素，那么执行循环操作，从要删除元素的索引removeIndex之后的元素都往前移动一个位置，那么要删除的元素就被removeIndex之后的元素替换，从而也就完成了删除操作。接着看take()方法，是一个阻塞方法，直接获取队列头元素并删除。
//从队列头部删除，队列没有元素就阻塞，可中断
 public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
      lock.lockInterruptibly();//中断
      try {
          //如果队列没有元素
          while (count == 0)
              //执行阻塞操作
              notEmpty.await();
          return dequeue();//如果队列有元素执行删除操作
      } finally {
          lock.unlock();
      }
    }

take方法其实很简单，有就删除没有就阻塞，注意这个阻塞是可以中断的，如果队列没有数据那么就加入notEmpty条件队列等待(有数据就直接取走，方法结束)，如果有新的put线程添加了数据，那么put操作将会唤醒take线程，执行take操作。图示如下

public E peek() {
      final ReentrantLock lock = this.lock;
      lock.lock();
      try {
       //直接返回当前队列的头元素，但不删除
          return itemAt(takeIndex); // null when queue is empty
      } finally {
          lock.unlock();
      }
  }

final E itemAt(int i) {
      return (E) items[i];
  }

peek方法非常简单，直接返回当前队列的头元素但不删除任何元素。ok~，到此对于ArrayBlockingQueue的主要方法就分析完了。

#LinkedBlockingQueue的基本概要

LinkedBlockingQueue是一个由链表实现的有界队列阻塞队列，但大小默认值为Integer.MAX_VALUE，所以我们在使用LinkedBlockingQueue时建议手动传值，为其提供我们所需的大小，避免队列过大造成机器负载或者内存爆满等情况。其构造函数如下
//默认大小为Integer.MAX_VALUE
public LinkedBlockingQueue() {
       this(Integer.MAX_VALUE);
}

//创建指定大小为capacity的阻塞队列
public LinkedBlockingQueue(int capacity) {
     if (capacity <= 0) throw new IllegalArgumentException();
     this.capacity = capacity;
     last = head = new Node<E>(null);
 }

//创建大小默认值为Integer.MAX_VALUE的阻塞队列并添加c中的元素到阻塞队列
public LinkedBlockingQueue(Collection<? extends E> c) {
     this(Integer.MAX_VALUE);
     final ReentrantLock putLock = this.putLock;
     putLock.lock(); // Never contended, but necessary for visibility
     try {
         int n = 0;
         for (E e : c) {
             if (e == null)
                 throw new NullPointerException();
             if (n == capacity)
                 throw new IllegalStateException("Queue full");
             enqueue(new Node<E>(e));
             ++n;
         }
         count.set(n);
     } finally {
         putLock.unlock();
     }
 }

从源码看，有三种方式可以构造LinkedBlockingQueue，通常情况下，我们建议创建指定大小的LinkedBlockingQueue阻塞队列。LinkedBlockingQueue队列也是按 FIFO（先进先出）排序元素。队列的头部是在队列中时间最长的元素，队列的尾部 是在队列中时间最短的元素，新元素插入到队列的尾部，而队列执行获取操作会获得位于队列头部的元素。在正常情况下，链接队列的吞吐量要高于基于数组的队列（ArrayBlockingQueue），因为其内部实现添加和删除操作使用的两个ReenterLock来控制并发执行，而ArrayBlockingQueue内部只是使用一个ReenterLock控制并发，因此LinkedBlockingQueue的吞吐量要高于ArrayBlockingQueue。注意LinkedBlockingQueue和ArrayBlockingQueue的API几乎是一样的，但它们的内部实现原理不太相同，这点稍后会分析。使用LinkedBlockingQueue，我们同样也能实现生产者消费者模式。只需把前面ArrayBlockingQueue案例中的阻塞队列对象换成LinkedBlockingQueue即可。这里限于篇幅就不贴重复代码了。接下来我们重点分析LinkedBlockingQueue的内部实现原理，最后我们将对ArrayBlockingQueue和LinkedBlockingQueue 做总结，阐明它们间的不同之处。
#LinkedBlockingQueue的实现原理剖析

##原理概论
LinkedBlockingQueue是一个基于链表的阻塞队列，其内部维持一个基于链表的数据队列，实际上我们对LinkedBlockingQueue的API操作都是间接操作该数据队列，这里我们先看看LinkedBlockingQueue的内部成员变量
public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    /**
     * 节点类，用于存储数据
     */
    static class Node<E> {
        E item;

        /**
         * One of:
         * - the real successor Node
         * - this Node, meaning the successor is head.next
         * - null, meaning there is no successor (this is the last node)
         */
        Node<E> next;

        Node(E x) { item = x; }
    }

    /** 阻塞队列的大小，默认为Integer.MAX_VALUE */
    private final int capacity;

    /** 当前阻塞队列中的元素个数 */
    private final AtomicInteger count = new AtomicInteger();

    /**
     * 阻塞队列的头结点
     */
    transient Node<E> head;

    /**
     * 阻塞队列的尾节点
     */
    private transient Node<E> last;

    /** 获取并移除元素时使用的锁，如take, poll, etc */
    private final ReentrantLock takeLock = new ReentrantLock();

    /** notEmpty条件对象，当队列没有数据时用于挂起执行删除的线程 */
    private final Condition notEmpty = takeLock.newCondition();

    /** 添加元素时使用的锁如 put, offer, etc */
    private final ReentrantLock putLock = new ReentrantLock();

    /** notFull条件对象，当队列数据已满时用于挂起执行添加的线程 */
    private final Condition notFull = putLock.newCondition();

}

从上述可看成，每个添加到LinkedBlockingQueue队列中的数据都将被封装成Node节点，添加的链表队列中，其中head和last分别指向队列的头结点和尾结点。与ArrayBlockingQueue不同的是，LinkedBlockingQueue内部分别使用了takeLock 和 putLock 对并发进行控制，也就是说，添加和删除操作并不是互斥操作，可以同时进行，这样也就可以大大提高吞吐量。这里再次强调如果没有给LinkedBlockingQueue指定容量大小，其默认值将是Integer.MAX_VALUE，如果存在添加速度大于删除速度时候，有可能会内存溢出，这点在使用前希望慎重考虑。至于LinkedBlockingQueue的实现原理图与ArrayBlockingQueue是类似的，除了对添加和移除方法使用单独的锁控制外，两者都使用了不同的Condition条件对象作为等待队列，用于挂起take线程和put线程。

ok~,下面我们看看其其内部添加过程和删除过程是如何实现的。
##添加方法的实现原理
对于添加方法，主要指的是add，offer以及put，这里先看看add方法和offer方法的实现
public boolean add(E e) {
     if (offer(e))
         return true;
     else
         throw new IllegalStateException("Queue full");
}

从源码可以看出，add方法间接调用的是offer方法，如果add方法添加失败将抛出IllegalStateException异常，添加成功则返回true，那么下面我们直接看看offer的相关方法实现
public boolean offer(E e) {
     //添加元素为null直接抛出异常
     if (e == null) throw new NullPointerException();
      //获取队列的个数
      final AtomicInteger count = this.count;
      //判断队列是否已满
      if (count.get() == capacity)
          return false;
      int c = -1;
      //构建节点
      Node<E> node = new Node<E>(e);
      final ReentrantLock putLock = this.putLock;
      putLock.lock();
      try {
          //再次判断队列是否已满，考虑并发情况
          if (count.get() < capacity) {
              enqueue(node);//添加元素
              c = count.getAndIncrement();//拿到当前未添加新元素时的队列长度
              //如果容量还没满
              if (c + 1 < capacity)
                  notFull.signal();//唤醒下一个添加线程，执行添加操作
          }
      } finally {
          putLock.unlock();
      }
      // 由于存在添加锁和消费锁，而消费锁和添加锁都会持续唤醒等到线程，因此count肯定会变化。
      //这里的if条件表示如果队列中还有1条数据
      if (c == 0) 
        signalNotEmpty();//如果还存在数据那么就唤醒消费锁
    return c >= 0; // 添加成功返回true，否则返回false
  }

//入队操作
private void enqueue(Node<E> node) {
     //队列尾节点指向新的node节点
     last = last.next = node;
}

//signalNotEmpty方法
private void signalNotEmpty() {
      final ReentrantLock takeLock = this.takeLock;
      takeLock.lock();
          //唤醒获取并删除元素的线程
          notEmpty.signal();
      } finally {
          takeLock.unlock();
      }
  }

这里的Offer()方法做了两件事，第一件事是判断队列是否满，满了就直接释放锁，没满就将节点封装成Node入队，然后再次判断队列添加完成后是否已满，不满就继续唤醒等到在条件对象notFull上的添加线程。第二件事是，判断是否需要唤醒等到在notEmpty条件对象上的消费线程。这里我们可能会有点疑惑，为什么添加完成后是继续唤醒在条件对象notFull上的添加线程而不是像ArrayBlockingQueue那样直接唤醒notEmpty条件对象上的消费线程？而又为什么要当if (c == 0)时才去唤醒消费线程呢？

唤醒添加线程的原因，在添加新元素完成后，会判断队列是否已满，不满就继续唤醒在条件对象notFull上的添加线程，这点与前面分析的ArrayBlockingQueue很不相同，在ArrayBlockingQueue内部完成添加操作后，会直接唤醒消费线程对元素进行获取，这是因为ArrayBlockingQueue只用了一个ReenterLock同时对添加线程和消费线程进行控制，这样如果在添加完成后再次唤醒添加线程的话，消费线程可能永远无法执行，而对于LinkedBlockingQueue来说就不一样了，其内部对添加线程和消费线程分别使用了各自的ReenterLock锁对并发进行控制，也就是说添加线程和消费线程是不会互斥的，所以添加锁只要管好自己的添加线程即可，添加线程自己直接唤醒自己的其他添加线程，如果没有等待的添加线程，直接结束了。如果有就直到队列元素已满才结束挂起，当然offer方法并不会挂起，而是直接结束，只有put方法才会当队列满时才执行挂起操作。注意消费线程的执行过程也是如此。这也是为什么LinkedBlockingQueue的吞吐量要相对大些的原因。


为什么要判断if (c == 0)时才去唤醒消费线程呢，这是因为消费线程一旦被唤醒是一直在消费的（前提是有数据），所以c值是一直在变化的，c值是添加完元素前队列的大小，此时c只可能是0或c>0，如果是c=0，那么说明之前消费线程已停止，条件对象上可能存在等待的消费线程，添加完数据后应该是c+1，那么有数据就直接唤醒等待消费线程，如果没有就结束啦，等待下一次的消费操作。如果c>0那么消费线程就不会被唤醒，只能等待下一个消费操作（poll、take、remove）的调用，那为什么不是条件c>0才去唤醒呢？我们要明白的是消费线程一旦被唤醒会和添加线程一样，一直不断唤醒其他消费线程，如果添加前c>0，那么很可能上一次调用的消费线程后，数据并没有被消费完，条件队列上也就不存在等待的消费线程了，所以c>0唤醒消费线程得意义不是很大，当然如果添加线程一直添加元素，那么一直c>0，消费线程执行的换就要等待下一次调用消费操作了（poll、take、remove）。

##移除方法的实现原理
关于移除的方法主要是指remove和poll以及take方法，下面一一分析
public boolean remove(Object o) {
   if (o == null) return false;
     fullyLock();//同时对putLock和takeLock加锁
     try {
         //循环查找要删除的元素
         for (Node<E> trail = head, p = trail.next;
              p != null;
              trail = p, p = p.next) {
             if (o.equals(p.item)) {//找到要删除的节点
                 unlink(p, trail);//直接删除
                 return true;
             }
         }
         return false;
     } finally {
         fullyUnlock();//解锁
     }
    }

//两个同时加锁
void fullyLock() {
       putLock.lock();
       takeLock.lock();
   }

void fullyUnlock() {
      takeLock.unlock();
      putLock.unlock();
  }

remove方法删除指定的对象，这里我们可能会诧异，为什么同时对putLock和takeLock加锁？这是因为remove方法删除的数据的位置不确定，为了避免造成并非安全问题，所以需要对2个锁同时加锁。
public E poll() {
         //获取当前队列的大小
        final AtomicInteger count = this.count;
        if (count.get() == 0)//如果没有元素直接返回null
            return null;
        E x = null;
        int c = -1;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            //判断队列是否有数据
            if (count.get() > 0) {
                //如果有，直接删除并获取该元素值
                x = dequeue();
                //当前队列大小减一
                c = count.getAndDecrement();
                //如果队列未空，继续唤醒等待在条件对象notEmpty上的消费线程
                if (c > 1)
                    notEmpty.signal();
            }
        } finally {
            takeLock.unlock();
        }
        //判断c是否等于capacity，这是因为如果满说明NotFull条件对象上
        //可能存在等待的添加线程
        if (c == capacity)
            signalNotFull();
        return x;
    }

  private E dequeue() {
        Node<E> h = head;//获取头结点
        Node<E> first = h.next; 获取头结的下一个节点（要删除的节点）
        h.next = h; // help GC//自己next指向自己，即被删除
        head = first;//更新头结点
        E x = first.item;//获取删除节点的值
        first.item = null;//清空数据，因为first变成头结点是不能带数据的，这样也就删除队列的带数据的第一个节点
        return x;
    }

poll方法也比较简单，如果队列没有数据就返回null，如果队列有数据，那么就取出来，如果队列还有数据那么唤醒等待在条件对象notEmpty上的消费线程。然后判断if (c == capacity)为true就唤醒添加线程，这点与前面分析if(c==0)是一样的道理。因为只有可能队列满了，notFull条件对象上才可能存在等待的添加线程。
public E take() throws InterruptedException {
        E x;
        int c = -1;
        //获取当前队列大小
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lockInterruptibly();//可中断
        try {
            //如果队列没有数据，挂机当前线程到条件对象的等待队列中
            while (count.get() == 0) {
                notEmpty.await();
            }
            //如果存在数据直接删除并返回该数据
            x = dequeue();
            c = count.getAndDecrement();//队列大小减1
            if (c > 1)
                notEmpty.signal();//还有数据就唤醒后续的消费线程
        } finally {
            takeLock.unlock();
        }
        //满足条件，唤醒条件对象上等待队列中的添加线程
        if (c == capacity)
            signalNotFull();
        return x;
    }

take方法是一个可阻塞可中断的移除方法，主要做了两件事，一是，如果队列没有数据就挂起当前线程到 notEmpty条件对象的等待队列中一直等待，如果有数据就删除节点并返回数据项，同时唤醒后续消费线程，二是尝试唤醒条件对象notFull上等待队列中的添加线程。 到此关于remove、poll、take的实现也分析完了，其中只有take方法具备阻塞功能。remove方法则是成功返回true失败返回false，poll方法成功返回被移除的值，失败或没数据返回null。下面再看看两个检查方法，即peek和element
//构造方法，head 节点不存放数据
 public LinkedBlockingQueue(int capacity) {
       if (capacity <= 0) throw new IllegalArgumentException();
       this.capacity = capacity;
       last = head = new Node<E>(null);
   }

 public E element() {
        E x = peek();//直接调用peek
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();//没数据抛异常
    }

 public E peek() {
        if (count.get() == 0)
            return null;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            //获取头结节点的下一个节点
            Node<E> first = head.next;
            if (first == null)
                return null;//为null就返回null
            else
                return first.item;//返回值
        } finally {
            takeLock.unlock();
        }
    }

从代码来看，head头结节点在初始化时是本身不带数据的，仅仅作为头部head方便我们执行链表的相关操作。peek返回直接获取头结点的下一个节点返回其值，如果没有值就返回null，有值就返回节点对应的值。element方法内部调用的是peek，有数据就返回，没数据就抛异常。下面我们最后来看两个根据时间阻塞的方法，比较有意思，利用的Conditin来实现的。
//在指定时间内阻塞添加的方法，超时就结束
 public boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException {

        if (e == null) throw new NullPointerException();
        //将时间转换成纳秒
        long nanos = unit.toNanos(timeout);
        int c = -1;
        //获取锁
        final ReentrantLock putLock = this.putLock;
        //获取当前队列大小
        final AtomicInteger count = this.count;
        //锁中断(如果需要)
        putLock.lockInterruptibly();
        try {
            //判断队列是否满
            while (count.get() == capacity) {
                if (nanos <= 0)
                    return false;
                //如果队列满根据阻塞的等待
                nanos = notFull.awaitNanos(nanos);
            }
            //队列没满直接入队
            enqueue(new Node<E>(e));
            c = count.getAndIncrement();
            //唤醒条件对象上等待的线程
            if (c + 1 < capacity)
                notFull.signal();
        } finally { 
            putLock.unlock();
        }
        //唤醒消费线程
        if (c == 0)
            signalNotEmpty();
        return true;
    }

对于这个offer方法，我们重点来看看阻塞的这段代码
//判断队列是否满
 while (count.get() == capacity) {
        if (nanos <= 0)
            return false;
        //如果队列满根据阻塞的等待
        nanos = notFull.awaitNanos(nanos);
    }

//CoditionObject（Codition的实现类）中的awaitNanos方法
 public final long awaitNanos(long nanosTimeout)
                throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            //这里是将当前添加线程封装成NODE节点加入Condition的等待队列中
            //注意这里的NODE是AQS的内部类Node
            Node node = addConditionWaiter();
            //加入等待，那么就释放当前线程持有的锁
            int savedState = fullyRelease(node);
            //计算过期时间
            final long deadline = System.nanoTime() + nanosTimeout;
            int interruptMode = 0;

            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    transferAfterCancelledWait(node);
                    break;
                }
                //主要看这里！！由于是while 循环，这里会不断判断等待时间
                //nanosTimeout 是否超时
                //static final long spinForTimeoutThreshold = 1000L;
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);//挂起线程
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                //重新计算剩余等待时间，while循环中继续判断下列公式
                //nanosTimeout >= spinForTimeoutThreshold
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return deadline - System.nanoTime();
        }

awaitNanos方法中，根据传递进来的时间计算超时阻塞nanosTimeout，然后通过while循环中判断nanosTimeout >= spinForTimeoutThreshold 该公式是否成立，当其为true时则说明超时时间nanosTimeout 还未到期，再次计算nanosTimeout = deadline - System.nanoTime();即nanosTimeout ，持续判断，直到nanosTimeout 小于spinForTimeoutThreshold结束超时阻塞操作，方法也就结束。这里的spinForTimeoutThreshold其实更像一个经验值，因为非常短的超时等待无法做到十分精确，因此采用了spinForTimeoutThreshold这样一个临界值。offer(E e, long timeout, TimeUnit unit)方法内部正是利用这样的Codition的超时等待awaitNanos方法实现添加方法的超时阻塞操作。同样对于poll(long timeout, TimeUnit unit)方法也是一样的道理。
#LinkedBlockingQueue和ArrayBlockingQueue迥异
通过上述的分析，对于LinkedBlockingQueue和ArrayBlockingQueue的基本使用以及内部实现原理我们已较为熟悉了，这里我们就对它们两间的区别来个小结
1.队列大小有所不同，ArrayBlockingQueue是有界的初始化必须指定大小，而LinkedBlockingQueue可以是有界的也可以是无界的(Integer.MAX_VALUE)，对于后者而言，当添加速度大于移除速度时，在无界的情况下，可能会造成内存溢出等问题。
2.数据存储容器不同，ArrayBlockingQueue采用的是数组作为数据存储容器，而LinkedBlockingQueue采用的则是以Node节点作为连接对象的链表。
3.由于ArrayBlockingQueue采用的是数组的存储容器，因此在插入或删除元素时不会产生或销毁任何额外的对象实例，而LinkedBlockingQueue则会生成一个额外的Node对象。这可能在长时间内需要高效并发地处理大批量数据的时，对于GC可能存在较大影响。
4.两者的实现队列添加或移除的锁不一样，ArrayBlockingQueue实现的队列中的锁是没有分离的，即添加操作和移除操作采用的同一个ReenterLock锁，而LinkedBlockingQueue实现的队列中的锁是分离的，其添加采用的是putLock，移除采用的则是takeLock，这样能大大提高队列的吞吐量，也意味着在高并发的情况下生产者和消费者可以并行地操作队列中的数据，以此来提高整个队列的并发性能。