栈（Stack）

栈的概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作，进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈的数据遵循后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做压栈/进栈/入栈，入的数据在栈顶。

出栈：栈的删除操作叫做出栈，出的数据在栈顶。

栈的常用方法

//入栈
public void push(int val)//将栈顶元素出栈并返回
public int pop()//获取栈顶元素
public int peek()//检测栈是否为空
public boolean isEmpty()

模拟实现栈

构造一个空栈

public class MyStack {private int[] elem;private int usedSize;//栈的实际元素个数private static final int DEFAULT_CAPACITY = 10;//初始化栈的大小为DEFAULT_CAPACITYpublic MyStack() {this.elem = new int[DEFAULT_CAPACITY];}
}

实现push方法（入栈）

public void push(int val) {//判断栈是否已满 满就扩容if (this.elem.length == usedSize) {this.elem = Arrays.copyOf(this.elem,this.elem.length*2);}this.elem[usedSize] = val;usedSize++;
}

实现pop方法（将栈顶元素出栈并返回）

如果栈为空，返回栈顶元素就会报错，我们可以自定义一个异常用来解决报错问题

public class emptyException extends RuntimeException {public emptyException() {}public emptyException(String message) {super(message);}
}

public int pop() {//如果为空栈就抛出一个异常if (usedSize==0){throw new emptyException();}int oldVal = this.elem[usedSize-1];usedSize--;return oldVal;
}

实现peek方法（获取栈顶元素）

public int peek() {//如果为空栈就抛出一个异常if (usedSize==0){throw new emptyException();}return this.elem[usedSize-1];
}

实现isEmpty方法（检测栈是否为空）

public boolean isEmpty() {//判断栈是否为空 只需要判断栈的实际元素个数是否为0即可return usedSize==0;
}

队列（Queue）

队列的概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循先进先出FIFO（First in First Out）的原则。在Java里面Queue 是一个接口，底层是通过链表实现的。

入队列：进行插入的一端称为队尾。

出队列：进行删除的一端称为队头。

队列的常用方法

//入队
public void offer(int x)//出队
public int poll()//获取队头元素x
public int peek()//获取队列中有效元素的个数
public int size()//检测队列是否为空
public boolean isEmpty()

队列的模拟实现

双链表模拟实现队列

public class MyQueue {static class ListNode {public int val;public ListNode next;public ListNode prev;public ListNode(int val) {this.val = val;}}public ListNode front;//队头public ListNode rear;//队尾public int usedSize = 0;//队列实际元素个数}

实现offer方法（入队）

public void offer(int x) {ListNode node = new ListNode(x);//队列为空if (front==null){front=rear=node;}else {node.next=front;front.prev=node;front=node;}usedSize++;
}

实现poll方法（出队）

public int poll(){//队列为空if (front==null){return -1;}int ret = rear.val;//队列中只有一个元素if (front==rear){front=null;rear=null;usedSize--;return ret;}//删除尾节点rear=rear.prev;rear.next=null;usedSize--;
}

实现peek方法（获取队头元素）

public int peek(){if (front==null){return -1;}return front.val;
}

实现size方法（获取队列中有效元素的个数）

public int size(){return usedSize;
}

实现isEmpty方法（检测队列是否为空）

public boolean isEmpty(){return front==null;
}

循环队列模拟实现

public class MyCircularQueue {public int[] elem;public int front;//队头public int rear;//队尾//构造循化队列public MyCircularQueue(int len) {this.elem = new int[len+1];}//入队public boolean enQueue(int val){//判断队列是否装满if (isFull()){return false;}elem[rear] = val;rear = (rear+1)%elem.length;return true;}//检测队列是否装满private boolean isFull() {return (rear+1)%elem.length==front;}//出队public boolean deQueue(){if (isFull()){return false;}front = (front+1)%elem.length;return true;}//获取队头元素public int getFront(){if (isEmpty()){return -1;}return elem[front];}//检测队列是否为空public boolean isEmpty(){return front==rear;}
}