数据结构-栈

niushao 2020-07-06

栈与队列

数据结构-栈

概念

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

栈顶(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)。

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

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

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

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

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

栈的作用

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

相关推荐