目录
栈（Stack）
队列（Queue）
循环队列
栈（Stack）
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除操作元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In Out)的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
可以将栈类比为枪的弹匣，先进弹夹的子弹后打出。
java中提供了Stack类来实现栈。Stack包括以下方法：
以下是栈的模拟实现：
package MyStack;
import java.util.Arrays;
public class MyStack {
public int[] elem;
public int usedSize;
public static final int DEFAULT_CAPACITY = 10;
public MyStack(){
this.elem = new int[DEFAULT_CAPACITY];
}
//压栈，入栈
public void push(int val){
if(isFull()){
this.elem = Arrays.copyOf(elem,elem.length*2);
}
elem[usedSize++] = val;
}
public boolean isFull(){
return usedSize == elem.length;
}
//出栈
public int pop(){
if(isEmpty()){
throw new StackEmptyException("栈为空");
}
int oldVal = elem[usedSize-1];
usedSize--;
// elem[usedSize] == null;
return oldVal;
}
public boolean isEmpty(){
return usedSize ==0;
}
public int peek(){
if(isEmpty()){
throw new StackEmptyException("栈为空");
}
return elem[usedSize-1];
}
}
队列（Queue）
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
在java中，提供了Queue接口来实现队列。底层是通过链表实现的。
包括以下方法：
注：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
以下是队列的模拟实现;
package MyQueue;
public class MyQueue {
static class ListNode{
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
//入队
public void offer(int val){
ListNode node = new ListNode(val);
if (head == null) {
head = last = node;
}else {
//尾插
last.next = node;
node.prev = last;
last = node;
}
}
public int poll(){
if(head == null){
return -1;
}
int val = -1;
if(head.next == null){
val = head.val;
head =null;
last = null;
return val;
}
val = head.val;
head = head.next;
head.prev = null;
return val;
}
public boolean empty(){
return head == null;
}
public int peek(){
if(head == null){
return -1;
}
return head.val;
}
}
循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可能就会使用循环队列。环形队列通常使用数组实现。
如以下数组，我们可以定义rear和front指针，front表示队头，rear表示队尾。队列采用头删，尾插的方式。当插入元素时，rear向后++，当删除元素时，front也向后++。当rear来到队尾，超出数组下标时，就可以回到数组开头，继续添加元素。数组就可以循环利用起来了。
问题：当rear和front相遇的时候，要么队列为空，要么队列为满。那么如何判断为空为满呢？
有以下方法：
1、添加usedSize属性来记录数组已经使用的长度。
2、牺牲一个空间，当rear的下一个元素时front的时候，此时rear指向的空间就不能再放了。
3、加标记，定义boolean类型的flag变量，初始为fasle，当rear与front第一次相遇的时候，置为true，当判断为true的时候，就说明再次相遇了。有可能是空，有可能是满。
注：rear如何从数组末尾回到数组开头：rear = （rear +1）%len
rear如何获得它的前一个元素： elem[（rear + elem.length -1）%elem.length]
以下是循环队列的实现：
public class MyCircularQueue {
public int[] elem;
public int front;
public int rear;
public MyCircularQueue(int k){
elem = new int[k];
}
//入队操作
public boolean enQueue(int value){
if(isFull()){
return false;
}
elem[rear] = value;
rear = (rear +1)%elem.length;
return true;
}
//删除队头元素
public boolean deQueue(){
if(isEmpty()){
return false;
}
front = (front+1)%elem.length;
return true;
}
//得到队头元素，不删除
public int Front(){
if(isEmpty()){
return -1;
}
return elem[front];
}
//得到队尾元素，不删除
public int Rear(){
if(isEmpty()){
return -1;
}
int index = (rear ==0) ? elem.length -1: rear-1;
return elem[ index];
}
//判空 front和rear相遇
public boolean isEmpty(){
return rear == front;
}
public boolean isFull(){
return (rear +1)%elem.length == front;
}
}
练习一题：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。（力扣链接：. - 力扣（LeetCode））
解：
依次读取字符串，将字符放到栈中。如果是左括号，直接入栈。
如果是右括号： 有三种情况返回false：
1、在未读取完时，如果栈为空，返回false
2、读取到的右括号如果和左括号不匹配，返回false
3、在字符串读取完时，如果栈不为空，返回false
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack();
for(int i=0;i<s.length();i++){
char ch = s.charAt(i);
//是不是左括号
if(ch == '(' || ch == '[' || ch == '{'){
stack.push(ch);
}else{
//右括号
//1.栈为空
if(stack.isEmpty()){
return false;
}
//2.栈不为空
char ch2 = stack.peek();
if((ch == ')' && ch2 == '(' )||( ch == ']' && ch2 =='[') ||( ch == '}' && ch2 =='{')){
stack.pop();
}else{
return false;
}
}
}
return stack.isEmpty();
}
}以上，关于栈和队列，希望对你有所帮助。
