Java数据结构-栈的实现

         嘻嘻,今天博主终于要更新栈的知识了,上次结束说要更新要是上一次,所以这次咱就把栈的实现的更新带来了,嗯~ o(*￣▽￣*)o小伙伴可能会问,栈能干什么啊,在Java中栈不是有对应的类吗....

         栈能够实现逆波兰计算机,中缀表达式转后缀表达式,还有普通中缀计算机等.....

         话不多说,我们就从一下几个方面开始吧

        栈的概念 ???? 栈的实现思路 ???? 栈的代码实现与分析 ???? 结论 

        如果喜欢作者的话,戳这

        往期精彩:
        普通队列与环形队列

1.  栈是一个先进后出,后进先出的有序列表
2.  在栈中添加元素和删除元素都在一端执行,是一个特殊的线性表
3.  插入元素或删除元素的一端是活跃的一端,被称为栈顶
4.  另一端不活跃,被称为栈底
5.  常用术语:压栈=入栈=push 出栈=弹栈=pop

•  我们需要创建一个数组去模拟栈
•  定义一个栈顶变量top,用于指向栈顶
•  定义压栈弹栈等方法

• 创建一个数组及其变量模拟栈 

    private int maxSize;     private int top;     private Object[] stack;      public ArraysStack(int maxSize) {         this.maxSize = maxSize;         this.top = -1;         stack = new Object[maxSize];     }

 代码分析:

•  maxSize是栈的最大容量,在调用构造方法的时候可以自行指定
•  top用于指向栈顶的变量,应该被初始化为-1
•  这里选用了Object[]数组,目的是什么都可以放进去

图解: 

•  创造两个方法,分别判断是否已满或已空
  

public boolean isFull() {         return top == maxSize - 1;     } public boolean isEmpty() {         return top == -1;     }

 代码分析: 

图解: 

•  创建一个压栈和弹栈的方法

public void push(E element) {         if(isFull()) {             System.out.println("栈已满,无法压栈");             return;         }         stack[++top] = element;     } public E pop() throws Exception{         if(isEmpty()) {             throw new Exception("栈已空,无法弹栈");         }         return (E)stack[top--];     }

  代码分析: 

• 加入元素和取出元素之前,要分别分析一下栈是否为空,或是否为满,要有校验意识
• 因为top初始化为-1,所以添加元素的时候应该先要自增,再添加
• 因为top指向栈顶元素,所以取出元素时,先取出,栈顶top变量再自减 

 图解: 

•  创建一个遍历的方法

public void print() {         if(isEmpty()){             System.out.println("栈已空,无法输出");             return;         }         for (int i = top; i >= 0; i--) {             System.out.println("stack[" + i + "] = " + stack[i]);         }     }

   代码分析: 

1. 从栈的定义得知,先拿出来的是栈顶元素,所以应该从top开始,到0结束  

 完整代码:

package datastructure.chapter02.stack.instance;  /**  *  * @param <E> 指定栈存储的元素  */ public class ArraysStack<E> {     private int maxSize;     private int top;     private Object[] stack;      /**      * 栈(数组实现)的构造方法      * @param maxSize 栈空间的最大值      */     public ArraysStack(int maxSize) {         this.maxSize = maxSize;         this.top = -1;         stack = new Object[maxSize];     }      /**      *  判断栈是否为满      * @return 若返回值为true,则栈已满,否则为false      */     public boolean isFull() {         return top == maxSize - 1;     }      /**      *  判断栈是否为空      * @return 若返回值为true,则栈已空,否则为false      */     public boolean isEmpty() {         return top == -1;     }      /**      * @param element 压入栈的数据      */     public void push(E element) {         if(isFull()) {             System.out.println("栈已满,无法压栈");             return;         }         stack[++top] = element;     }      /**      *      * @return 返回栈顶数据      * @throws Exception 空栈异常      */     public E pop() throws Exception{         if(isEmpty()) {             throw new Exception("栈已空,无法弹栈");         }         return (E)stack[top--];     }      /**      * 输出栈      */     public void print() {         if(isEmpty()){             System.out.println("栈已空,无法输出");             return;         }         for (int i = top; i >= 0; i--) {             System.out.println("stack[" + i + "] = " + stack[i]);         }     } } 

        栈的知识点简单又重要,代码不多,理解起来也不难,我来总结一下重要的几点:

        栈顶top的初始化赋值

        栈的压栈和弹栈的方法

        ????下一站:双向链表!!!