• 如果你学完链表的编写,今天的内容那就很搜一贼了,哈哈,如果你没有学过链表的编写,可以移步到我的链表学习的文章哈~(今天的内容很简单)

• 栈是一种线性结构,如果从数据的存储结构来进行进步不划分,栈结构可以分为

  • 顺序栈:即使用一块地址连续的内存单元依次保存栈内的数据
  • 线性栈:即使用链表形式保存栈内各个元素的值
• 栈结构图

• 如上,栈只能在一段进行操作,这一端称为栈顶,而反方向是栈底,栈结构遵循后入先出LIFO(last in first out)的原则处理数据节点的
• 如上现实生活中的图,我们只能从罐子顶部取出食物,而我们首先放入罐内的我们只能最后拿出来

• 在栈结构中,只有栈顶元素可以访问,一般栈结构的基本操作有两个

  • 入栈push:将数据放到栈顶的操作
  • 出栈pop:将栈顶元素取出的操作

顺序栈

• 顺序栈是有初始化大小的,这也是内部数组的大小,顺序栈有一个标识,即栈顶的标识,他是一个int值,只有有元素入栈就加一,出栈就减一,所以这个标识在等于0的情况下代表是空栈

  public class MyStack<T> {
      private int top ;
      private final Object[] elementData;
      private final int MAX_SIZE;
      public MyStack() {
          this.MAX_SIZE = 5;
          elementData = new Object[MAX_SIZE];
      }
      public MyStack(int max_size) {
          this.MAX_SIZE = max_size;
          elementData = new Object[MAX_SIZE];
      }
      //入栈
      public void push (T element){
          if (top == MAX_SIZE){
              throw new RuntimeException("栈已满");
          }
          elementData[top] = element;
          top ++;
      }
      //出栈
      public T pop (){
          if (top == 0){
              return null;
          }
          top --;
          return (T) elementData[top];
      }
      //peek
      public T peek(){
          if (top == 0){
              return null;
          }
          return (T) elementData[top];
      }
      @Override
      public String toString() {
          return Arrays.toString(elementData);
      }
  }

• 程序编写还是很简单的,但是上面程序有一个诟病,就是没有达到函数式,就是说,上面直接返回元素的引用,我感觉应该是拷贝一下要返回的对象,避免栈内数据在外面通过引用修改掉,因为这样可能会引发其他引用此栈数据的程序出错

• 测试

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

• 结果

  [1, 2, 3, 4, 5]
  5
  4
  3
  3
  2
  1

链式栈

• 如果是链式,那么就无需考虑栈大小了,它可以通过堆内存,来进行动态的扩充栈大小,如果你清楚链表怎么写,那么这个也就信手拈来了,好了下面就是代码实现了

  public class MyLinkedStack<T> {
  
      private int top;
      private Node<T> head;
      public MyLinkedStack() {
          this.head = new Node<>(null,null);
      }
      private class Node<T>{
          private Node<T> next;
          private T element;
          public Node(Node<T> next, T element) {
              this.next = next;
              this.element = element;
          }
  
          @Override
          public String toString() {
              return String.valueOf(element);
          }
      }
      //入栈
      public void push(T element){
          Node<T> next = head.next;
          head.next = new Node<>(next,element);
          top ++;
      }
      //出栈
      public T pop(){
          Node<T> next = head.next;
          head.next = next.next;
          top --;
          return (T) next;
      }
      //peek
      public T peek(){
          return (T) head.next;
      }
  
      @Override
      public String toString() {
          StringBuilder builder = new StringBuilder();
          for (Node<T> node = head.next; node != null ; node = node.next){
              builder.append(node.element+",");
          }
          return builder.toString();
      }
  }

• 测试

  public static void main(String[] args) {
      MyLinkedStack<Integer> stack = new MyLinkedStack<>();
      for (int i = 0; i < 10; i++) {
          stack.push(i);
      }
      System.out.println(stack);
      System.out.println(stack.pop());
      System.out.println(stack.pop());
      System.out.println(stack);
      System.out.println(stack.peek());
      System.out.println(stack.peek());
      System.out.println(stack);
  }

• 结果

  9,8,7,6,5,4,3,2,1,0,
  9
  8
  7,6,5,4,3,2,1,0,
  7
  7
  7,6,5,4,3,2,1,0,