首页 > 代码库 > 数据结构—栈

数据结构—栈

先说什么是栈

      1、后进先出  2、对数据的所有操作只能在固定的一端进行操作,不能再中间或者另一端对数据进行操作。

 符合以上两点的 存储数据的类(对象) 叫做栈。

  需要说明的是:栈是符合以上两个特性的所有的数据结构都可以叫做栈,无论其用什么基本容器实现的。

再说如何实现:

      可以使用数组或者链表实现栈,在用链表实现的时候要屏蔽掉链表的一些特性:在链表中间对数据进行操作等。

 

看一下jdk中自带的栈:

    注意Stack(图一)中:  Stack继承自Vactor     Stack自己的方法种类

    Vector(图二)中 : Vector中的方法

   Stack继承自Vactor,所以Stack是可以调用父类中的set(int index, E element),insertElementAt(E obj, int index)等操作的,这样的话就与栈的特性有矛盾,我对这一点还没有理解透彻,是不是第二条特性需要去掉?希望有朋友看到之后能够指教指教。感谢!

 

图一:Stack.java

    技术分享

图二:Vector.java

           技术分享

既然是jdk自带的有栈,我们还了解他干什么?

  在一些特殊情况下,需要根据实际情况封装自己的栈。

 

下面给两个自己做的示例,一个使用数组实现的栈,一个是用链表实现的栈。

数组实现:

技术分享

package com.datastructure;/**
 * @author Perkins .Zhu 
 * @date:2016年7月17日 上午9:13:01
 * @version :1.1
 * 
 */public class ArrayStack implements Stack {    private int maxSize;    private Object[] myStack;    private int top = -1;// 指向最后入栈的对象
    private final int DEFAULT_SIZE = 100;    private boolean canExpendSize = true;// 是否允许扩容
    private int multiple = 2;// 扩容倍数

    public ArrayStack() {
        myStack = new Object[DEFAULT_SIZE];
    }    public ArrayStack(int size, boolean canExpendSize) {        if (size < 1) {
            size = DEFAULT_SIZE;
        }
        myStack = new Object[size];        this.canExpendSize = canExpendSize;
    }

    @Override    public void push(Object obj) {        if (top == myStack.length - 1) {            if (canExpendSize) {
                exspandSize();
            } else {
                move();
            }
        }
        myStack[++top] = obj;
    }    // 删除栈底元素,所有元素向后移动一位,top指向 myStack.length-2
    private void move() {        for (int i = 0; i < myStack.length - 1; i++) {
            myStack[i] = myStack[i + 1];
        }
        top = myStack.length - 2;
    }    // 扩容
    private void exspandSize() {
        Object[] temp = new Object[multiple * myStack.length];        for (int i = 0; i < myStack.length; i++) {
            temp[i] = myStack[i];
        }
        top = myStack.length - 1;
        myStack = temp;
    }

    @Override    public Object pop() {        if (top == -1)            return null;        return myStack[top--];
    }

    @Override    public boolean isEmpty() {        return top == -1;
    }

}

技术分享

 

 

链表实现:(只实现了基本功能,可根据实际需要添加参数或者方法)

技术分享

package com.datastructure;import java.util.LinkedList;/**
 * @author Perkins .Zhu 
 * @date:2016年7月17日 下午1:16:26
 * @version :1.1
 * 
 */public class LinkStack implements Stack {    private Node top;    private class Node {        private Object obj;        private Node nextNode;        public Node(Object obj, Node node) {            this.obj = obj;            this.nextNode = node;
        }
    }    public void push(Object obj) {        if (top != null) {
            top = new Node(obj, top);
        } else {
            top = new Node(obj, null);
        }
    }    public Object pop() {
        Node res = top;
     top = top.nextNode;
=   top ==

技术分享

 再给个测试类:

技术分享

package com.datastructure;import org.junit.Test;/**
 * @author Perkins .Zhu 
 * @date:2016年7月17日 上午9:16:50
 * @version :1.1
 * 
 */public class StackTest {

    @Test    public void testArrayStack() {
        ArrayStack stack = new ArrayStack(100, false);        int loop = 0;        while (loop < 150) {
            stack.push(loop++);
        }
        print(stack);
    }    public void print(Object obj) {        if (obj instanceof Stack) {
            Stack stack = (Stack) obj;            while (!stack.isEmpty()) {
                System.out.print(stack.pop() + "  ");
            }
        }
        System.out.println();
    }

    @Test    public void testLinkStack() {
        LinkStack stack = new LinkStack();        int loop = 0;        while (loop < 150) {
            stack.push(loop++);
        }
        print(stack);
    }
}

技术分享

 

遇到的几个问题:

    1、有没有栈的官方标准定义?

      只要符合后进先出(last in first off,LIFO)的数据结构都是栈。

    2、泛型 T和object有什么区别,接收参数的时候有什么不同的?? 

      a:约束了此容器中只能存储一种类型数据。

      b:在从容器中取出对象的时候不需要进行类型强转,容器已经知道(因为在new 容器的时候在<>中已经制定了存储对象类型)你存储的是什么类型,但是object需要进行强转。

    3、栈要不要实现其删除、插入、查找操作?

      栈不需要这些方法,这些方法的存在没意义。画蛇添足。

    4、除了使用数组和链表还有没有其他栈实现方式?

      应该没有了吧?


数据结构—栈