4.2 栈和队

一、栈

栈（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

4.栈的Java实现

JDK包中也提供了"栈"的实现，它就是集合框架中的Stack类。 本部分使用数组实现栈，能存储任意类型的数据。

/**
 * Java : 数组实现的栈，能存储任意类型的数据
 *
 * @author skywang
 * @date 2013/11/07
 */
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--;
        }
    }
}

二、队列

队列（Queue），是一种线性存储结构。它有以下几个特点： (1) 队列中数据是按照"先进先出（FIFO, First-In-First-Out）"方式进出队列的。 (2) 队列只允许在"队首"进行删除操作，而在"队尾"进行插入操作。 队列通常包括的两种操作：入队列 和 出队列。

1.队列的示意图

队列中有10，20，30共3个数据。

2.出队列

出队列前：队首是10，队尾是30。

出队列后：出队列(队首)之后。队首是20，队尾是30。

3.入队列

入队列前：队首是20，队尾是30。

入队列后：40入队列(队尾)之后。队首是20，队尾是40。

4.队列的Java实现

JDK中的Queue接口就是"队列"，它的实现类也都是队列，用的最多的是LinkedList。本部分使用数组实现队列，能存储任意类型的数据。

/**
 * Java : 数组实现“队列”，只能存储int数据。
 *
 * @author skywang
 * @date 2013/11/07
 */
public class ArrayQueue {

    private int[] mArray;
    private int mCount;

    public ArrayQueue(int sz) {
        mArray = new int[sz];
        mCount = 0;
    }

    // 将val添加到队列的末尾
    public void add(int val) {
        mArray[mCount++] = val;
    }

    // 返回“队列开头元素”
    public int front() {
        return mArray[0];
    }

    // 返回“队首元素值”，并删除“队首元素”
    public int pop() {
        int ret = mArray[0];
        mCount--;
        for (int i=1; i<=mCount; i++)
            mArray[i-1] = mArray[i];
        return ret;
    }

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

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