关于栈:数据结构和算法-栈

1. 什么是栈(Stack)

栈是一种数据结构。要阐明栈的定义，咱们须要从栈的个性说起，只有合乎这种个性的数据结构就能够叫做栈。

上面咱们来看看栈的个性是什么。

栈的个性是存入栈中的元素先进后出。先进后出是什么意思呢？

咱们思考有一个桶，桶有 5 层，每层只能放一个球，并且只有桶的最下面有个闭口用来放球和拿球。

当初假如咱们有三个球叫A,B,C，桶也是空的。

咱们依照 A,B,C 的先后顺序把球放进桶里，那么此时的桶外面的球的排布如下：

第五层 | |

第四层 | |

第三层 | C |

第二层 | B |

第一层 | A |

此时咱们再从桶里逐个把球拿进去。首先只能拿 C 球，把 C 球拿掉后能力拿 B 球，而后才是 A 球。

依据以上场景，咱们能够晓得放球程序是A,B,C；拿球程序是C,B,A。

即后面所说的栈的个性：先进后出，并且栈只提供栈顶供咱们放元素和取元素。

2. java 实现

栈能够通过链表实现，也能够通过数组实现。

背刺抉择双链表作为实现栈的载体。

对于链表以及双链表的实现，能够参考以前的文章：

Segment Fault

Bugkit

package org.bugkit.structure;

/**
 * @author bugkit
 * @since 2021.10.27
 */
public class LinkedList<E> extends AbstractList<E> implements List<E>, Queue<E>, Stack<E> {

    private Node<E> head;
    private Node<E> tail;

    // 创立一个空栈
    public LinkedList() {tail = head = null;}

    // 放入元素到栈中
    @Override
    public boolean push(E e) {Node<E> node = new Node<>(e);
        if (isEmpty()) {tail = head = node;}else{
            node.prev = tail;
            tail.next = node;
            tail = node;
        }
        size++;
        return true;
    }

    // 取出栈中的一个元素
    @Override
    public E pop() {if (isEmpty()) {throw new RuntimeException("Stack is empty");
        }
        E e = tail.e;
        if (size() == 1) {tail = head = null;}else{
            tail = tail.prev;
            tail.next = null;
        }
        size--;
        return e;
    }

    @Override
    public String toString() {StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: {");
        Node<E> node = head;
        while (node != null) {sb.append(node.e).append("<->");
            node = node.next;
        }
        sb.append("null}");
        return sb.toString();}

    private static class Node<E> {

        E e;

        Node<E> next;
        Node<E> prev;

        public Node(E e) {this.e = e;}
    }

}