算法-3-链表栈（最优设计方案）

目录

1、链表

2、链表栈

3、链表栈Kotlin

1、链表

链表是一种递归的数据结构，链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 

2、链表栈

链表的加入，让我们的栈的设计达到了最有的方案：

• 它可以处理任何类型的数据；
• 所需的空间总是和集合的大小成正比；
• 操作所需时间总是和集合大小无关。

public class LinkedStack<T> {private Node first;private int N = 0;// 集合的数量// 结点class Node {T item;Node next;}/*** 将元素放入栈顶*/public void push(T t) {Node oldFirst = first;first = new Node();first.item = t;first.next = oldFirst;N++;}/*** 将元素从栈顶删除*/public T pop() {T item=first.item;first=first.next;N--;return item;}public boolean isEmpty() {return N == 0;}public int size() {return N;}
}

3、链表栈Kotlin

class LinkedStack1<T> {private var first: Node? = nullprivate var N = 0 // 集合的数量// 结点internal inner class Node {var item: T? = nullvar next: Node? = null}fun push(t: T) {val oldFirst = firstfirst = Node()first!!.item = tfirst!!.next = oldFirstN++}fun pop(): T? {val item: T? = first?.itemfirst = first!!.nextN--return item}val isEmpty: Booleanget() = N == 0fun size(): Int {return N}
}

本文章的大部门内容来之于由Robert Sedgewick和Kevin Wayne著的《算法》第四版书籍中，本文章的目的主要是为了记录自己的学习笔记和技术分享。