为什么String对象是不可变的
1)首先,char 数组是 private 的,并且 String 类没有对外提供修改这个数组的方法,所以它初始化之后外界没有有效的手段去改变它;
2)其次,String 类被 final 修饰的,也就是不可继承,避免被他人继承后破坏;
3)最重要的!是因为 Java 作者在 String 的所有方法里面,都很小心地避免去修改了 char 数组中的数据,涉及到对 char 数组中数据进行修改的操作全部都会重新创建一个 String 对象。
栈是一个数据结构,先进先出;1、add()和offer()区别:
add()和offer()都是向队列中添加一个元素。一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,调用 add() 方法就会抛出一个 unchecked 异常,而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断!
2、poll()和remove()区别:
remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空,调用remove() 的行为与 Collection 接口的版本相似会抛出异常,但是新的 poll() 方法在用空集合调用时只是返回 null。因此新的方法更适合容易出现异常条件的情况。
3、element() 和 peek() 区别:
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似,在队列为空时, element() 抛出一个异常,而 peek() 返回 null。
下面是Java中Queue的一些常用方法:
add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满,则返回false
poll 移除并返问队列头部的元素 如果队列为空,则返回null
peek 返回队列头部的元素 如果队列为空,则返回null
put 添加一个元素 如果队列满,则阻塞
take 移除并返回队列头部的元素
原文链接:https://blog.csdn.net/xiaozhegaa/article/details/106136105
下面我们来看一下JVM的内存分布
此时的java虚拟机栈只不过是JVM中的一块内存该内存一般用来存放例如局部变量,调用函数的时候,我们会为这个函数开辟一块内存,叫做栈桢,这块内存就在java虚拟机栈里面
练习题1:一个栈的入栈顺序是abcde,那么不可能的出栈顺序是(载入站的时候也可以进行出栈)
A edcba B decba C dceab D abcde
那来进行举例,我们先出的元素是e,那么说明之前的abcd已经依次入栈了,此时在进行出栈,那么顺序就是dcba;B选项,如果先出d元素,那么说明之前abc已经进入到了栈里面,此时我出c,但是我此时在将e进行入栈,在对e进行出栈,在对b,a进行出栈;(所以必须先出b再出a)
D选项,a先入栈,立即对a进行出栈;入b在出b.........
练习题2:已知,一个站的入栈顺序是mnxyz,那么它的出栈顺序不可能是(C)
A mnxyz Bxnyzm Cnymxz D nmyzx
练习题3:中缀表达式转成后缀表达式,(5+4)*2-3,中缀表达式就是我们正常使用的那种;
解决思路:把加减乘除的每一个运算部分加上括号,然后再把对应的运算符放到对应的括号之后(后缀表达式)(放到前面就是前缀表达式),就得到了后缀表达式,(((5+4)*2)-3)再变成把加号移出黑色的括号外,把*移出红色的括号外,把-号移除蓝色的括号外;然后在进行去除括号,(((54)+2)*3)-,再变成54+2*3-;
问题:如何通过后缀表达式来进行计算值呢?
遍历字符串,如果是一个数,就把他们来进行入栈,以此向后进行遍历,如果遇到的是运算符,弹出栈顶的两个元素;计算出的结果继续放到栈里面,循环往复;
练习题四:逆波兰表达式(力扣原题)
根据 逆波兰表示法,求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:
输入:tokens = ["2","1","+","3","*"]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
示例 2:输入:tokens = ["4","13","5","/","+"]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
示例 3:输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出:22
解释:该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22思路:我们要做的是:如果遍历这个字符串发现是数字,就把它放到栈里面,如果发现此时不是数字,而是一个运算符,就取出栈顶的两个元素,进行运算;再把运算结果放到栈里面,最后返回栈顶元素
1)如何判断这个字符串里面的每一个字符是数字还是字符串?
2)如何把一个数字字符串转化成整数
public static int evalPPN(String[] arr1)//传过来的是一个字符串数组
{
Stack stack=new Stack<>();
for(int i=0;i
练习题5:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序;假设压入栈的所有数字均不会相同;假设序列1,2,3,4,5是某个栈的压入顺序,序列4,5,3,2,1是该栈序列最终的一个弹出序列,但是4,3,5,1,2就不可能是该压栈序列的弹出序列;
1)外层循环遍历arr1数组,每进行一次循环就将数组中的一个元素放到里面去
2)在每一次循环的内部,判断当前栈顶的元素和arr1[j]是否相等,如果相等就进行出栈操作,就是先进行入栈操作,再进行判断;
3)如果发现相同,就将j进行向后加加,并进行出栈操作(判断条件j不可以越界,栈不可以为空)
Stack练习题5:括号匹配问题:stack=new Stack<>(); int[] arr1={1,2,3,4,5}; int arr2[]={4,5,3,2,1}; int j=0; for(int i=0;i
这个题的结果有三种
1)左右括号不匹配([})
2)左括号多((())
3)右括号多())))))
遍历这个字符串,如果是左括号,就进行入栈操作;如果是右括号,就拿当前的栈顶元素和当前字符串遍历的右括号进行匹配,如果匹配,就弹出栈顶元素,如果不匹配,直接返回false;
//这个题保证左括号一定在前面,右括号一定在右边
public static boolean isVard(String s)
{
if(s==null||s.length()==0)
{
return true;
}
Stack stack=new Stack<>();
for(int i=0;i
练习题六:实现一个最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出:
[null,null,null,null,-3,null,0,-2]
解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
此时想要获取到最小值,常数时间内O(1),例如一组数据-2,3,10,-1;
我们要用到两个栈,一个是普通的栈,一个是最小栈
1)已开始进行遍历第一个的时候,两个栈都是空的所以都要存放数据
2)当遍历到第二个元素或者是以后的元素的时候,先将最小栈的栈顶元素和遍历中的元素进行比较,如果比当前栈顶元素小(或者相等)就进行入栈操作
3)每一次进行出栈的时候,出普通栈的时候一定要和当前最小栈的栈顶元素进行比较,如果相同,也进行出栈操作;
4)获得最小栈元素是时,不需要进行出栈操作,只需要进行peek(),获得最小元素就是获得栈顶元素;
class MinStack{
Stack stack=null;
Stack minStack=null;
public MinStack() {
this.stack =new Stack<>();
this.minStack =new Stack<>();
}
public void push(int val)
{ stack.push(val);
if(minStack.empty())
{
minStack.push(val);
}else{
int num=minStack.peek();
if(num>=val)
{
minStack.push(val);
}
}
}
public int GetMin()
{
return minStack.peek();
}
public void pop()
{
int num=stack.pop();
int min=minStack.peek();
if(num==min)
{
minStack.pop();
}
}
}
2.Stack中的常见方法(默认容量是10,扩容也是以2倍进行扩容的)
1)E push(E item) 压栈
2)E pop()出栈
3)E peek()获取栈顶元素但是不出栈
4)boolean empty()判断栈是否为空
他继承了Vector类,他有isEmpty()方法,但是Stack本身还有一个empty()方法
class MyStack{
int[] arr1;
int usedsize;
public MyStack() {
this.arr1 = new int[10];
this.usedsize = 0;
}
public boolean isFull()
{
return usedsize==arr1.length;
}
public void push(int val)
{ //1先进行判断数组是否是满的,满了就要进行扩容
if(isFull())
{
this.arr1= Arrays.copyOf(this.arr1,2*this.arr1.length);
}
arr1[this.usedsize]=val;
this.usedsize++;
}
public Boolean isEmpty()
{
return this.usedsize==0;
}
public int pop()
{ if(isEmpty())
{
System.out.println("当前栈里面的元素是空,是不可以进行删除的");
return -1;
}
int ret=arr1[usedsize-1];//先把要删除的人进行保存
//arr1[usedsize-1]=null;如果栈里面存放的是引用类型,那么需要把要删除的元素值为空
usedsize--;
return ret;
}
public int peek()
{
if(isEmpty())
{
throw new UnsupportedOperationException("当前栈顶元素是空");
}
return arr1[this.usedsize-1];
}
}
此时我们自己实现的栈,底层是一个数组,那么请问,可不可以用一个单链表来实现一个栈?
我们要向进行实现的话,还要保证,先进后出,入栈和出栈的时间复杂度是O(1);
实现链表的时候可以进行头插也可以进行尾插,呢么入栈是使用头插还是尾插?
1)如果入栈采用尾插法,那么时间复杂度就是O(N),因为尾插法每次都要找尾巴,出栈的时间复杂度就是O(1);
2)假设头插法入栈,那么时间复杂度就是O(1)
3)入栈采用头插法,出栈的时候只需要删除头节点即可,时间复杂度一定是O(1)
如果我非得想要用尾插法来实现入栈操作,我可以使用一个节点Last来进行记录每一次入栈时候的尾巴节点,但是此时又出现了问题;你出栈的时候,元素肯定要减少,你必须知道你当前记录的尾巴节点的前一个结点才可以进行删除出栈(此时单链表虽然最后一个节点我知道是谁,但是他的前一个结点我就不知道了,我们还需要遍历去找这个前一个结点的前区,此时的时间复杂度就又是O(N)勒
此时我们就需要使用双向链表来实现一个栈;
2.队列:Queue是一个普通的队列,Deque是一个双端队列
普通的队列:只能是队尾进,队头出;
双端队列:可以从队头进队尾出,也可以从队尾进,队头出,也可以用作一个栈;
下面我们来介绍一下Queue的实现方法
Queue queue=new LinkedList();
//1放元素
queue.add(1); offer()
queue.add(2);
//2获取队头元素
System.out.println(queue.peek());
System.out.println(queue.element());
//3出队列的元素
System.out.println(queue.poll());
System.out.println(queue.remove());
Deque queue=new LinkedList<>();
//queue.add(1);//默认是从队尾进入的 offerFirst
queue.addFirst(1);//默认是队头入队的
queue.addLast(2);//默认是从队头入队的 offerLast
queue.addFirst(3);
queue.addLast(4);
System.out.println(queue.peekFirst());
System.out.println(queue.peekLast());
//上面打印的结果是3,4
pollFirst() pollLast()//删除元素
getFirst() getLast() peekLast() peekFirst()//获取元素
add() offer() addFirst() addLast() offerFirst() offerLat()//新增元素
addFirst()和addLast()底层默认是调用LinkFirst(元素)和LinkLast(元素)
对于LinkedList,它不仅可以作为普通的队列,还可以作为双端队列,还可以作为双向链表(里面有一个头指针和一个尾指针),还可以作为栈来进行使用;
ArrayList是一个顺序存储,物理内存是连续的,逻辑上也是连续的;但是LinkedList在物理内存上面是不连续的
下面用一个单链表来实现一个队列
那么现在问题就来了?如果是单链表,哪边是队头,那便是队尾呢?
1)head是队头,tail是队尾,入队操作的时间复杂度是O(N)(每次都要从尾巴节点进行插入),出队的时间复杂度是O(1),那么这时只出队头元素就行了;
2)如果Head是队尾,tail是队头,才有头插法那么入队的时间复杂度是O(1),出队的时间复杂度是O(N)
3)现在以head为队头,tail为队尾,我们使用Last节点来进行指定链表的最后一个节点;此时入队列(尾插法)的时间复杂度是O(1),但是此时出队列,只需要出队头元素即可,时间复杂度也是O(1)
4)我们再进行新增节点的时候,分两种情况,第一次进行入队列的操作;和不是第一次入队列的操作;
在进行出队列的时候,我们还要进行判断一下当前队列是不是空;
class Node{
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
class MyQueue{
public Node head;
public Node tail;
public void offer(int data)
{ //创建一个新的节点
Node node=new Node(data);
if(head==null)
{
head=node;
tail=node;
}else{
tail.next=node;
tail=tail.next;
}
}
public boolean isEmpty()
{
return this.head==null;
}
public int pop()
{ //1判断对头是否为空
if(isEmpty())
{
throw new RuntimeException("此时队列时空");
}
//2只需队头出去即可
int data= head.data;
head=head.next;
return data;
}
public int peek()
{
return head.data;
}
}
3.设计循环队列
1)当新增元素的时候,让tail++,count++如果发现tail已经加到了数组的末尾,就将tail=0;
2)出循环队列的时候,让head++,count--如果此时发现了head已经减到了数组的末尾,就将head=0;
在这里面我们要注意一些点:当我们设置循环队列的时候,head==tail的时候,有两种情况
1)还没有进行放元素的时候
2)当整个循环队列的内容就已经满了
class MyCircularQueue {
private int[] arr1;
int count=0;
int head=0;
int tail=0;
public MyCircularQueue(int k) {
this.arr1=new int[k];
}
public boolean enQueue(int value) {
if(isFull())
{
return false;
}
arr1[tail]=value;
tail++;
count++;
if(tail==arr1.length)
{
tail=0;
}
return true;
}
public boolean deQueue() {
if(isEmpty())
{
return false;
}
head++;
if(head==arr1.length)
{
head=0;
}
count--;
return true;
}
public int Front() {
if(isEmpty())
{
return -1;
}
return arr1[head];
}
public int Rear() {
if(count==0)
{
return -1;
}
if(tail==0) return arr1[arr1.length-1];
return arr1[tail-1];
}
public boolean isEmpty() {
return count==0;
}
public boolean isFull() {
return count==arr1.length;
}
}
练习题1:用队列来实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
题解:栈先进后出的数据结构,队列是先进先出的数据结构
刚一开始进栈的时候,两个队列都是空的,所以先进哪一个都可以,我们此时就约定现金第1个吧;
1)每次入栈的时候都入到不为空的队列
2)出栈,一个不为空A队列的中的所有元素-1都出队列,放到另一个为空队列B里面,然后最后的出栈操作,只需要出队列A中的那一个元素即可
class MyStack{
private Queue queue1=null;
private Queue queue2=null;
public MyStack()
{
this.queue1=new LinkedList<>();
this.queue2=new LinkedList<>();
}
public void push(int data)
{
if(!queue1.isEmpty())
{
queue1.add(data);
}else if(!queue2.isEmpty())
{
queue2.add(data);
}else{
//这种情况下两个队列都是空队列,我们默认放到第一个队列当中
queue1.add(data);
}
}
public int pop()
{
if(!queue1.isEmpty())
{
int size=queue1.size();
for(int i=0;i
练习题2:用栈来实现队列
题解:我们使用两个栈来进行实现一个队列
我们入队列指定到入到S1这个栈
我们出队列指定到出S2这个栈,我们如果发现S2这个栈是空的,那么就把S1中的队列中的元素全部放到S2中,再进行出队列操作



