栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
2.栈的示意图 3.栈在生活中的例子给枪上膛，或者后吃的东西先吐出来。
4.栈在Java中的定义和使用栈继承Vector类，底层还是连续的存储空间，和ArrayList底层都是数组。
（1）常用方法 （2）栈的常用操作练习
import java.util.Stack;
public class StackDemo {
public static void main(String[] args) {
Stack st = new Stack<>();
st.push(1);
st.push(2);
st.push(3);
st.push(4);
System.out.println(st.pop());//4弹出
System.out.println(st.peek());//查看栈顶元素
System.out.println(st.size());
}
}
5.栈的模拟实现
（1）问题分析
首先需要一个数组，然后再需要一个size来判断栈空间是否以满，通过上面分析，可以知道栈理解为对数组进行尾插和尾删的操作。这里还实现了一个动态扩容的方法，每次以原数组2倍的方式进行扩容。
（2）代码实现import java.util.Arrays;
import java.util.EmptyStackException;
public class MyStack {
public static void main(String[] args) {
Stack st = new Stack<>();
System.out.println(st.isEmpty());
st.push("111");
st.push("222");
st.push("333");
st.push("444");
System.out.println(st.getSize());
System.out.println(st.isEmpty());
System.out.println(st.peek());
System.out.println(st.pop());
System.out.println(st.peek());
st.pop();
st.pop();
st.pop();
st.pop();
System.out.println(st.getSize());
}
}
class Stack{
E[] array;
private int size;//统计栈中元素
public Stack(){
array= (E[])new Object[2];
}
//获取栈中元素的个数
public int getSize(){
return size;
}
public boolean isEmpty(){
if(size==0){
return true;
}
return false;
}
public E pop(){
if(size>0){
size--;
return array[size];
}
throw new EmptyStackException();
}
public E push(E ele){
//确保是否可以添加
ensureCapacity(size);
array[size]= ele;
size++;
return array[size-1];
}
//查看栈顶元素
public E peek(){
if(size>0){
return array[size-1];
}
throw new EmptyStackException();//栈为空异常
}
//扩容
private void ensureCapacity(int size){
if(size==array.length){
array = Arrays.copyOf(array,size*2);
}
}
}
6.栈的简单应用（习题）
（1）简单的括号匹配
问题：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
匹配的时候
不符合的情况：
代码实现：
public boolean isValid(String s) {
//遇到左括号进栈，遇到右括号出栈匹配
Stack st = new Stack<>();
for(int i=0;i
（2）逆波兰表达式求值
逆波兰表达式就是后缀表达式，我们平时的在数学中的加减乘除就是一种中缀表达式，为了使计算机可以计算，所有就有了逆波兰表达式，目的就是让计算机好识别。
题目：有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
举例：((2 + 1) * 3) = 9 ------》逆波兰表达式： ["2","1","+","3","*"]
我们用代码实现就是将字符串中的逆波兰求出结果
示意图：
代码实现：
public int evalRPN(String[] tokens) {
Stack st = new Stack<>();
for(int i=0;i
7.递归与栈的关系
（1）关系说明
由于Java中存在虚拟机栈，而递归和栈的后进后出关系相同，我们可以将递归转化用栈来进行实现。
（2）栈，虚拟机栈，栈帧的区别
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作
虚拟机栈：是线程私有的，它的生命周期与线程相同。虚拟机栈描述的是Java方法执行的内存模型
栈帧：每个栈帧都对应一个被调用的方法，可以理解为方法的运行空间
二.队列
1.队列概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点。其中进行插入操作的一端称为队尾（Tail/Rear） 出队列，进行删除操作的一端称为队头。
图解：
2.Java中队列的实现
底层是接口，需要借助链表linkedList来进行实现，而链表又是根据双向链表进行实现的，下面我们会自己实现一个简单的队列
3.常用方法
方法 功能 boolean offer(E e) 入队列 E poll() 出队列 peek() 获取队头元素 int size() 获取队列中有效元素个数 boolean isEmpty() 检测队列是否为空
4.队列常用操作练习
import java.util.linkedList;
import java.util.Queue;
public class QueueDemo {
public static void main(String[] args) {
Queue queue = new linkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
System.out.println(queue.size());
System.out.println(queue.poll());//出队列
System.out.println(queue.peek());//查看队头元素
}
}
5.队列的模拟实现
（1）问题分析
队列一个队头标记，一个队尾标记，其中队尾添加相当于一个尾插，队头出队相当于为头删，其中还有一个size来标记队列中有多少个元素，从而进行判断队列是否为空，并且通过双向链表进行实现。
（2）代码实现
public class MyQueue {
public static void main(String[] args) {
Queue st= new Queue<>();
// System.out.println(st.poll());
System.out.println(st.getSize());
st.offer("111");
st.offer("222");
st.offer("333");
System.out.println(st.getSize());
System.out.println(st.peek());
System.out.println(st.poll());
System.out.println(st.peek());
st.poll();
// st.poll();
System.out.println(st.peek());
// System.out.println(st.poll());
}
}
//原队列是接口，借助链表来进行实现
class Queue{
Node first;//队头
Node last;//队尾
private int size;
public int getSize(){
return size;
}
//队尾中插入元素
public E offer(E ele){
//链表尾插
Node newNode= new Node<>(ele);
if(first==null){
first=newNode;
last=newNode;
}else{
Node cur=first;
while(cur.next!=null){
cur=cur.next;
}
cur.next=newNode;
newNode.prev=cur;
last=newNode;
}
size++;
return last.value;
}
//队头移除元素
public E poll(){
if(first==null){
return null;
}
first=first.next;
E value= first.value;
first.prev.next=null;
first.prev=null;
size--;
return value;
}
//获取队头元素，不移除
public E peek(){
if(first==null){
throw new RuntimeException("队列为空，无法获取");
}
return first.value;
}
public boolean isEmpty(){
return size==0;
}
}
class Node{
E value;
Node prev;
Node next;
public Node(E value){
this.value=value;
}
}
6.循环队列
（1）引言
虽然Java中是通过链表来进行实现队列，但是还有另一种方法实现队列，那就是数组，由于直接使用数组会导致在删除后导致空间的浪费，所以就有了循环队列，这种方式实现的队列空间利用率是很好的。
（2）循环队列实现图解
（3）代码实现
class MyCircularQueue {
int[] arr;//数组
int count;//有效元素个数
int front;
int rear;
int size;//数组空间大小
public MyCircularQueue(int k) {
arr=new int[k];
size=arr.length;
}
//向队尾添加元素
public boolean enQueue(int value) {
if(isFull()){
return false;
}
arr[rear%size]=value;
rear++;
count++;
return true;
}
//出队列
public boolean deQueue() {
if(isEmpty()){
return false;
}
front++;
count--;
return true;
}
//获取队头元素
public int Front() {
if(isEmpty()){
return -1;
}
return arr[front%size];
}
//获取队尾元素
public int Rear() {
if(isEmpty()){
return -1;
}
return arr[(rear-1)%size];
}
//判空
public boolean isEmpty() {
return 0==count;
}
//判满
public boolean isFull() {
return size==count;
}
}
三.栈和队列的转换习题
1.用队列实现一个栈
这里使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
代码实现：
class MyStack {
Queue s1 = new linkedList<>();
Queue s2 = new linkedList<>();
public MyStack() {
}
public void push(int x) {
if(s1.size()!=0){
s1.offer(x);
}else if(s2.size()!=0){
s2.offer(x);
}else{
s1.offer(x);
}
}
public int pop() {
int val=0;//保存需要返回的值
//s1队列为空
if(!s1.isEmpty()){
while(s1.size()>1){
s2.offer(s1.poll());
}
val=s1.poll();
}else {
//s2队列不为空
while(s2.size()>1){
s1.offer(s2.poll());
}
val=s2.poll();
}
return val;
}
public int top() {
int val=0;//保存需要返回的值
//s2队列为空
if(!s1.isEmpty()){
while(s1.size()>1){
s2.offer(s1.poll());
}
val=s1.poll();
s2.offer(val);
}else {
//s2队列不为空
while(s2.size()>1){
s1.offer(s2.poll());
}
val=s2.poll();
s1.offer(val);
}
return val;
}
public boolean empty() {
return s1.size()==0 && s2.size()==0;
}
}
2.用栈实现一个队列
（1）实现目标
我们使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
（2）图解
（3）代码实现
class MyQueue {
Stack st1;//入队列操作
Stack st2;//出队列操作
public MyQueue() {
st1=new Stack<>();
st2=new Stack<>();
}
//入队列
public void push(int x) {
st1.push(x);
}
//出队列
public int pop() {
if(st2.empty()){
while(!st1.empty())
st2.push(st1.pop());
}
return st2.pop();
}
//插卡队头元素
public int peek() {
if(st2.empty()){
while(!st1.empty())
st2.push(st1.pop());
}
return st2.peek();
}
//判断队列是否为空
public boolean empty() {
return st1.empty() && st2.empty();
}
}
3.实现最小栈
（1）目的
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
（2）图解
（3 代码实现
class MinStack {
Stack st;
public MinStack() {
st = new Stack<>();
}
//入栈
public void push(int val) {
if(st.empty()){
st.push(val);
st.push(val);
}else{
int min = getMin();
if(min>val){
st.push(val);
st.push(val);
}else{
st.push(min);
st.push(val);
}
}
}
//弹出栈顶元素
public void pop() {
st.pop();
st.pop();
}
//查看栈顶元素
public int top() {
return st.peek();
}
//得到最小值
public int getMin() {
int t = st.pop();
int min = st.peek();
st.push(t);
return min;
}
}
