栈与队列

栈

概念

栈：是限定仅在表尾进行插入和删除操作的线性表。

栈顶(top)：允许插入和删除的一端，即表尾称为栈顶

栈底(bottom):表头称为栈底

栈是LIFO结构，后进先出。

与线性表相比，特殊之处在于

限制了线性表的插入和删除位置，始终在栈顶进行。

所以栈底是固定的，最先进栈的只能在栈底

相关操作

栈的插入操作 —> 进栈（圧栈、入栈）

栈的删除操作 —> 出栈（弹栈）

假设入栈元素从小到大，出栈的每个元素后面比该元素小的元素，应该按从大到小的相对顺序排列

比如数字元素1、2、3依次进栈，

出栈顺序可能是 1、2、3 / 1、3、2 / 2、1、3 / 2、3、1 / 3、2、1

不可能是 3、1、2 的出栈顺序。

抽象数据类型

栈的顺序存储结构

用数组实现

ArrayStack.java

package com.stack;

/**
 * 用数组实现的顺序表
 * 限制操作端，使其成为栈
 */
public class ArrayStack {

    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStackDemo(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

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

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


    public void push(int value) {
        // 入栈
        if (isFull()) {
            System.out.println("栈满了");
            return;
        }

        stack[++top] = value;
    }

    public int pop() {
        // 出栈
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        return stack[top--];
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("没有数据");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }
}

栈的链式存储结构

简称链栈

LinkStack.java

package com.stack;

/**
 * 因为头结点是必须的，栈顶指针也是必须的。
 * 所以合二为一！即初始化的时候不需要头结点
 */
public class LinkStack {
    private Node top;

    public boolean isFull() {
        return false;
    }

    public boolean isEmpty() {
        return top == null;
    }


    public void push(int num) {
        // 很少满栈，直接创建结点头插
        Node node = new Node(num);
        node.next = top;
        top = node;
    }

    public int pop() {
        // 出栈
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int value = top.data;
        top = top.next;
        return value;
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("没有数据");
            return;
        }
        Node temp = top;
        while (temp != null) {
            System.out.print(temp.data+"\t");
            temp = temp.next;
        }
    }

}

class Node{
    public int data;
    public Node next;

    public Node() {
    }

    Node(int data) {
        this.data = data;
    }
}

Java中自带封装好的Stack类，可以直接使用。

底层继承关系 class Stack<E> extends Vector<E>

用数组存储，如果栈满会自动扩容。

对比

顺序栈与链栈，它们在时间复杂度上是一样的，均为0（1）。

对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，

但它的优势是存取时定位很方便，

而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。

所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，

有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

栈的作用

• 递归
• 逆波兰式
• 中缀转后缀