1. 栈(Stack)
1.1 概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
1.2 实现
1. 利用顺序表实现，即使用尾插 + 尾删的方式实现
2. 利用链表实现，则头尾皆可
相对来说，顺序表的实现上要更为简单一些，所以我们优先用顺序表实现栈。
基于数组的顺序栈，实现代码如下：
import java.util.ArrayList; import java.util.List; import java.util.NoSuchElementException; /** * 基于数组的顺序栈实现 * @param <E> */ public class MyStack<E> { // 当前栈的数据个数 private int size; // 实际存储数据的动态数组 - ArrayList private List<E> data=new ArrayList<>(); //入栈 public void push(E val){ //尾插 data.add(val); size++; } //出栈，并返回栈顶元素 public E pop(){ if(isEmpty()){ // 栈为空，没有栈顶元素 throw new NoSuchElementException("stack is empty! cannot pop!"); } // 删除栈顶元素 E val = data.remove(size - 1); size --; return val; // 等同于 return data.remove(--size); } //只返回栈顶元素 public E peek(){ if(isEmpty()){ // 栈为空，没有栈顶元素 throw new NoSuchElementException("stack is empty! cannot peek!"); } return data.get(size-1); } //判断栈是否为空 public boolean isEmpty(){ return size == 0; } @Override public String toString() { StringBuilder sb=new StringBuilder(); sb.append("["); for (int i = 0; i < size; i++) { sb.append(data.get(i)); if(i!=size-1){ // 此时还没到栈顶，还没到数组末尾 sb.append(","); } } sb.append("]"); return sb.toString(); } }
引用方法如下：
public class StackTest { public static void main(String[] args) { MyStack<Integer> stack=new MyStack<>(); stack.push(1); stack.push(2); stack.push(3); //打印栈所有元素 System.out.println(stack); //打印栈顶元素 System.out.println(stack.peek()); //出栈，并打印栈顶元素 stack.pop(); System.out.println(stack); } }
2. 队列(Queue)
2.1 概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头
先进先出
2.2 实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
基于链表实现的基础队列，实现代码如下：
接口类：
public interface IQueue<E> { // 入队 void offer(E val); //出队 E poll(); //返回队首元素 E peek(); //判断队列是否为空 boolean isEmpty(); }
队列类：
import stack_queue.queue.IQueue; import java.util.NoSuchElementException; /** * 基于链表实现的基础队列 * @param <E> */ public class MyQueue<E> implements IQueue<E> { // 链表的每个节点 private class Node{ E val; Node next; public Node(E val){ this.val=val; } } // 当前队列中的元素个数 private int size; // 队首 private Node head; //队尾 private Node tail; @Override public void offer(E val) { Node node=new Node(val); if(head==null){ // 此时链表为空 head=tail=node; }else { tail.next=node; tail=node; } size++; } @Override public E poll() { if(isEmpty()){ throw new NoSuchElementException("queue is empty! cannot poll"); } Node node=head; head=node.next; // 将原来头节点脱钩 node.next=null; size--; return node.val; } @Override public E peek() { if(isEmpty()){ throw new NoSuchElementException("queue is empty! cannot peek"); } return head.val; } @Override public boolean isEmpty() { return size==0; } @Override public String toString() { StringBuilder sb=new StringBuilder(); sb.append("["); // 链表的遍历 for(Node x=head;x!=null;x=x.next){ sb.append(x.val); if(x.next!=null){ // 还没走到链表尾部 sb.append(","); } } sb.append("]"); return sb.toString(); } }
引用方法如下：
import stack_queue.queue.impl.MyQueue; public class QueueTest { public static void main(String[] args) { IQueue iQueue=new MyQueue(); iQueue.offer(1); iQueue.offer(2); iQueue.offer(3); System.out.println(iQueue); System.out.println(iQueue.peek()); iQueue.poll(); System.out.println(iQueue); } }
