栈和队列

栈和队列是程序中最常使用的数据结构，它们的实现最常用机制是基于数组，相对于其它数据结构而言是最简单也是最基础的数据结构。

栈(Stack)

一种特殊的线性表，插入和删除在同一端，该端叫栈顶（top），另一端叫栈底（bottom）。后进先出（LIFO），故也称为后进先出的线性表。

public class StackApp {

    public static void main(String[] args) {
        StackX stackX = new StackX(10);

        System.out.print("进栈：");
        for (int i = 0; i < 12 ; i++) {
            if(!stackX.isFull()){
                System.out.print(i + " ");
                stackX.push(i);
            }
        }

        System.out.println("\n栈顶数据项：" + stackX.peek());
        System.out.print("\n出栈：");
        for (int j = 0; j < 10 ; j++) {
            if(!stackX.isEmpty()){
                System.out.print(stackX.pop() + " ");
            }
        }
    }
}


// 定义栈结构
class StackX{
    private int maxSize;
    private int[] data;
    private int top;

    public StackX(int size){
        maxSize = size;
        data = new int[maxSize];
        top = -1;
    }

    public void push(int p){
        data[++top] = p;
    }

    public int pop(){
        return data[top--];
    }

    public int peek(){
        return data[top];
    }

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

    public boolean isFull(){
        return (top == maxSize -1);
    }

}

队列(Queue)

一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。先进先出(FIFO)，故又称先进先出的线性表。

队列可以实现为循环队列，将数组下标从数组末端绕回到数组的开始位置。

public class QueueApp {

    public static void main(String[] args) {

        Queue queue = new Queue(10);

        System.out.print("插入队列：");
        for (int i = 0; i < 10; i++) {
            if (!queue.isFull()){
                System.out.print(i + " ");
                queue.insert(i);
            }
        }

        System.out.println("\n队列长度：" + queue.size());
        System.out.println("队列头元素： " + queue.peekFront());

        System.out.print("\n移除队列：");
        while (!queue.isEmpty()){
            System.out.print(queue.remove() + " ");
        }

        System.out.println("\n队列长度：" + queue.size());
    }
}


class Queue{
    private int maxSize;
    private int[] data;
    private int front;
    private int rear;
    private int index;

    public Queue(int size){
        maxSize = size;
        data = new int[maxSize];
        front = 0;
        rear = -1;
        index = 0;
    }

    public void insert(int value){
        if(rear == maxSize -1){
            rear = -1;
        }
        data[++rear] = value; // 尾位置填数据
        index++;
    }

    public int remove(){
        int temp = data[front++]; // 头位置取数据
        if(front == maxSize){
            front = 0;
        }

        index--;
        return temp;
    }

    public int peekFront(){
        return data[front];
    }

    public boolean isEmpty(){
        return (index == 0);
    }

    public boolean isFull(){
        return (index == maxSize);

    }

    public int size(){
        return index;
    }
}

算术表达式

算术表达式最常用的是中缀表达式，另外还有前缀表达式和后缀表达式。和以后要讲的树的中序，前序和后序遍历差不多是一个概念。下表给出几个中缀表达式对应的后缀表达式的例子，举一反三，就能推广到其他情况了。

中缀表达式	后缀表达式
A+B-C	AB+C-
A*B/C	AB*C/
A+B*C	ABC*+
A*(B+C)	ABC+*
(A+B)*(C-D)	AB+CD-*

算术表达式求值通常是先装换成后缀表达式，然后在求后缀表达式的值，在这个过程中栈都是很好用的工具。