当前位置:首页>Java>Java 高级教程>Java栈、顺序栈、链式栈的数据结构和算法

Java栈、顺序栈、链式栈的数据结构和算法

作者:githubofrico发布时间:2019-09-14 16:13:36地址:https://dwz.cn/AMenD9kw

Java栈的概念

栈的概念名词

  • 栈:一种只允许在一端进行插入或删除的线性表

  • 栈顶:线性表允许进行插入删除的那一端

  • 栈底:固定的,不允许进行插入和删除的那一端

  • 空栈:不含任何元素的空表

什么是栈

栈是一种特殊的线性结构。

  • 栈满足线性结构

  • 栈特殊性:栈有特殊的存储方式,访问结构(先进先出,进和出在一个端)

什么是栈

Java实现栈

本文使用Java语言,实现了顺序栈链式栈 的数据结构及其相关算法常用操作,主要包括如下:

  • 压栈操作push

  • 弹栈操作pop

  • 查看栈顶元素peek

  • 查看栈的大小

  • 查看栈是否为空

  • 查看栈的最小元素(O(1)时间复杂度)

构建栈的结点类

/**
 * Title: 结点类 
 * Description: 链表的基本元素
 */
 public class Node<T> {
    //包可见性
    Node<T> next;   
    T data;

    /**
     * 构造函数
     * 
     * @description 构造一个新节点
     * @param data 新元素数据
     * @param next 新元素与链表结合节点
     */
    public Node(T data) { 
        this.data = data;
    }

    public T getData() {
        return data;
    }

    @Override
    public String toString() {
        return data.toString();
    }

    public Node<T> getNext() {
        return next;
    }
}

使用LinkedList实现栈

/**        
 * Title: 使用LinkedList实现栈  
 */      
public class LinkedListStack<E> {

    // 支撑List
    private LinkedList<E> stack;

    // 构造函数
    public LinkedListStack(){
        stack = new LinkedList<E>();
    }
}

栈是否为空

public boolean isEmpty(){
    return stack.isEmpty();
}

压栈

public void push(E data){
    stack.addFirst(data);
}

弹栈

public E pop() throws Exception{
    if(stack.isEmpty()){
        throw new Exception("栈已满...");
    }
    return stack.pop();
}

打印栈信息

@Override
public String toString() {
    return stack.toString();
}

测试程序

public static void main(String[] args) throws Exception {
    LinkedListStack<String> stack = new LinkedListStack<String>();
    stack.push("Rico");
    stack.push("TJU");
    stack.push("Livia");
    stack.push("NEU");

    System.out.println(stack);

    stack.pop();
    System.out.println(stack);
}

顺序栈

栈的顺序存储成为顺序栈,他是利用一组地址连续的储存单元存放自栈底到栈顶的数据元素,同时附设一个指针(Top)指示当前栈的位置。底层数据结构是数组。

  • 栈顶指针:S.top,初始值设定为S.top = -1; 栈顶元素:S.data[S.top]。

  • 进栈操作:栈不满的时候,栈顶指针先加1,再送值到栈顶元素

  • 出栈操作:栈非空的时候,先取值栈顶元素,再将栈顶指针减1

  • 栈空操作:S.top = -1; 栈满条件:S.top == MaxSize-1; 栈长:S.top + 1;

  • 由于顺序栈的入栈操作收到数组上界的约束,对栈的最大使用空间估计不足时候,有可能发生栈的上溢。

顺序栈的核心数据结构

import java.util.Arrays;

/**        
 * Title: 顺序栈    
 * Description: 数组作为底层实现
 */      
public class SeqStack<E> {

    private Object[] stack;  // 支撑数组
    private int top;         // 栈顶指针
    private int maxSize;     // 栈的最大容量

    // 默认构造函数
    public SeqStack(){
        this(10);
    }

    // 可以指定容量的构造函数
    public SeqStack(int maxSize){
        this.stack = new Object[maxSize];
        this.top = -1;
        this.maxSize = maxSize;
    }
}

栈是否为空

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

弹出并删除栈顶元素

public E pop() throws Exception{
    if (top == -1) {
        throw new Exception("栈为空...");
    }
    E element = (E)stack[top];
    stack[top --] = null;    // 删除该元素
    return element;
}

栈添加元素

public void push(E e) throws Exception{
    if (top == maxSize -1) {
        throw new Exception("栈已满...");
    }
    stack[++top] = e;
}

打印栈

@Override
public String toString() {
    return Arrays.toString(stack);
}

测试栈的程序

public static void main(String[] args) throws Exception {
    SeqStack<String> stack = new SeqStack<String>();
    stack.push("Rico");
    stack.push("TJU");
    stack.push("Livia");
    stack.push("NEU");

    System.out.println(stack);

    stack.pop();
    System.out.println(stack);
}

增强自定义链式栈

增强自定义链式栈:通过维护一个栈来保证用O(1)的时间复杂度求栈中的最小元素 (空间换取时间)。

使用额外的栈结构存储栈中的最小元素。

如果当前入栈的元素比原来栈中的最小值还小,则将其保存到最小值栈中;否则,不做任何操作。

如果当前出栈的元素正好是当前栈中的最小值,那么将最小值栈中的该最小值也一并弹出;否则,不做任何操作。

链式栈 核心数据结构

import java.util.Comparator;

public class LinkedStack<E> {

    private Node<E> top; // 栈顶元素
    private int size; // 链式栈的大小

    /**  最小值栈*/    
    private LinkedStack<E> min;

    // 构造函数
    public LinkedStack(){
    }

判断栈是否为空

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

压栈操作

public void push(E data) {
    Node<E> node = new Node<E>(data); 
    // 新加入的元素指向栈顶元素
    node.next = top;
    top = node;
    size++;
}

压栈操作,使用最小值栈

public void push(E data, Comparator<? super E> c) {
    push(data);
    if(min == null){
        min = new LinkedStack<E>();
    }
    if(min.peek() == null){
        min.push(data);
    }else if(c.compare(this.peek().data, min.peek().data) < 0){
        min.push(data);
    }
}

弹出并删除栈顶元素

public Node<E> pop(){
    if (isEmpty()) {
        return null;
    }

    Node<E> node = top;
    top = top.next;
    node.next = null;
    size--;
    return node;
}

弹出并删除栈顶元素,使用最小值栈

public Node<E> pop(Comparator<? super E> c){
    Node<E> temp = this.pop();
    if(temp != null && min.peek() != null){
        if(c.compare(temp.data, min.peek().data) == 0){
            min.pop();
        }
    }
    return temp;
}

弹出栈顶元素(不执行删除操作)

public Node<E> peek(){
    if (isEmpty()) {
        return null;
    }
    return top;
}

获取当前栈中的最小值

public Node<E> min() {
    if(min.peek() == null){
        return null;
    }else{
        return min.peek();
    }
}

打印栈

public void print() {
    Node<E> index = top;
    while (index != null) {
        System.out.print(index.data + " ");
        index = index.next;
    }
    System.out.println();
}

返回栈的大小

public int size(){
    return size;
}

getMin

public LinkedStack<E> getMin() {
    return min;
}

setMin

public void setMin(LinkedStack<E> min) {
    this.min = min;
}

toString方法

@Override
public String toString() {
    Node<E> index = top;
    StringBuilder sb = new StringBuilder();
    while (index != null) {
        sb.append(index.data).append(" ");
        index = index.next;
    }
    return sb.toString();
}

Java栈测试代码

public class OptimizationStackQueueTest {
    public static void main(String[] args) {
        OptimizationStackQueue<Integer> queue = new OptimizationStackQueue<Integer>();
        queue.put(1);
        queue.put(3);
        queue.put(5);
        queue.put(2);
        queue.put(8);
        queue.put(6);
        System.out.println(queue);
        System.out.println("\n------------------\n");

        queue.pop();
        System.out.println(queue);
        System.out.println("\n------------------\n");

        queue.put(4);
        queue.put(5);
        System.out.println(queue);
        System.out.println("\n------------------\n");
    }
}