JAVA数据结构系列 栈

java数据结构系列之栈

手写栈

1.利用链表做出栈，因为栈的特殊，插入删除操作都是在栈顶进行，链表不用担心栈的长度，所以链表再合适不过了，非常好用，不过它在插入和删除元素的时候，速度比数组栈慢，因为它要维护自己的指针(Next)引用。

package com.rsc.stack;

import java.util.LinkedList;

/**
 * 利用链表实现的栈
 * @author 落雨
 * http://ae6623.cn
 * @param <T>
 */
public class LinkedListStack<T> {
    LinkedList<T> list;

    public LinkedListStack() {
        list = new LinkedList();
    }

    /**
     * 出栈
     *
     * @return
     */
    public T pop() {
        return list.removeLast();
    }

    /**
     * 入栈
     *
     * @param t
     */
    public void push(T t) {
        list.add(t);
    }

    public T getTop() {
        return list.getLast();
    }

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

    public int getSize() {
        return list.size();
    }

    public static void main(String[] args) {
        LinkedListStack<String> ls = new LinkedListStack<String>();
        System.out.println(ls.getSize());
        ls.push("2");
        ls.push("我");
        ls.push("你");
        ls.push("他");
        ls.push("1");
        ls.push("3");
        ls.push("5");
        System.out.println(ls.getSize());
        System.out.println(ls.getTop());

        ls.pop();
        System.out.println(ls.getSize());
        System.out.println(ls.getTop());

        ls.push("嘿嘿");
        System.out.println(ls.getSize());
        System.out.println(ls.getTop());

    }

}

打印结果:

0
7
5
6
3
7
嘿嘿

2.利用数组实现的栈，好处是速度快，坏处是要考虑数组的扩容，既然要扩容，肯定就涉及数组元素的拷贝，一对一的一个萝卜一个坑的塞过去，相对链表来说，它的插入和删除就比链表要快，因为它不用维护指针(Next),不懂这个指针next的同学，自行脑补链表的实现方式，下节会说到链表的实现。

package com.rsc.stack;

import java.util.Arrays;

/**
 * 利用数组实现的栈的数据结构
 *
 * @author
 * 落雨 2015年6月5日 http://ae6623.cn
 *
 */
public class ArrayStack {

    public Object[] t;// 存数的数据数组
    int top = 0;// 默认Top为0

    public ArrayStack(int size) {
        t = new Object[size];
    }

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

    public boolean clean() {
        top = 0;
        return true;
    }

    public void pop() {
        if (top > 0) {
            t[--top] = null;
        }
        System.out.println(getTop());
    }

    public void push(Object o) {

        // 检测扩容
        if (top >= t.length) {
            int newCapacity = (t.length * 3) / 2 + 1; // 增加50%+1
            Object[] newObject = new Object[newCapacity];
            int k = 0;
            for (Object i : t) {
                newObject[k++] = i;
            }
            t = newObject;
        }

        t[top++] = o;
        System.out.println(getTop());
    }

    public Object getTop() {
        System.out.println("top:" + top);
        printStack();
        return top <= 0 ? null : "当前栈顶元素:" + t[top - 1];
    }

    public int getSize() {
        return top;
    }

    public void printStack() {
        System.out.println(Arrays.toString(t));
    }

    public static void main(String[] args) {
        ArrayStack as = new ArrayStack(5);

        as.push("1");
        as.push("2");
        as.push("3");
        as.push("4");
        as.push("5");
        as.push("我");
        as.push("6");
        as.push("7");
        as.printStack();
        as.pop();
        as.pop();
        as.pop();
        as.pop();
        as.pop();
        as.pop();
        as.pop();
        as.pop();
        as.pop();

    }
}

打印结果:

top:1
[1, null, null, null, null]
当前栈顶元素:1
top:2
[1, 2, null, null, null]
当前栈顶元素:2
top:3
[1, 2, 3, null, null]
当前栈顶元素:3
top:4
[1, 2, 3, 4, null]
当前栈顶元素:4
top:5
[1, 2, 3, 4, 5]
当前栈顶元素:5
top:6
[1, 2, 3, 4, 5, 我, null, null]
当前栈顶元素:我
top:7
[1, 2, 3, 4, 5, 我, 6, null]
当前栈顶元素:6
top:8
[1, 2, 3, 4, 5, 我, 6, 7]
当前栈顶元素:7
[1, 2, 3, 4, 5, 我, 6, 7]
top:7
[1, 2, 3, 4, 5, 我, 6, null]
当前栈顶元素:6
top:6
[1, 2, 3, 4, 5, 我, null, null]
当前栈顶元素:我
top:5
[1, 2, 3, 4, 5, null, null, null]
当前栈顶元素:5
top:4
[1, 2, 3, 4, null, null, null, null]
当前栈顶元素:4
top:3
[1, 2, 3, null, null, null, null, null]
当前栈顶元素:3
top:2
[1, 2, null, null, null, null, null, null]
当前栈顶元素:2
top:1
[1, null, null, null, null, null, null, null]
当前栈顶元素:1
top:0
[null, null, null, null, null, null, null, null]
null
top:0
[null, null, null, null, null, null, null, null]
null