栈

栈是限定仅在表尾进行插入和删除操作的线性表。

栈又称为后进先出（Last In First Out ）的线性表，简称LIFO结构。

栈只对线性表的插入和删除的位置做了限制，并没有对元素的进出时间做限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶出栈就可以。

栈的顺序存储结构

我们通常将数组下标为0的一端作为栈低，因为首元素都存在栈帝，变化最小。
我们定义一个top变量用来指示栈顶元素在数组中的位置。

进栈 O(1)

String push(Stack s,SelemType e){
    if(s.top == MAXZIZE -1){ //栈已满
      return "ERROR";
   }
   s.top = s.top ++;
   s.data[ s.top] = e;
   return "OK"; 
}

出栈 O(1)

String pop(Stack s,SelemType e){
    if(s.top == -1){ //空栈
      return "ERROR";
   }
    e = s.data[ s.top];//e为出栈元素
   s.top = s.top --;
   return "OK"; 
}

两栈共享空间

先来说说为什么会有这样的需求？因为栈有一个很大的缺陷，就是必须事先确定好数组的长度，万一不够用了，就需要通过编程手段来动态的扩展数组的代销，比较麻烦，所以如果存在两个相同类型的栈，我们可以通过共享空间的的方式来最大限度的利用事先已经开辟好的存储空间。
下面说一下两栈共享空间的原理：

image.png

我们让其中一个栈的栈底称为数组的起始位置，另外一个栈的栈底称为数组的末尾，新数组长度为n。两个栈在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，只要他们不见面，两个栈就可以共享存储空间。
当top1等于-1时代表栈1为空，而当top2等于n时，级栈2为空。
当top1+1 = top2时为栈满状态

共享空间入栈

String push(Stack s,SelemType e,int stackNumber){
    if(s.top1 +1 == s.top2){ //栈已满
        return "ERROR";
    }

    if(stackNumber == 1){ //栈1进栈
    s.data[s.top1 ++] = e;
    }
 
  if(stackNumber == 2){ //栈2进栈
    s.data[s.top2 ++] = e;
    }

  return “OK”
}

共享空间出栈

String pop(Stack s,SelemType e,int stackNumber){
    if(stackNumber == 1){ 
      if(s.top1 == -1)
          return "ERROR";//栈1为空
       e = s.data[s.top1 --] ;
    }
 
  if(stackNumber == 2){ 
    if(s.top2 == MAXSIZE)
          return "ERROR";//栈2为空
        e = s.data[s.top2 ++] ;
    }
  return “OK”
}

使用场景

事实上，使用这样的数据结构，通常都是当两个梢的空间需求有相反关系时，也
就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定是有
一个你不知道的人在做卖出操作 。有人赚钱，就肯定是有人赔钱。这样使用两钱共享空间存储方法才有比较大的意义。否则两个钱都在不停地增长，那很快就会因枝满而溢出了。

栈的链式存储结构

链栈相对于数组栈的优势不存在栈满的情况，而且也不用事先确定栈的大小。

链栈进栈 O(1)

image.png

String push(stack s,SelemType e){
  Node node = new Node()；
  node.data = e;
  node.next = s.top;//把当前栈顶数据赋值给当前元素的后继
  s.top = node; //把新的结点赋值给栈顶
  s.count = s.count ++;//栈的数量加1
  return “OK”
}

链栈出栈 O(1)

image.png

String pop(stack s,SelemType e){
    if(s.count == 0) //空栈
        return "ERROR"
  e = s.top.data;
  Node node = null;
  node= s.top;
  s.top = s.top.next //把栈顶指针向下移动一个位置
  node = null； //释放空结点
  s.count = s.count --;//栈的数量减1
  return “OK”
}

栈的应用

递归:斐波那契数列实现
四则运算表达式求值：仔细观察后发现，括号都是成对出现的，有左括号就一定会有右括号，对于多重括号，最终也是完全嵌套匹配的。这用栈结构正好合适，只有碰到左括号，就将此左括号进栈，不管表达式有多少重括号，反正遇到左括号就进栈，而后面出现右括号时，就让栈顶的左括号出栈。期间让数字运算，这样，最终有括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最终再因全部匹配成功后成为空栈的结果。

逆波兰算法：后缀表达式

例子：9+（3-1）*3+10/2如果用后缀表示法应该是"9 3 1 - 3 * + 10 2 / +"
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进钱，一直到最终获得结果。

标准正则表达式转后缀表达式

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分。若是符号，则判断其与栈顶符号的优先级（左括号由于还未配对故直接进栈），是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

运算步骤

1. 将中缀表达式转化为后缀表达式(栈用来迸出运算的符号)。
2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

队列

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。
队列是一种先进先出（First in First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头

队列的顺序存储结构

顺序存储的队列需建立一个大于 n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为 0的一端即是队头。
入列：由于入队操作其实就是在对尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。
出列：队列的所有元素都得向前移动，一保证队列的对头的位置不为空，因此时间复杂度为O(n)。

循环队列

我们把首尾相接的顺序存储结构队列称为循环队列。

image.png

判断循环队列满或空的2中方法

1、设置一个标致变量flag，当front == rear，且flag =0时队列为空，当front == rear，且flag =1时队列为满。
2、当front == rear时，队列为空，当队列满时，我们修改其条件，保留一个元素空间。也就是说。队列满时，数组中还有一个空闲单元(不允许出现上图front和rear重合的状态)。

image.png

由于rear可能比front大，也有可能比front小，所以尽管他们只差一个位置时就是满的情况，当也有可能是相差真正一圈一圈（比如上图左边的图）。假设队列的最大尺寸为QueueSize，那么判断队列满的公式为：

(rear + 1)%QueueSize == front
计算队列长度：
(rear - front + QueueSize ) %QueueSize

入队

String EnQueue(Queue Q,QElemType e){
      if(Q.rear + 1) % MAXSIZE == Q.front)//队列已满
             return "ERROR"

     Q.data[Q.rear] = e;
     Q.rear = (Q.rear + 1) % MAXSIZE;//先后移动一个位置 ，若到最后这转到数组头部
   return "OK"
}

出队

String EnQueue(Queue Q,QElemType e){
      if(Q.rear  == Q.front)//队列为空
             return "ERROR"
     e =  Q.data[Q.front];
     Q.front= (Q.front+ 1) % MAXSIZE;//先后移动一个位置 ，若到最后这转到数组头部
    return "OK"
}

队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链衰，只不过它只能尾进头出而已，
我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点,而队尾指针指向终端结点

入队

链式队列不存在队列为满的状态

image.png

String EnQueue(Queue Q,QElemType e){
     Node node = new Node()；
     node.data = e;
     node.next = null
     Q.rear.next = node;//把新节点赋值给原队尾结点的后继
     Q.rear = node;//把当前的结点设置为尾结点
     return "OK"
}

出队

image.png

String EnQueue(Queue Q,QElemType e){
    Node p = new Node()；
    if(Q.front == Q.rear)//队列为空
         return "ERROR";
    p = Q.front.next; //将要删除的结点赋值给p
    e = p.data;
    Q.front.next = p.next;//将原队通结点的后继赋值给头结点后继
    if(Q.rear == p){ // 若对头是对尾。删除后将rear指向头结点
         Q.rear = Q.front;
      }
     p = null；//将删除的结点置空
     return "OK"
}

总结

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基
本操作都是常数时间，即都为 0(1) 的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域， 会产生 些空间上的开销，但也可以接受 所以在空间上，链队列更加灵
活。总的来说，在可以确定队列长度最大值的情况 ，建议用循环队列，如果你无法
预估队列的长度时，则用链队列。

栈和队列总结

image.png