做网站会很忙吗,网站支付怎么做的,建设工程施工合同协议书,centos 6.5 搭建wordpress232 用栈实现队列
题目描述 两个栈模拟队列的思路是利用栈#xff08;后进先出结构#xff09;的特性来实现队列#xff08;先进先出结构#xff09;的行为。这种方法依赖于两个栈来逆转元素的入队和出队顺序#xff0c;从而实现队列的功能。
入队操作#xff08;使用s…232 用栈实现队列
题目描述 两个栈模拟队列的思路是利用栈后进先出结构的特性来实现队列先进先出结构的行为。这种方法依赖于两个栈来逆转元素的入队和出队顺序从而实现队列的功能。
入队操作使用stackIn所有新加入的元素都直接推入stackIn。因为栈支持后进先出所以此时不需要考虑元素的顺序。
出队操作使用stackOut当需要进行出队操作即移除队列的最前端元素时我们先检查stackOut如果stackOut为空则将stackIn中所有元素逐一弹出并推入stackOut。这样最先进入stackIn的元素也就是最早入队的元素会位于stackOut的顶部。如果stackOut不为空则直接从stackOut弹出顶部元素队列的前端元素。
通过这种方式stackOut的栈顶始终保持为队列的最前端而stackIn用于处理新的入队操作。
class MyQueue {StackInteger stackIn;StackInteger stackOut;public MyQueue() {stackIn new Stack();stackOut new Stack();}public void push(int x) {stackIn.push(x);}public int pop() {// 将in栈的内容全部转移到out栈从out栈进行输出// 如果out栈有内容就先输出if(stackOut.empty()){while(!stackIn.empty()){stackOut.push(stackIn.pop());}}return stackOut.pop();}public int peek() {if(stackOut.empty()){while(!stackIn.empty()){stackOut.push(stackIn.pop());}}return stackOut.peek();}public boolean empty() {return (stackIn.empty())(stackOut.empty());}
}/*** 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();*/225 用队列实现栈
题目链接 这题也是利用两个队列来进行元素顺序的调整。
queue2是辅助队列queue1存放进入栈的元素当想要得到栈顶队尾元素即把queue1的元素放入queue2知道queue1只剩一个元素该元素则为栈顶元素。将其弹出即可。剩余操作也是类似。
class MyStack {QueueInteger queue1;QueueInteger queue2;public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}public void push(int x) {queue2.offer(x); // 先放在辅助队列中while (!queue1.isEmpty()){queue2.offer(queue1.poll());}QueueInteger queueTemp;queueTemp queue1;queue1 queue2;queue2 queueTemp; // 最后交换queue1和queue2将元素都放到queue1中}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll(); // 因为queue1中的元素和栈中的保持一致所以这个和下面两个的操作只看queue1即可}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}/*** 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();*/python版本
from queue import Queueclass MyStack:def __init__(self):self.queue1 Queue()def push(self, x):# 临时队列用于转移元素temp_queue Queue()temp_queue.put(x) # 先放入新元素栈顶元素# 将原队列中的元素转移到临时队列中确保新元素始终在队列头部while not self.queue1.empty():temp_queue.put(self.queue1.get())self.queue1 temp_queue # 更新队列为新的队列def pop(self):# 直接从 queue1 中取出元素因为 queue1 的队头是栈顶return self.queue1.get()def top(self):# 获取队头元素即栈顶元素top_element self.queue1.get()# 为保持队列状态将该元素重新放回队头temp_queue Queue()temp_queue.put(top_element)while not self.queue1.empty():temp_queue.put(self.queue1.get())self.queue1 temp_queue # 更新队列return top_elementdef empty(self):# 如果 queue1 为空则栈为空return self.queue1.empty()20 有效的括号
题目描述 很经典的栈的题目。
如果遇到左括号则要入栈遇到右括号则与栈顶的元素配对配对失败则是false反之继续配对。这里要特别注意右括号来的适合左括号可能为空这是false。或者最后左括号剩余这也是false。
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();for(int i0; is.length(); i){char tmp s.charAt(i);if (tmp ( || tmp { || tmp [) {stack.push(tmp);} else {if (stack.empty()) return false; // 先检查栈是否为空char top stack.pop(); // 弹出栈顶元素以匹配if (tmp ) top ! () return false;if (tmp } top ! {) return false;if (tmp ] top ! [) return false;}}return stack.empty();}
}python版本
class Solution:def isValid(self, s: str) - bool:stack []for char in s:if char in ({[:stack.append(char)else:if not stack:return False # 检查栈是否为空top stack.pop() # 弹出栈顶元素以匹配if char ) and top ! (:return Falseif char } and top ! {:return Falseif char ] and top ! [:return Falsereturn not stack # 栈空则有效非空则无效当然这题也可以用setmap进行查找的优化但意义不太大。比如如下代码 import java.util.HashMap;
import java.util.Stack;public class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();HashMapCharacter, Character map new HashMap();// 存储括号对应关系map.put(), ();map.put(}, {);map.put(], [);for (int i 0; i s.length(); i) {char c s.charAt(i);// 如果是右括号if (map.containsKey(c)) {// 栈为空或栈顶元素不匹配当前右括号对应的左括号if (stack.isEmpty() || stack.pop() ! map.get(c)) {return false;}} else {// 否则为左括号压入栈中stack.push(c);}}// 如果栈为空说明所有括号都匹配成功return stack.isEmpty();}
}1047 删除字符串中的所有相邻重复项
题目链接 第一眼还以为要双指针或者滑动窗口但并不用双指针往往是对数组/字符串/链表进行操作滑动窗口则是找子序列/最大长度这种。
这题实际上就是栈的应用没遇到一个新元素就入栈如果栈顶元素与新的元素相同则把栈顶元素出栈以此类推。
关于java的StringBuider看这篇链接
class Solution {public String removeDuplicates(String s) {StackCharacter stack new Stack();for(int i0; is.length(); i){char tmp s.charAt(i);if(!stack.isEmpty() stack.peek()tmp){stack.pop();}else{stack.push(tmp);}}StringBuilder res new StringBuilder();for (char ch : stack) {res.append(ch);}return res.toString();}
}python版本join可以方便的把列表转换为字符串。如果不用join那会浪费一些时间。
class Solution:def removeDuplicates(self, s: str) - str:stack []for char in s:if stack and stack[-1] char:stack.pop()else:stack.append(char)return .join(stack)#或者这样res for c in stack:res res creturn res150 逆波兰表达式求值
题目链接 题目很简单如果了解后缀表达式很轻松能写出来将数字存在栈中遇到符号取出栈顶的2个元素计算再将结果放回栈内即可。
class Solution {public int evalRPN(String[] tokens) {StackInteger stack new Stack();for (String token : tokens) {if (token.equals() || token.equals(-) || token.equals(*) || token.equals(/)) {int b stack.pop(); // 先弹出的是第二个操作数int a stack.pop(); // 再弹出的是第一个操作数switch (token) {case :stack.push(a b);break;case -:stack.push(a - b);break;case *:stack.push(a * b);break;case /:stack.push(a / b);break;}} else {// 直接将字符串转换为整数并压栈stack.push(Integer.parseInt(token));}}// 最终栈顶元素就是表达式的结果return stack.peek();}
}python版本
class Solution:def evalRPN(self, tokens: List[str]) - int:res []print(int(6/(-132)))for token in tokens:if token not in {, -, *, /}:res.append(int(token))else:a res.pop()b res.pop()if token :res.append(ab)elif token -:res.append(b-a)elif token *:res.append(a*b)elif token /:res.append(int(b/a))return res[0]在Python中对于整数除法/ 操作符执行的是真除法返回浮点结果而 // 操作符执行的是地板除即对结果向下取整到最近的整数。因此当使用 / 并将结果强制转换为 int 时它只是简单地去掉了小数部分不进行四舍五入而且对于负数结果也只是截断小数部分。而使用 //则是在计算结果后直接返回一个整数且结果总是向下取整这种方式与C和Java中的整数除法一致。
对于正数除法
5 / 2 结果为 2.5int(5 / 2) 结果为 25 // 2 结果为 2。
对于负数除法
-5 / 2 结果为 -2.5int(-5 / 2) 结果为 -2。-5 // 2 结果为 -3因为 -2.5 向下取整是 -3。
因此这里要使用转换为int而不是//。
