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

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;        }    }}

1. 什么是栈(Stack)

2. java实现

1. 什么是栈(`Stack`)