你的位置:首页 > Java教程

[Java教程]数据结构—栈


先说什么是栈:

      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;    res.nextNode = null;    top = top.nextNode;    return res.obj;  }  public boolean isEmpty() {    return top == null;  }}

 再给个测试类:

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、有没有栈的官方标准定义?

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

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

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

 后期把这几个问题搞清楚之后会更新此文章。