网站开发需求书模板,什么是主机托管,网站怎么做宣传,wordpress 防站教程栈和队列理论基础
抽象认识
栈是先进后出(FIFO)#xff0c;队列是先进先出(LIFO) 队首(先进))队尾(后进)栈顶(后进)栈底(先进) 栈(Stack) 只在一端进行进出操作(只在一端进一端出)像个篮球框#xff0c;取用篮球从一端进出。 /进栈
int a[1000];//足够大的栈空间
int top-1…栈和队列理论基础
抽象认识
栈是先进后出(FIFO)队列是先进先出(LIFO) 队首(先进))队尾(后进)栈顶(后进)栈底(先进) 栈(Stack) 只在一端进行进出操作(只在一端进一端出)像个篮球框取用篮球从一端进出。 /进栈
int a[1000];//足够大的栈空间
int top-1;//栈的初始化栈顶位置标记
for(i0;i10;i){a[top]i;//先对top1再录入位置使用top为了防止最后一次循环赋值后top依旧进行1,使得top指向了栈外的空数组。
}
/出栈
for(i0;i10;i){
print(%d,a[top--]);}队列(Queue) 在两端分别进行进和出的操作(一端进一端出)食堂排队从后面排队前面买饭离开。 //QQ号有10个数字的排列排序为奇数的数字取出排列排序为偶数的数字放入队尾重新报号组成QQ号。
int a[100]{1,2,3,4,5,6,7,8,9,0},head,tail;
//队头队尾
head0;
tail10;//标记的是最后一个元素后面的空元素
while(headtail){printf(%d,a[head]);//奇数离开队伍head;a[tail]a[head];//偶数放在队尾tail;//补长队尾head;//减少队头}
JAVA中的栈和队列
栈(Stack) Stack类位于java.util包中 基本操作 push(E item):将元素压入栈顶。pop():移除并返回栈顶的元素。peek():查看栈顶的元素但不移除。isEmpty():判断栈是否为空。 低层实现基于一个动态数组(Vector)来实现的和C类似可以通过扩展Vector来管理栈中的元素。 队列(Queue) Queue接口 常见的实现类 LinkedList:提供队列的标准实现PriorityQueue:优先队列根据元素的优先级顺序出队。ArrayDeque:基于数组的双端队列。 基础操作 add(E e):将元素添加到队尾remove():移除并返回队首的元素peek():查看队首的元素但不移除。isEmpty():判断队列是否为空 底层实现默认的队列实现是LinkedList基于双向链表来实现队列的入队和出队操作。ArrayDeque是基于数组的实现通常性能更好。
几个问题
Java中的Stack是容器吗 是Stack是一个继承自vector类的容器。vector是一个可动态扩展的数组实现了List接口。Stack类本身是一个容器类提供了栈(LIFO)操作由于 Stack 继承自 Vector所以它本质上也继承了 Vector 的所有特性包括动态调整大小和随机访问等。然而Stack 主要用来模拟栈的行为提供了栈特有的操作但并不暴露所有 Vector 提供的操作。 我们使用的stack是属于什么 JAVA标准库(JDK)位于java.utilstack类是继承自Vector的一个类设计用于支持栈(LIFO)行为。 JAVA的stack是如何实现的 Stack是通过继承Vector类来实现的。Vector是一个动态数组可以自动扩展它的容量。Stack通过push()和pop()方法来操作Vector中的元素以实现栈的LIFO行为。 stack提供迭代器来遍历stack空间吗 是的但不推荐使用。Stack提供了iterator()方法来获取一个迭代器从而遍历栈中的元素、但是不符合栈的设计哲学因为栈是符合先进后出原则允许迭代器遍历栈中 元素会破坏这一原则。由于栈的特性只允许访问栈顶元素允许迭代的做法违背了栈的设计原则因此并不推荐使用Stack类推荐使用Deque(双端队列)或ArrayDeque来代替Stack这些类支持栈和队列的操作并且不会提供队元素的遍历行为。 在java中没有缺省容器的概念栈类和队列类都是固定的不能更换低层容易Java中的Stack类的底层实现是固定的。
232.用栈实现队列
题目
https://leetcode.cn/problems/implement-queue-using-stacks/description/
使用栈实现队列的下列操作
push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作。
思路 思路 用****2个栈(入栈)****来改变出栈顺序 入栈要全部放在出栈里模拟队列的行为如果出栈是空的队列是先进先出栈是先进后出那么就让数先入栈再将入栈的数移动到出栈里开口不变。 如果要弹出看看出栈是否为空如果为空把所有元素加倒出栈里。 代码思路 写清各个接口的返回类型初始化入栈和出栈类创建入栈和出战的对象。 class MyQueue{//声明入栈和出栈StackInteger stackIn;StackInteger stackOut;//Initialize public MyQueue(){stackInnew Stack();stackOutnew Stack();}//将一个元素放入队列的尾部public void push(int x){stackIn.push(x);//队列从入栈进入}//从队列首部移除元素public int pop(){//队列中的先进先出就是取出一个元素并返回它。dumpstackIn();//在出栈放入栈pop出来的数return stackOut.pop();//弹出(移除)再返回值}//返回队列首部的元素public int peek(){dumpstackIn();return stackOut.peek();//返回栈顶但不移除它。}//返回队列是否为空public boolean empty(){return stackIn.isEmpty()stackOut.isEmpty();}private void dumpstackIn(){if(!stackOut.isEmpty()) return;//如果出栈不是空的那就返回不用执行while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());//放入栈pop出来的数}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj new MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* boolean param_4 obj.empty();*/总结
声明入栈和出栈 Stack Integer stackIn; Stack Integer stackOut;创建入栈和出栈的对象stackInnew Stack();stackOutnew Stack();return stackOut.peek();//默认返回栈顶但不移除它
225.用队列实现栈
题目
https://leetcode.cn/problems/implement-stack-using-queues/description/
https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
【惯性思维用两个队列来模拟栈其实只用一个队列就可以模拟栈了】
使用队列实现栈的下列操作
push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的例如, 对一个空的栈不会调用 pop 或者 top 操作【单向队列】
思路
我的思路 队列是先进先出我们让它先进后出改变出口方向每当队列满了之后从列尾出去 Karl思路 队列是先进先出的顺序如果用两个队列将一个队列移动到另一个队列中时先进先出的顺序还是没有改变。栈pop的是栈顶元素(后进)队列pop的是队首我们让栈顶元素(后进)元素pop到栈尾假设栈有n个元素每次让栈的栈底元素pop出来需要将前n-1个元素放入到栈底后面。 代码class MyStack {QueueInteger queue;//Queue是个接口public MyStack() {queuenew LinkedList();//LinkedList是Queue的一个实现类 }public void push(int x) {queue.add(x);//将元素添加到队尾相当于栈整体移动到队列了 }public int pop() {rePosition();return queue.poll();//移除并返回栈首元素}public int top() {rePosition();int resultqueue.poll();//先移除队首(实际是之前的队尾即后进)queue.add(result);//后进在栈顶返回return result;}public boolean empty() {return queue.isEmpty();}//将队列前面的元素加入到队列末尾public void rePosition(){int sizequeue.size();size--;//需要将size-1个元素移动到队尾while(size--0)//在每次循环后将size-1,只要size0就继续queue.add(queue.poll());//移除并返回队首元素知道前size-1个元素全部返回}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* boolean param_4 obj.empty();*/总结
size()和length的使用范围 size()是方法length是属性size():用于动态大小的集合类Map的键值对数量length:固定长度的数组字符串 注意事项 接口和实现类 Queue Integer queue;//Queue是个接口queuenew LinkedList();//LinkedList是Queue的一个实现类 queue的一些用法 queue.add(x) 将元素加入队尾queue.poll() 移除并返回队首元素 top()方法需要多练习很绕。
20.有效的括号
题目
https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”输出: true
示例 2:
输入: “()[]{}”输出: true
示例 3:
输入: “(]”输出: false
示例 4:
输入: “([)]”输出: false
示例 5:
输入: “{[]}”输出: true
思路
我的思路 思路很混乱怎么能在栈和队列中实现这些 Carl 三种不匹配的情况 字符串里的左方向的括号多余了不匹配。括号没有多余但是括号的类型没有匹配上。右方向的括号多余了不匹配 代码思路 如果是奇数一定可以发现不匹配字符。for循环 if 遇到(在栈中加)提前准备比较匹配 else if { 在栈中加}elseif [,在栈中加] 【情况23】elseif 栈空(情况3)||不匹配(情况2) return false;相等情况弹出。【情况1】 遍历到最后一个了如果不是空栈return false; 代码class Solution {public boolean isValid(String s) {DequeCharacter dequenew LinkedList();//声明并创建实例char ch;for(int i0;is.length();i){chs.charAt(i);//提前匹配if(ch(){deque.push());}else if(ch{){deque.push(});}else if(ch[){deque.push(]);}else if(deque.isEmpty()||deque.peek()!ch){ //情况23return false;}else{//如果是右括号判断是否和栈顶元素匹配deque.pop();}}return deque.isEmpty();}
}总结
string要转换为char才能比较注意情况23先判断栈空【情况3】
1047.删除字符串中的所有相邻重复项
题目
https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例
输入“abbaca”输出“ca”解释例如在 “abbaca” 中我们可以删除 “bb” 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”其中又只有 “aa” 可以执行重复项删除操作所以最后的字符串为 “ca”。
提示
1 S.length 20000S 仅由小写英文字母组成。
【栈的经典应用栈喜欢做这种消除的操作栈帮助记录了遍历数组当前元素的时候前一个元素是什么】
思路
我的思路 难点删除完bb后aa又靠近了。迭代。每遍历一个元素 如果有前一个元素把他的前一个元素储push在栈中。 比较它和前一个元素如果匹配就删除字符串里的这个元素和前一个元素不匹配就pop。 else if continue. Carl思路 消消乐 if 栈是空的||不匹配那么放入当前元素else if 消除 pop弹出最后要把栈中的字符串翻转过来 代码class Solution {public String removeDuplicates(String s) {ArrayDequeCharacter dequenew ArrayDeque();char ch;for(int i0;is.length();i){chs.charAt(i);//如果栈空或不匹配栈顶if(deque.isEmpty()||deque.peek()!ch){deque.push(ch);}else{//匹配就删掉deque.pop();}}String str;//剩余的元素while(!deque.isEmpty()){//全pop出去strdeque.pop()str;//先pop出去的放在前面恢复正序}return str;}
}总结 ArrayDeque 是JAVA中的双端队列数据结构既可以用作栈也可以用做队列 栈 push()pop() 队列 add()poll() //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点//参考https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist低级错误chs.charAt(i); 里面是string s 的第i个而不是直接chs.charAt(s);
