栈和队列的相关应用（一）

栈和队列

一 、 栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出LIFO（Last In First Out）的原则。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

• 栈的使用

根据栈的底层代码可以得知。栈的底层就是使用数组来实现的

Java 集合框架中的 Stack 继承自 Vector

• 由于 Vector 有 4 个构造函数，加上 Stack 本身的一种，也就是说有 5 中创建 Stack 的方法
• 跟 Vector 一样，它是可以由数组实现的栈。

那么就可以使用数组来简单的模拟实现栈

• 栈的模拟实现

  • 初始化栈

  public class MyStack {
      public int elem[];
  
      public int usedsize;
  
      //设置一个默认的大小
      public static final int DEFAULT_SIZE = 10;
  
      public MyStack(){
          this.elem = new int[DEFAULT_SIZE];
      }

  • 压栈的实现

   public int push(int val){
       //将val压入栈，并返回val,判断栈是否为满，如栈满则进行扩容
          if(isFull()){
              elem = Arrays.copyOf(elem,2*elem.length);
          }
       //使用数组实现栈时，栈顶元素的下标即usedsize-1，在usedsize下标处新增元素即可
          this.elem[usedsize] = val;
          usedsize++;
          return val;
      }

  • 判满实现

  public boolean isFull(){
          return usedsize == elem.length;
      //如果usedsize等于数组的长度则满
    }

  • 元素出栈

   public int pop(){
         if(isEmpty()){
             throw new StackEmptyException("此时栈为空");
         }
       //先将usedsize--再返回
         return elem[--usedsize];
   }

  • 判空实现

  public boolean isEmpty(){
          return usedsize == 0;
  }
  //自定义异常
  public class StackEmptyException extends RuntimeException{
      public StackEmptyException() {
      }
      public StackEmptyException(String message) {
          super(message);
      }
  }

  • 获取栈顶元素（仅获取不改变位置）

  public int peek(){
         if(isEmpty()){
             throw new StackEmptyException("此时栈为空");
         }
         return elem[usedsize-1];
  }

  • 测试

  public class TestStack {
      public static void main(String[] args) {
          MyStack stack = new MyStack();
          stack.push(1);
          stack.push(2);
          stack.push(3);
          stack.push(4);
          stack.push(5);
          stack.push(6);
          System.out.println(stack.peek());
          System.out.println(stack.pop());
          System.out.println(stack.pop());
      }
  }

  

二、 栈的应用

• 改变元素的序列

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

根据栈先进后出的性质，结合题目中进栈的过程中也可以出栈，如A选项：1进1出,2进3进4进，4出3出2出即符合题意，同理C选项，1进2进3进3出之后不可能直接出1，故C选项不可能实现。

一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）

A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

先进后出，依次入栈，依次出栈，故B选项合理