您的位置: 首页  >  文章  >  栈的图文解析

栈的图文解析

分类: 文章 • 2024-02-21 13:38:04

栈的介绍

栈（stack），是一种线性存储结构，它有以下几个特点：
(01) 栈中数据是按照"后进先出（LIFO, Last In First Out）"方式进出栈的。
(02) 向栈中添加/删除数据时，只能从栈顶进行操作。
栈通常包括的三种操作：push、peek、pop。
push -- 向栈中添加元素。
peek -- 返回栈顶元素。
pop  -- 返回并删除栈顶元素的操作。
1. 栈的示意图
栈的图文解析
栈中的数据依次是 30 --> 20 --> 10
2. 出栈
栈的图文解析
出栈前：栈顶元素是30。此时，栈中的元素依次是 30 --> 20 --> 10
出栈后：30出栈之后，栈顶元素变成20。此时，栈中的元素依次是 20 --> 10
3. 入栈
栈的图文解析
入栈前：栈顶元素是20。此时，栈中的元素依次是 20 --> 10
入栈后：40入栈之后，栈顶元素变成40。此时，栈中的元素依次是 40 --> 20 --> 10
栈的java实现
JDK包中也提供了"栈"的实现，它就是集合框架中的Stack类。
本部分给出2种Java实现
Java实现一：数组实现的栈，能存储任意类型的数据。
Java实现二：Java的 Collection集合 中自带的"栈"(stack)的示例。
1. Java实现一：数组实现的栈，能存储任意类型的数据
[Java] 纯文本查看 复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
[/align][align=left]/**
 * 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] 纯文本查看 复制代码
1
2
3
4
5
6
[/color][/font][/align][align=left][font=verdana, arial, helvetica, sans-serif][color=#000000]tmp=30
tmp=20
stack size()=3
40
20
10
结果说明：GeneralArrayStack是通过数组实现的栈，而且GeneralArrayStack中使用到了泛型。
2. Java实现二：Java的 Collection集合 中自带的"栈"(stack)的示例
[Java] 纯文本查看 复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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][/font][/align][align=left][font=verdana, arial, helvetica, sans-serif][color=#000000]tmp=40
tmp=20
tmp=10[/color][/font][/align][align=left][font=verdana, arial, helvetica, sans-serif][color=#000000]
 
参考
http://www.cnblogs.com/skywang12345/p/3562239.html

相关推荐