1. 栈基础
结构: 先进后出
2. 手写基于链表的栈 (和基于动态数组的栈对比)
- package com.tc.javabase.datastructure.linklist.stack;
- import com.tc.javabase.datastructure.linklist.LinkedList;
- import com.tc.javabase.datastructure.stack.Stack;
- /**
- * @Classname LinkedListStack
- * @Description 基于链表实现栈
- *
- * 结构特性: 先进后出
- *
- * 时间复杂度分析:
- * 入栈: O(1)
- * 出栈: O(1)
- * 查询栈顶元素: O(1)
- *
- * 综上所述: 基于链表的操作时间复杂度都是 O(1)
- *
- * @Date 2020/7/18 17:32
- * @Created by zhangtianci
- */
- public class LinkedListStack<E> implements Stack<E> {
- private LinkedList<E> list;
- private int size;
- @Override
- public int getSize() {
- return size;
- }
- @Override
- public boolean isEmpty() {
- return size == 0 ? true : false;
- }
- /**
- * 入栈
- * 时间复杂度: O(1)
- * @param e
- */
- @Override
- public void push(E e) {
- list.addFirst(e);
- }
- /**
- * 出栈
- * 时间复杂度: O(1)
- * @return
- */
- @Override
- public E pop() {
- return list.removeFirst();
- }
- /**
- * 瞧一眼栈顶元素
- *
- * 时间复杂度: O(1)
- * @return
- */
- @Override
- public E peek() {
- return list.getFirst();
- }
- @Override
- public String toString(){
- StringBuilder res = new StringBuilder();
- res.append("Stack: top");
- res.append(list);
- return res.toString();
- }
- }
来源: http://www.bubuko.com/infodetail-3654076.html