一、栈
1.什么是栈
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
2.栈的使用
public static void main(String[] args) {
Stack<Integer> stack=new Stack<>();
stack.push(12);
stack.push(23);
stack.push(34);
stack.push(45);
int ret=stack.size();
System.out.println(ret);
int ret1=stack.peek();
System.out.println(ret1);
int ret2=stack.pop();
System.out.println(ret2);
boolean ret3=stack.empty();
System.out.println(ret3);
}运行结果：
3.栈的模拟实现
1.数组实现栈
import java.util.Arrays;
public class MyStack {
int elem[];
int Usedsize;
public static final int DEFAULT_CAPACITY=10;
public MyStack(){
elem=new int[DEFAULT_CAPACITY];
}
//入栈
public int push(int val){
if(isFull()){
//判断是否满了，满了就扩容
this.elem= Arrays.copyOf(elem,2*elem.length);
}
elem[Usedsize++]=val;
return val;
}
public boolean isFull(){
return Usedsize==elem.length;
}
//出栈
public int pop(){
if (isEmpty()){
throw new EmptyStackEception("栈为空。。。");
}
int e=peek();
Usedsize--;
return e;
}
public boolean isEmpty(){
return Usedsize==0;
}
public int peek(){
if(isEmpty()){
return -1;
}
return elem[Usedsize-1];
}
}public class EmptyStackEception extends RuntimeException{
public EmptyStackEception() {
}
public EmptyStackEception(String message) {
super(message);
}
}2.双链表实现栈
//双链表实现栈
class MyStack2{
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 int push(int val){
ListNode node=new ListNode(val);
if(head==null){
head=last=node;
}
last.next=node;
node.prev=last;
last=node;
return val;
}
//出栈
public int pop(){
if (isEmpty()){
throw new EmptyStackEception("栈为空....");
}
if(head.next==null){
//只有一个节点
int val1=head.val;
head=last=null;
return val1;
}
int val2=last.val;
last=last.prev;
return val2;
}
public boolean isEmpty(){
return head==null;
}
public int peek(){
return last.val;
}
}栈、虚拟机栈、栈帧有什么区别呢？
1.栈是一种数据结构
2.虚拟机栈是JVM的内存
3.栈帧是调用方法的时候开辟的内存。
4.栈的相关习题
解题思路：
遍历tokens数组，如果遇上数字就入栈，如果不是数字是运算符就弹出栈顶的两个元素，根据运算符进行加减乘除（switch）。
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack=new Stack<>();
for(int i=0;i<tokens.length;i++){
String str=tokens[i];
if(!isoperations(str)){
//是操作数
int val=Integer.valueOf(str);
stack.push(val);
}else{
//是运算符
int num2=stack.pop();
int num1=stack.pop();
switch(str){
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1-num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1/num2);
break;
}
}
}
return stack.pop();
}
private boolean isoperations(String str){
if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")){
return true;
}
return false;
}
}解题思路：这里要两个指针，i指针用来遍历pushV，j指针用来遍历popV。 遍历pushV数组时要先把元素入栈，然后还要看pushV入栈的元素与popV是否相同，如果一样就从栈中弹出，然后 j++，否则i++，继续入栈。（注意：不能无限制地去弹出，弹出时也要看栈是否满了，以及j指针遍历popV数组时是否超出了popV数组的长度。）
import java.util.*;
public class Solution {
public boolean IsPopOrder(int[] pushV, int[] popV) {
Stack<Integer> stack=new Stack<Integer>();
int j=0;
for(int i=0;i< popV.length;i++){
stack.push(pushV[i]);
while(!stack.isEmpty() && j<popV.length && stack.peek()==popV[j]){
stack.pop();
j++;
}
}
//return j>=popV.length;
return stack.empty();
}
}解题思路：
这里需要两个栈来完成，一个是普通栈（stack），一个是最小栈（minStack）。
首先普通栈一定要存放数据，那么最小栈如何放数据呢？这要看情况：
1.如果是第一次存数据，无论值多大都一定要放进去，因为，此时的数据既是最小值也是最大值。 2.如果不是第一次放数据就要进行比较了，要看这个数据是否小于等于最小栈的栈顶元素，如果小于等于就放，不然就不放。
为什么等于也要放呢？
因为minStack pop的时候是根据stack的栈顶来看的，如果和stack栈顶一样，就弹出。 如果等于的时候不放，就可能会出现以下情况
public class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack=new Stack<>();
minStack=new Stack<>();
}
public void push(int val) {
stack.push(val);
if(minStack.isEmpty()){
//最小栈为空则为第一次存放
minStack.push(val);
}else {
int peekNum= minStack.peek();
if(val<=peekNum){
minStack.push(val);
}
}
}
public void pop() {
int val=stack.pop();
if(val==minStack.peek()){
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}解题思路：
1.找到所有不匹配的情况，一共五种，那么剩下的就是匹配的情况
2.只要是左括号就入栈，遇到右括号看此时栈顶的左括号是否匹配，如果不匹配 就直接返回false
3.字符串没有遍历完成，但是栈是空的，此时也是不匹配
4.字符串遍历完成，但是栈还是不为空，此时也是不匹配
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{
//不是左括号，但是第一个就是右括号，不匹配，不入栈，此时栈为
if(stack.isEmpty()){
return false;
}
int ch2=stack.peek();//得到的是前面入栈的左括号
//前面已入栈了左括号，那么就看这个右括号和前面入栈的左括号是否匹配
//匹配就弹出前面入栈的左括号
if(ch2=='(' && ch==')' || ch2=='[' && ch==']' || ch2=='{' && ch=='}'){
stack.pop();
}else{
return false;
}
}
}
//字符串遍历完成，看栈是不是为空，为空则匹配
return stack.isEmpty();
}
}二、队列
1.什么是队列？
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，进行插入操作的一端称为队尾，进行删除操作的一端称为队头，队列中的数据遵循先进先出的原则出入队。
2.队列的使用
public static void main(String[] args) {
Queue<Integer> queue=new LinkedList<>();
queue.offer(21);
queue.offer(33);
queue.offer(26);
queue.offer(65);
int ret=queue.size();
System.out.println(ret);
int ret2=queue.peek();
System.out.println(ret2);
int ret3=queue.poll();
System.out.println(ret3);
boolean ret4=queue.isEmpty();
System.out.println(ret4);
}运行结果：
3.队列的模拟实现
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 int offer(int val){
ListNode node=new ListNode(val);
if(head==null){
head=last=node;
} else{
last.next=node;
node.prev=last;
last=node;
}
return val;
}
//出队
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(empty()){
return -1;
}
return head.val;
}
}4.队列的相关习题
解题思路：
1.当两个队列 都是空的时候 放到第一个队列
2.再次“入栈”的时候 ，放到不为空的队列
3.“出栈”的时候，出不为空的队列，出size-1个元素 剩下的元素就是要出栈的元素
class MyStack {
Queue<Integer> q1;
Queue<Integer> q2;
public MyStack() {
q1=new LinkedList<>();
q2=new LinkedList<>();
}
public void push(int x) {
if(empty()){
q1.offer(x);
return;
}else {
if(!q1.isEmpty()){
q1.offer(x);
}else {
q2.offer(x);
}
}
}
public int pop() {
if (empty()){
return -1;
}
if(!q1.isEmpty()){
int size=q1.size();
for(int i=0;i<size-1;i++){
q2.offer(q1.poll());
}
return q1.poll();
}else {
int size=q2.size();
for (int i=0;i<size-1;i++){
q1.offer(q2.poll());
}
return q2.poll();
}
}
public int top() {
if (empty()){
return -1;
}
if(!q1.isEmpty()){
int size=q1.size();
int tmp=-1;
for(int i=0;i<size;i++){
tmp=q1.poll();
q2.offer(tmp);
}
return tmp;
}else {
int size=q2.size();
int tmp=-1;
for (int i=0;i<size;i++){
tmp=q2.poll();
q1.offer(tmp);
}
return tmp;
}
}
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}解题思路：
1.“入队”:把数据放到第一个栈当中
2.“出队”:出s2这个栈当中的栈顶元素即可，如果s2为空，把s1里面所有的元素全部放到s2
3.当两个栈都为空 说明 模拟的队列为空
import java.util.Queue;
import java.util.Stack;
public class StackImplementQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public StackImplementQueue() {
s1=new Stack<>();
s2=new Stack<>();
}
//入队
public void push(int x) {
s1.push(x);
}
//出队
public int pop() {
if(empty()){
return -1;
}
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
//获得队头元素
public int peek() {
if(empty()){
return -1;
}
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}