目标：1、 栈的概念及使用，2、 队列的概念及使用，3.、相关OJ题

1、栈(Stack)

1、什么是栈

栈：
1、一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

2、进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
3、栈中的数据元素遵守先进后出的原则。

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

进栈：

出栈

2、栈中常使用的方法

public class Test {public static void main(String[] args) {Stack stack = new Stack<>();//构造一个空栈//push()方法是往栈中存放元素stack.push(1);//向栈中压入元素，底层可以理解为是以数组的形式存储的stack.push(2);stack.push(3);System.out.println(stack);}
}

运行结果：

//pop()方法是将栈顶元素弹出，并返回栈顶元素//所谓栈顶元素就是最后入栈的元素stack.pop();System.out.println(stack);

运行结果：

        //peek()方法是获取栈顶元素，并不弹出System.out.println(stack.peek());

运行结果：

      stack.push(1);//向栈中压入元素，底层可以理解为是以数组的形式存储的stack.push(2);stack.push(3);stack.push(4);stack.push(5);System.out.println(stack);//获取栈中有效元素的个数int ret = stack.size();System.out.println(ret);

运行结果：

        //判断栈是否为空，栈为空返回true，栈中有元素返回falseBoolean flag = stack.isEmpty();System.out.println(flag);

运行结果：

3、栈的应用场景

1、逆序打印链表

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class Test1 {Stack stack = new Stack<>();//构造一个空栈class ListNode{public int val;ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;public ListNode creatNode(){ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);head = listNode1;//创建一个头结点listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;listNode5.next = null;return listNode1;}public void print(ListNode Node){ListNode cur = Node;//将原始链表的头结点保存，防止丢失//打印原始链表while (Node != null){System.out.print(Node.val+" ");Node = Node.next;}System.out.println();//将链表中的元素存入栈中while (cur != null){stack.push(cur.val);//元素入栈cur = cur.next;}//在链表不为空的情况下，将栈中元素出栈并打印//重点：栈中的元素是先入后出while(!stack.isEmpty()){System.out.print(stack.pop()+" ");}}public static void main(String[] args) {Test1 test1 = new Test1();test1.creatNode();//创建一个链表test1.print(test1.head);//逆序打印一个链表}}

运行结果：

2、有效的括号

力扣第20题：添加链接描述

其次，我们要想到利用栈相关的知识去解决问题
解题思路：

创建一个栈，并将所有的左括号压入栈中，一旦遇到右括号，从栈中弹出一个元素与之比较，相同则继续比较下一个，否则返回false；因为栈是先进后出的特性，所以弹出的那个元素就是与右括号相邻的左括号。

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack();//创建一个栈for(int i=0;i<s.length();i++){//遍历整个字符串，并获取每一个元素char x  = s.charAt(i);//元素是左括号，则存入栈中if(x == '('||x == '['||x == '{'){stack.push(x);}else{if(stack.empty()){return false;}char ch2 = stack.peek();//先判断栈中最顶部的元素是否与之匹配if((x==')'&&ch2=='(')||(x=='}'&&ch2=='{')||(x==']'&&ch2=='[')){//如果匹配，则弹出该元素stack.pop();}else{//否则返回falsereturn false;}}}//当字符串遍历完成之后，如果栈不为空，则意味着左括号多了，此时也返回falseif(!stack.empty()){return false;}//当字符串遍历完成之后，如果栈为空，此时也返回true；return true;}
}

2、队列(Queue)

1、什么是队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

队的插入删除操作是在队的两端进行的，这一点需要和栈进行区别

2、队列的使用

在Java中，Queue（队列）是个接口，底层是通过链表实现的。

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;public class Test {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<Integer>();//因为Queue只是一个接口，所以我们要创建一个LinkedList，并进行向下转型//offer()往队列中放入元素queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue);//因为Queue底层是链表实现的，所以我们直接打印即可}
}

运行结果：

          //poll()将队头的元素删除queue.poll();System.out.println(queue);

运行结果：

peek()、isEmpty()、size()使用方法与Stack相同，故不再做过多讲解。

3、循环队列

实际中我们有时还会使用一种队列叫循环队列。

循环队列通常使用数组实现。

创建一个循环队列：
题目地址：
添加链接描述

//MyCircularQueue(k): 构造器，设置队列长度为 k 。
//Front: 从队首获取元素。如果队列为空，返回 -1 。
//Rear: 获取队尾元素。如果队列为空，返回 -1 。
//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
//deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
//isEmpty(): 检查循环队列是否为空。
//isFull(): 检查循环队列是否已满。class MyCircularQueue {public int[] elem;public int front;//队头public int rear;//队尾//构造器，设置队列长度为 kpublic MyCircularQueue(int k) {//创建一个k+1长度的数组，防止溢出elem = new int[k+1];}// enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。public boolean enQueue(int value) {if(isFull()){//数组已满的情况下，直接返回falsereturn false;}elem[rear] = value;rear = (rear+1)%elem.length;return true;}//    deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。public boolean deQueue() {if(isEmpty()){return false;}front = (front+1)%elem.length;return true;}//    Front: 从队首获取元素。如果队列为空，返回 -1 。public int Front() {if(isEmpty()){return -1;}else{return elem[front];}}public int Rear() {if(isEmpty()){return -1;}else{int index = rear == 0 ? elem.length-1 : rear-1;return elem[index];}}//    isEmpty(): 检查循环队列是否为空。public boolean isEmpty() {if(front == rear){return true;}return false;}//    isFull(): 检查循环队列是否已满。public boolean isFull() {if((rear+1)%elem.length == front){return true;}return false;}
}