栈的图文解析

41次阅读

共计 2601 个字符,预计需要花费 7 分钟才能阅读完成。

栈的介绍
栈(stack),是一种线性存储结构,它有以下几个特点:
(01) 栈中数据是按照 ” 后进先出(LIFO, Last In First Out)” 方式进出栈的。
(02) 向栈中添加 / 删除数据时,只能从栈顶进行操作。
栈通常包括的三种操作:push、peek、pop。
push — 向栈中添加元素。
peek — 返回栈顶元素。
pop — 返回并删除栈顶元素的操作。

  1. 栈的示意图

栈中的数据依次是 30 –> 20 –> 10

  1. 出栈

出栈前:栈顶元素是 30。此时,栈中的元素依次是 30 –> 20 –> 10
出栈后:30 出栈之后,栈顶元素变成 20。此时,栈中的元素依次是 20 –> 10

  1. 入栈

入栈前:栈顶元素是 20。此时,栈中的元素依次是 20 –> 10
入栈后:40 入栈之后,栈顶元素变成 40。此时,栈中的元素依次是 40 –> 20 –> 10
栈的 java 实现
JDK 包中也提供了 ” 栈 ” 的实现,它就是集合框架中的 Stack 类。
本部分给出 2 种 Java 实现
Java 实现一:数组实现的栈,能存储任意类型的数据。
Java 实现二:Java 的 Collection 集合 中自带的 ” 栈 ”(stack) 的示例。

  1. Java 实现一:数组实现的栈,能存储任意类型的数据

[Java] 纯文本查看 复制代码
?

/align/**

  • Java : 数组实现的栈,能存储任意类型的数据

*/
import java.lang.reflect.Array;

public class GeneralArrayStack<T> {

private static final int DEFAULT_SIZE = 12;
private T[] mArray;
private int count;

public GeneralArrayStack(Class<T> type) {this(type, DEFAULT_SIZE);
}

public GeneralArrayStack(Class<T> type, int size) {// 不能直接使用 mArray = new T[DEFAULT_SIZE];
    mArray = (T[]) Array.newInstance(type, size);
    count = 0;
}

// 将 val 添加到栈中
public void push(T val) {mArray[count++] = val;
}

// 返回“栈顶元素值”public T peek() {return mArray[count-1];
}

// 返回“栈顶元素值”,并删除“栈顶元素”public T pop() {T ret = mArray[count-1];
    count--;
    return ret;
}

// 返回“栈”的大小
public int size() {return count;}

// 返回“栈”是否为空
public boolean isEmpty() {return size()==0;
}

// 打印“栈”public void PrintArrayStack() {if (isEmpty()) {System.out.printf("stack is Empty\n");
    }

    System.out.printf("stack size()=%d\n", size());

    int i=size()-1;
    while (i>=0) {System.out.println(mArray[i]);
       [/i] i--;
    }
}

public static void main(String[] args) {
    String tmp;
    GeneralArrayStack<String> astack = new GeneralArrayStack<String>(String.class);

    // 将 10, 20, 30 依次推入栈中
    astack.push("10");
    astack.push("20");
    astack.push("30");

    // 将“栈顶元素”赋值给 tmp,并删除“栈顶元素”tmp = astack.pop();
    System.out.println("tmp="+tmp);

    // 只将“栈顶”赋值给 tmp,不删除该元素.
    tmp = astack.peek();
    System.out.println("tmp="+tmp);

    astack.push("40");
    astack.PrintArrayStack();    // 打印栈}

}
运行结果
[Plain Text] 纯文本查看 复制代码
?

/color/alignfont=verdana, arial, helvetica, sans-seriftmp=30
tmp=20
stack size()=3
40
20
10
结果说明:GeneralArrayStack 是通过数组实现的栈,而且 GeneralArrayStack 中使用到了泛型。

  1. Java 实现二:Java 的 Collection 集合 中自带的 ” 栈 ”(stack)的示例

[Java] 纯文本查看 复制代码
?

import java.util.Stack;

/**

  • Java : java 集合包中的 Stack 的演示程序

*/
public class StackTest {

public static void main(String[] args) {
    int tmp=0;
    Stack<Integer> astack = new Stack<Integer>();

    // 将 10, 20, 30 依次推入栈中
    astack.push(10);
    astack.push(20);
    astack.push(30);

    // 将“栈顶元素”赋值给 tmp,并删除“栈顶元素”tmp = astack.pop();
    //System.out.printf("tmp=%d\n", tmp);

    // 只将“栈顶”赋值给 tmp,不删除该元素.
    tmp = (int)astack.peek();
    //System.out.printf("tmp=%d\n", tmp);

    astack.push(40);
    while(!astack.empty()) {tmp = (int)astack.pop();
        System.out.printf("tmp=%d\n", tmp);
    }
}

}
运行结果
[Plain Text] 纯文本查看 复制代码
?
1
2
3
/color/alignfont=verdana, arial, helvetica, sans-seriftmp=40
tmp=20
tmp=10/color/alignfont=verdana, arial, helvetica, sans-serif

参考
http://www.cnblogs.com/skywan…

正文完
 0