1、stack：特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
2、主要有三个核心操作：入栈、出栈、取栈顶元素。
（1）入栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
（2）出栈：：栈的删除操作叫做出栈。出数据在栈顶。
（3）取栈顶元素：即返回栈顶元素的值。
3、栈的实现：既可以利用线性表实现，即尾插 + 尾删的方式，也可利用链表实现，下面将用线性表实现。
public class MyStack { //使用线性表实现 //暂不考虑扩容 private int[] array = new int[100]; private int size = 0; //入栈 public void push(int v) { array[size++] = v; } //出栈 public int pop() { return array[--size]; } //取栈顶元素 public int peek() { return array[size - 1]; } //判空 public boolean isEmpty() { return size == 0; } //求长度 public int size() { return size; } }1、Queue：也是特殊的线性表，只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵守先进先出FIFO(First In First Out) 原则。
2、队列主要有三个核心操作：出队列、入队列、取队列首元素。
（1）入队列：：进行插入操作的一端称为队尾（Tail/Rear）。
（2）出队列：进行删除操作的一端称为队头 （Head/Front）。
（3）取队列首元素：
3、队列的实现：顺序表和链表均可，但使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出 数据，效率会比较低。
（1）链表实现：
class Node{ public int val; public Node next; public Node(int val) { this.val = val; } } public class MyQueue { //使用链表实现 //对应队首元素 private Node head = null; //对应队尾元素 private Node tail = null; private int size=0; //入队列 public void offer(int x) { Node newNode = new Node(x); //使用尾插 //空链表 if(head == null) { head = newNode; tail = newNode; size++; } //非空链表 tail.next = newNode; tail = tail.next; size++; return; } //出队列 public Integer poll() { if(head == null) { return null; } Integer ret = head.val; head = head.next; //当前队列只有一个元素 //删除后要修改tail的指向 if(head == null) { tail = null; } size--; return ret; } //取队首元素 public Integer peek() { if(head == null) { return null; } return head.val; } //判空 public boolean isEmpty() { return head == null; } //求长度 public int size() { return size; } }（2）数组实现：其思路是顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。当存储空间的最后一个位置已被使用而再要进入队运算时，只需存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。
另：循环队列中，判空判满的两种方式：
①：直接空出一个位置，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。
②：直接添加size属性记录长度，若size=0则队空、size=MaxSize则队满。
public class MyQueue { private int[] data = new int[100]; // [ head , tail ) private int head = 0;//队首元素下标 private int tail = 0;//队尾元素下标 private int size = 0; //入队列：插入成功返回true，失败返回false，队列满则失败 public boolean offer(int x) { if(size == data.length) { return false; } data[tail] = x; tail++; if(tail == data.length) { tail = 0; } size++; return true; } //出队列 public Integer poll() { if(size == 0) { return null; } Integer ret = data[head]; head++; if(head == data.length) { head = 0; } size--; return ret; } //取队列首元素 public Integer peek() { if(size == 0) { return null; } return data[head]; } //判空 public boolean isEmpty() { return size == 0; } //求长度 public int size() { return size; } }
