栈和队列

目录

1、引言
2、栈
3、队列

引言

栈和队列都是动态集合，可以理解为线性表或线性表实现的数据结构。它可以由数组实现，也可以由链表实现。

和数组链表等不一样的是，栈、队列添加、删除数据的位置都是预先设定的。在栈中，被删除的是最近被插入的元素，栈实现的是一种先进后出的策略。而队列中，被删去的总是在集合中存在时间最长的元素，队列实现的是一种先进先出的策略。

栈和队列是非常有用的数据结构，在计算机中很多的地方使用了栈、队列的思想。函数执行的压栈及出栈，消息队列的使用等等。本文最后将介绍栈和队列的常见使用场景，递归转化。

栈

栈的常用操作为以下四种

• push，在栈顶插入一个元素
• pop，弹出栈顶的元素
• peek，查看栈顶元素
• getSize，查看栈内元素的个数

本文中栈由数组实现。

由于入栈和出栈的操作都只集中在栈顶，所以栈实现中，必须定义变量mTop，用于标记当前栈顶位置。

插入操作，在mTop位置上插入新元素，mTop自增即可。

出栈操作，返回mTop自减后的位置的元素。

获取栈内元素个数，即为mTop值大小。

private int mTop = 0;
private static final int MAX = 20;
private Object[] mArray = null;

public DemoStack(){
    mTop = 0;
    mArray = new Object[MAX];
}

public int getSize(){
    return mTop;
}

public boolean push(T e){
    if (mTop < MAX) {
        mArray[mTop] = e;
        mTop ++;
        return true;
    }
    System.out.println("stack is full");
    return false;
}

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

public T pop(){
    if (mTop == 0) {
        System.out.println("stack is empty");
        return null;
    }
    T e = (T) mArray[--mTop];
    return e;
}

public T peek(){
    int index = mTop - 1;
    return (T) mArray[index];
}

栈的实现比较简单，但栈的用处非常大。

在java虚拟机中，函数的调用，会生成一个个函数调用栈，等函数执行完毕，得到函数的返回值，出栈，回到之前调用函数的地方。递归能简便解决非常多的问题，但递归有个最大的问题就是执行效率不高，因为函数调用的次数太多了。结合java虚拟机的函数调用思想，可否优化递归呢？因为递归本质上是将某一个状态的结果保存在栈中，再计算另外一个状态。如果不用递归，也可以使用栈数据结构来保存部分结果。

栈的使用场景之一，就是递归转化，使用栈保存部分结果，取结果再计算下一个状态的结果。二叉树的遍历分为前序遍历，中序遍历，后序遍历，递归实现非常简单，也可以使用栈将递归转化。

前序遍历非常简单，是三种遍历中转化最容易的一种。

  public void preTraverseByStack(Node root) {
    if (root == null) {
        return;
    }
    DemoStack<Node> stack = new DemoStack<>();
    stack.push(root);
    Node temp = null;
    while (!stack.isEmpty()) {
        temp = stack.pop();
        System.out.print(temp + "   ");
        if (temp.hasRightChild()) {
            stack.push(temp.getRightChild());
        }
        if (temp.hasLeftChild()) {
            stack.push(temp.getLeftChild());
        }
    }
    System.out.println();
}

中序遍历开始有一定困难了，中序遍历必须先遍历左子树，所以需要找到最左最下方的叶子结点。如果栈中元素值为空，则说明此元素的子元素已经被遍历过了或者不需要处理了。

  public void middleTraverseByStack(Node root){
    if (root == null) {
        return;
    }
    DemoStack<Node> stack = new DemoStack<>();
    stack.push(root);
    Node temp = null;
    while (!stack.isEmpty()) {
        while (stack.peek() != null && stack.peek().hasLeftChild()) {
            stack.push(stack.peek().getLeftChild());
        }
        if (stack.peek() == null) {
            stack.pop();
        }
        if (!stack.isEmpty()) {
            temp = stack.pop();
            System.out.print(temp + "   ");
            stack.push(temp.getRightChild());
        }
    }
    System.out.println();
}

后序遍历是三种转化中最难的，它需要先遍历左右子树才行，因为需要使用两个临时变化，记录之前遍历的结点和当前结点。

  public void lastTraverseByStack(Node root){
    if (root == null) {
        return;
    }
    DemoStack<Node> stack = new DemoStack<>();
    stack.push(root);
    Node cur = null;
    Node pre = null;
    while (!stack.isEmpty()) {
        cur = stack.peek();
        if ((cur.getLeftChild() == null && cur.getRightChild() == null)
                || (pre != null && (pre == cur.getLeftChild() || pre == cur.getRightChild()))) {
            System.out.print(cur + "   ");
            stack.pop();
            pre = cur;
        }else {
            if (cur.hasRightChild()) {
                stack.push(cur.getRightChild());
            }
            if (cur.hasLeftChild()) {
                stack.push(cur.getLeftChild());
            }
        }
        
    }
}

栈的使用场景还有很多，例如四则运算等等。在具体场景中，只要采用了合适的数据结构，事半功倍！

队列

队列的常用操作为：

• enqueue，入队，在队列头部插入元素
• dequeue，出队，在队列尾部删除元素
• getSize，获取队列元素个数

因为队列需要在队列头部和尾部进行元素操作，所以需要两个指针，一个指向头部，一个指向尾部。

队列比栈复杂，队列涉及循环问题。如果使用队列装满元素，再删除所有元素，此时再添加新的元素，虽然队列的mTop值已经是最大了，但尾部仍有空间，需要需要在尾部添加元素。导致mTop值会比mTail值小。

private int mTop;
private int mTail;
private static final int MAX = 10;
private Object[] mArray;
private int mLength = 0;

public DemoQueue(){
    mTop = mTail = 0;
    mArray = new Object[MAX];
    mLength = 0;
}

public int getSize(){
    return mLength;
}

public boolean enqueue(T e){
    if (getSize() == MAX) {
        System.out.println("queue is full");
        return false;
    }
    if (mTop == MAX) {
        mTop -= MAX;
    }
    mArray[mTop] = e;
    mTop ++;
    mLength++;
    return true;
}

public T dequeue(){
    if (getSize() == 0) {
        System.out.println("queue is empty");
        return null;
    }
    int index = mTail;
    mTail++;
    if (mTail == MAX) {
        mTail -= MAX;
    }
    mLength--;
    return (T) mArray[index];
}

队列和栈一样是非常重要的数据结构，在日常开发中常常用到消息队列，可能会接到某个需要，不允许漏掉任何一个消息，此时就可以使用队列完成需求。本例中，使用队列遍历二叉树，且是从上到下从左到右的水平遍历。

  public void traverse(Node root){
    if (root == null) {
        return;
    }
    DemoQueue<Node> queue = new DemoQueue<>();
    queue.enqueue(root);
    Node temp = null;
    while (queue.getSize() > 0) {
        temp = queue.dequeue();
        System.out.print(temp + "   ");
        if (temp.hasLeftChild()) {
            queue.enqueue(temp.getLeftChild());
        }
        if (temp.hasRightChild()) {
            queue.enqueue(temp.getRightChild());
        }
    }
    System.out.println();
}

本文中所有代码均已上传到本人的github空间，欢迎访问。