栈Stack JAVA实现

栈

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

• (1)通常称插入、删除的这一端为栈顶 （Top），另一端称为栈底 （Bottom）。
• (2)当表中没有元素时称为空栈。
• (3)栈为后进先出（Last In First Out）的线性表，简称为 LIFO 表。

栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"
最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，
要到最后才能删除。

2、栈的基本运算

• （1） 判断栈是否为空
  boolean isEmpty();
• （2）清空栈
  void clear();
• （3）栈的长度
  int length();
• （4）数据入栈
  boolean push(T data);
• （5）数据出栈 ，栈中删除
  T pop();
• （6）数据出栈 ,栈中不删除
  T peek();

接口

package com.ghg.data_structure.stack;

public interface MyStack<T> {

    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty();
    
    
    /**
     * 获取长度
     * @return
     */
    public int length();
    
    
    /**
     * 清空栈
     */
    public void clear();
    
    
    /**
     * 入栈
     * @param data
     * @return
     */
    public boolean push(T data);
    
    /**
     * 出栈,移除最后一个
     * @return
     */
    public T pop();
    
    
    /**
     * 出栈不移除
     * @return
     */
    public T peek();
}

数组实现

package com.ghg.data_structure.stack.imp;

import com.ghg.data_structure.stack.MyStack;

public class MyArrayStack<T> implements MyStack<T> {
    
    private Object [] objs= new Object[16];
    private int size;

    public boolean isEmpty() {
        return size==0;
    }

    public int length() {
        return size;
    }

    public void clear() {
        
        for(int i = 0; i <objs.length ; i++){
            objs[i]=null;
            size--;
        }
        
    }

    public boolean push(T data) {
        
        if(size==objs.length-1){
            Object [] temp = new Object[objs.length*2];
            
            for(int i = 0; i <objs.length ; i++){
                temp[i]=objs[i];
            }
            objs=temp;
        }
        
        
        objs[size++]=data;
        return true;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        return size==0?null:(T) objs[(size--)-1];
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        return size==0?null:(T) objs[size-1];
    }

}

列表实现

package com.ghg.data_structure.stack.imp;

import com.ghg.data_structure.stack.MyStack;
import com.sun.org.apache.bcel.internal.generic.ReturnaddressType;

public class MyListStack<T> implements MyStack<T> {

    private int size;
    private Node top;

    public class Node {
        // 数据
        T data;
        // 前一个
        Node pre;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int length() {
        return size;
    }

    public void clear() {

        top = null;
    }

    public boolean push(T data) {
        Node node = new Node();
        node.data = data;

        if (size == 0) {

            top = node;
        } else {

            node.pre=top;
            top=node;
        }
        size++;
        return true;
    }

    public T pop() {
        if (size == 0) {
            return null;
        }
        T data = top.data;
        top = top.pre;
        size--;
        return data;
    }

    public T peek() {
        if (size == 0) {
            return null;
        }
        T data = top.data;
        return data;
    }

}

测试

package com.ghg.data_structure.stack;

import com.ghg.data_structure.stack.imp.MyArrayStack;
import com.ghg.data_structure.stack.imp.MyListStack;

public class Test1 {

    public static void main(String[] args) {

        MyStack<Integer> myStack1 = new MyListStack<Integer>();
        MyStack<Integer> myStack2 = new MyArrayStack<Integer>();

        for (int i = 0; i < 50; i++) {
            myStack1.push(i);
            myStack2.push(i);
        }
        System.out.println(myStack1.length());
        System.out.println(myStack2.length());

        System.out.println("\n#########list 链表 peek#####");
        for (int i = 0; i < 50; i++) {
            System.out.print(myStack1.peek() + "\t");

        }
        System.out.println("\n#########array 数组 peek#####");

        for (int i = 0; i < 50; i++) {

            System.out.print(myStack2.peek() + "\t");

        }
        System.out.println("\n#########list 链表#####");
        for (int i = 0; i < 50; i++) {
            System.out.print(myStack1.pop() + "\t");

        }
        System.out.println("\n#########array 数组#####");
        for (int i = 0; i < 50; i++) {

            System.out.print(myStack2.pop() + "\t");

        }
    }

}

结果

50
50

#########list 链表 peek#####
49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  
#########array 数组 peek#####
49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  49  
#########list 链表#####
49  48  47  46  45  44  43  42  41  40  39  38  37  36  35  34  33  32  31  30  29  28  27  26  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0   
#########array 数组#####
49  48  47  46  45  44  43  42  41  40  39  38  37  36  35  34  33  32  31  30  29  28  27  26  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0