链式栈和链式队列

链式栈和链式队列的优点：不用像顺序栈和顺序队列一样，进行扩容。

链式栈

class LinkStack<T>{ // 链表的第一个节点充当栈顶元素 private Entry<T> bottom; // 栈底 private int count; // 记录链表节点的个数 public LinkStack(){ bottom = new Entry<>(null, null); } // 入栈操作 public void push(T val){ Entry<T> node = new Entry<>(val, bottom.next); bottom.next = node; count++; } // 出栈，并把出栈元素的值返回 public T pop(){ if(empty()) return null; T val = bottom.next.data; bottom.next = bottom.next.next; count--; return val; } // 查看栈顶元素 public T peek(){ if(empty()) return null; return bottom.next.data; } // 判断栈空 public boolean empty(){ return bottom.next == null; } // 返回栈里面元素的个数 public int size(){ return this.count; } /** * 链表的节点类型定义 * @param <T> */ static class Entry<T>{ T data; Entry<T> next; public Entry(T data, Entry<T> next) { this.data = data; this.next = next; } } } public class LinkStackTest { public static void main(String[] args) { LinkStack<Integer> ls = new LinkStack<>(); ls.push(23); ls.push(21); ls.push(56); ls.push(84); while(!ls.empty()){ System.out.print(ls.pop() + " "); } System.out.println(); } }

链式队列

/** * 链式队列 * front：指向的是链表的头节点 * rear:永远指向的是末尾节点 * @param <T> */ class LinkQueue<T> { // 构造函数 offer poll peek empty size private Entry<T> front; private Entry<T> rear; private int count=0; public LinkQueue() { Entry<T> node=new Entry<>(null,null); node.next=null; front=rear=node; } public void offer(T val) { Entry<T> node = new Entry<>(val, null); rear.next=node; rear= node; count++; } public T poll() { T val = null; if(this.front.next != null){ val = this.front.next.data; this.front.next = this.front.next.next; // 删除队列最后一个元素，要把rear指向front，队列才能判空 if(this.front.next == null){ this.rear = this.front; } this.count--; } return val; } public T peek() { if (empty()) { return null; } return front.next.data; } public boolean empty() { return front==rear; } public int size(){ return this.count; } public static class Entry<T> { T data; Entry<T> next; public Entry(T data, Entry<T> next) { this.data = data; this.next = next; } } }