数据结构之堆栈（stack）

栈简介

• 栈(Stack)是一种插入删除操作都只能在一个位置上进行,这个位- 置位于表的末端,叫做栈顶(Top)；
• 对栈的基本操作有push和pop,表示进栈和出栈.也就相当于插入和删除操作；
• 栈结构又叫做LIFO(后进先出)表.归根结底是一个表结构,因此任何能够实现表结构的方法都能实现栈；
• 在java语言中,ArrayList和LinkedList都支持栈操作,栈操作都是常数时间的操作,栈的实现方式一般有两种,一种是使用顺序存储的方式,即使用数组来实现,用ArrayList可以轻易实现栈结构,也可以自己使用数组来实现,一会下面我就用数组来实现栈,第二种是使用链式存储实现,即可以使用LinkedList来实现.
  基于数组实现的栈

/*
 * 后进先出（LIFO）或先进后出
 * 方法：
 * 1.进栈 push()
 * 2.出栈 pop()
 * 3. 获取栈顶元素 peek()
 * 4. 栈的大小 size
 * 5. 扩容 
 * 使用泛型，以便栈中能够存储我们想要的数据
 * 基于数组的栈实现
 */
public class MyStack<E> {
    private Object[] stack;
   /*栈中元素的个数,这里没有对size1进行初始化，
    是因为size是类成员变量，程序在实例化类的时
    候会把size初始化为默认值0
    */
    private int size;         
    public MyStack() {
        stack=new Object[10];     //初始长度为10
    }
//  判断栈是都为空
    public boolean isEmpty() {
        return size==0;
    }
//  返回栈顶元素
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        return (E) stack[size-1];
    }
    public E pop() {
        E e = peek();   //获取栈顶元素
        if(size>0) {
            stack[size-1]=null;   //将出栈后的位置置为空
            size--;   //将栈中元素减一
        }
        return e;  //返回栈顶元素
    }
//   检测栈是否满，满的话需要扩容
    private void ensureCapacity(int size) {
        int len = stack.length;
        if(size>len) {
            int newLen= len+10;       //每次扩容增10
            stack = Arrays.copyOf(stack, newLen);
        }
    }
    
    public E push(E e) {
        ensureCapacity(size+1);    //先进行扩容检测
        stack[size++]=e;         //把元素加进数组最后末尾，并将元素个数size加1
        return e;         //返回该元素
    }
    
    public void printStack() {
        System.out.println("start print stack....");
        for(int index=0;index<size;index++) {
            System.out.println(stack[index]);
        }
        System.out.println("finish!");
    }
    
//  测试
    public static void main(String[] args) {
        MyStack<String> myStack = new MyStack<String>();
        
        myStack.push("as");
        myStack.push("c");
        myStack.push("d");
        
        System.out.println(myStack.pop());
        myStack.printStack();
    }
}