栈

简介

数组、链表、树等数据结构适用于存储数据库应用中的数据记录，它们常常用于记录那些现实世界的对象和活动的数据，便与数据的访问：插入、删除和查找特定数据项

而栈和队列更多的是作为程序员的工具来使用。他们主要作为构思算法的辅助工具，而不是完全的数据存储工具。
栈和队列的访问是受限制的，即在特定时刻只有一个数据项可以被读取或删除

栈和队列是比数组和其他数据结构更加抽象的结构，是站在更高的层面对数据进行组织和维护

栈的主要机制可用数组来实现，也可以用链表来实现。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。

概念

栈只允许访问一个数据项：即最后插入的数据。移除这个数据项后才能访问倒数第二个插入的数据项。它是一种“后进先出”的数据结构。

栈最基本的操作是出栈（Pop）、入栈（Push），还有其他扩展操作，如查看栈顶元素，判断栈是否为空、是否已满，读取栈的大小等

入栈示意图

20150721204449175.jpg

出栈示意图

20141207093403031.jpg

代码实现栈(数组版本)实例

public class Stack {
    private int[] ints;
    private int top;
    private int maxSize;

    public Stack(int maxSize) {
        ints = new int[maxSize];
        top = -1;
        this.maxSize = maxSize;
    }

    //入栈，同时，栈顶元素的下标加一
    public void push(int elem){
        ints[++top] = elem;
    }

    //出栈，删除栈顶元素，同时，栈顶元素的下标减一
    public int pop() throws Exception {
        if (isEmpty()){
            throw new Exception("栈为空");
        }
        return ints[top--];
    }

    //查看栈顶元素，但不删除
    public int peek() throws Exception {
        if (isEmpty()){
            throw new Exception("栈为空");
        }
        return ints[top];
    }

    //判空
    public boolean isEmpty(){
        return top == -1;
    }
    //判满
    public boolean isFull(){
        return top == maxSize;
    }

}
//测试
    public static void main(String[] args) throws Exception {
        Stack stack = new Stack(4);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.print(stack.pop() + "\n");
        System.out.print(stack.peek() + "\n");
        stack.push(5);
        System.out.print(stack.pop() + "\n");
    }

栈通常用于解析某种类型的文本串。通常，文本串是用计算机语言写的代码行，而解析它们的程序就是编译器。