网站使用授权书,我想开网站,网站空间的控制面板首页,房产app平台有哪些理论基础
队列先入先出。 栈先入后出。 具体的实现和用法根据语言的不同而不同。
参考的文章
https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
232.用栈实现队列
这个定义入栈和出栈#xff0c;往队列中加入…理论基础
队列先入先出。 栈先入后出。 具体的实现和用法根据语言的不同而不同。
参考的文章
https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
232.用栈实现队列
这个定义入栈和出栈往队列中加入元素的时候就是栈中push操作一样出栈的时候首先看出栈是否为空如果不为空那么出栈pop如果出栈为空那么入栈中所有元素pop然后添加到出栈中。双栈实现队列 下面是C,JAVA和Python的实现。
class MyQueue {
public:stackint stIn;stackint stOut;MyQueue() {}void push(int x) {stIn.push(x);//队列中加入元素就直接入栈就好 }int pop() {//当出栈为空的时候再将入栈中的元素加入到出栈不会破坏他们的顺序if (stOut.empty()){//将stIn中的数据导入到stOutwhile(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}int result stOut.top();//获得元素值并且returnstOut.pop();return result;}int peek() {int res this-pop();//直接使用现有的函数stOut.push(res);//因为pop弹出元素所有push回去return res;}bool empty() {return stIn.empty() stOut.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();* bool param_4 obj-empty();*/class MyQueue {StackInteger stackIn;StackInteger stackOut;public MyQueue() {stackIn new Stack();//负责进栈JAVA必须new一个空间stackOut new Stack();//负责出栈}//入栈public void push(int x) {stackIn.push(x);//这个就是JAVA的栈}public int pop() {dumpstackIn();//后面自定义的一个函数这个就是判断出栈是否为空如果为空就将入栈中的所有元素导入到出栈return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() stackOut.isEmpty();}public void dumpstackIn(){if (!stackOut.isEmpty()) return;//如果出栈不为空就返回。之后正常pop和peek就可以while(!stackIn.isEmpty()){stackOut.push(stackIn.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();*/class MyQueue(object):def __init__(self):self.stack_in []self.stack_out []def push(self, x)::type x: int:rtype: None有新元素进来就往stack_in里面pushself.stack_in.append(x)def pop(self)::rtype: intif self.empty():return Noneif self.stack_out:return self.stack_out.pop()else:for i in range(len(self.stack_in)):self.stack_out.append(self.stack_in.pop())return self.stack_out.pop()def peek(self)::rtype: intans self.pop()self.stack_out.append(ans)return ansdef empty(self)::rtype: boolreturn not (self.stack_in or self.stack_out)# Your MyQueue object will be instantiated and called as such:
# obj MyQueue()
# obj.push(x)
# param_2 obj.pop()
# param_3 obj.peek()
# param_4 obj.empty()参考的文章
https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
225. 用队列实现栈
可以和上面方法相同使用两个队列表示栈也可以使用一个队列表示栈。一个队列就是往栈中加入元素就是队列的push弹出元素就是找到栈应该弹出的元素移动到队列的最开始然后pop。JAVA中有个实现是在加入元素的时候进行操作将队列的顺序变成栈的顺序弹出元素就是pop。 其中JAVA注释掉的没有按照queue来操作而是使用dequeue 下面是C,JAVA和Python的实现。
class MyStack {
public:queueint que;//MyStack() {}void push(int x) {que.push(x);}int pop() {int size que.size();size--;//弹出其中size-1个元素while(size--){//将队列头部元素除了最后一个元素外重新加到队列尾部que.push(que.front());//获得队列中的最前面的元素加入到队列que.pop();//然后弹出}int result que.front();//弹出的元素正好在队列最前面que.pop();return result;}int top() {return que.back(); }bool empty() {return que.empty();}
};/*** 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();* bool param_4 obj-empty();*/class MyStack {QueueInteger queue;public MyStack(){queue new LinkedList();}public void push(int x){//这个思路是在入栈的时候进行操作每次入栈新元素都调整现有的队列顺序与栈的出栈顺序相同queue.offer(x);//安全与add相比队列满的话会返回false不会阻塞等待队列有空间int size queue.size();//移动除了新加入的元素的其他元素while (size-- 1)queue.offer(queue.poll());}public int pop(){return queue.poll();}public int top() {return queue.peek();}public boolean empty(){return queue.isEmpty();}// DequeInteger deque;//deque是不是双向队列// public MyStack() {// deque new ArrayDeque();// }// public void push(int x) {// deque.addLast(x);//在最后加入// }// public int pop() {// //我感觉这个双向列表完成pop操作可以简化但是为了练习就是好像当作单向队列我这里还是当作双向队列// return deque.removeLast();// }// public int top() {// return deque.peekLast();// }// public boolean empty() {// return deque.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();*/from collections import deque
class MyStack(object):def __init__(self):self.que deque()def push(self, x)::type x: int:rtype: Noneself.que.append(x)def pop(self)::rtype: intif self.empty():return Nonefor i in range(len(self.que)-1):self.que.append(self.que.popleft())return self.que.popleft()def top(self)::rtype: intif self.empty():return Noneans self.pop()self.que.append(ans)return ansdef empty(self)::rtype: boolreturn not self.que# Your MyStack object will be instantiated and called as such:
# obj MyStack()
# obj.push(x)
# param_2 obj.pop()
# param_3 obj.top()
# param_4 obj.empty()参考的文章
https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
20. 有效的括号
栈的应用。 不匹配的情况三种1. 左括号多了 2. 右括号多了 3. 左右括号不匹配 Tips:就是如果遍历中遇到左括号就往栈中存储相对应的右括号。遇到右括号就进行判断如果栈为空就说明右括号多了输出false如果栈的top元素不等于当前的右括号就说明不匹配输出false其他情况就是说明匹配弹出相应的元素。如果遍历完字符串栈不为空就说明左括号多了输出fa;se否则就是左右括号匹配输出true。 下面是C,JAVA和Python的实现。
class Solution {
public:bool isValid(string s) {stackchar st;if(st.size()%2!0) return false;for(int i 0; i s.size(); i){//遍历字符串if(s[i]() st.push());else if(s[i]{) st.push(});else if(s[i][) st.push(]);else if (st.empty() || st.top()!s[i]) return false;else st.pop();}return st.empty();}
};class Solution {public boolean isValid(String s) {DequeCharacter deque new LinkedList();char ch;for(int i 0; i s.length(); i){ch s.charAt(i);//存储字符进行比较if(ch () deque.push());else if(ch () deque.push());else if(ch {) deque.push(});else if(ch [) deque.push(]);else if(deque.isEmpty() || deque.peek()!ch){return false;}else deque.pop();}return deque.isEmpty();}
}class Solution(object):def isValid(self, s)::type s: str:rtype: boolstack []for item in s:if item (:stack.append())elif item [:stack.append(])elif item {:stack.append(})elif not stack or stack[-1]!item:return Falseelse:stack.pop()return True if not stack else False 参考的文章
https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
1047. 删除字符串中的所有相邻重复项
栈的应用。与有效括号类似。 就是使用string类型变量实现栈的操作。定义string类型变量result。 如果result为空或者result的栈顶的元素与当前元素不匹配就将当前元素push到栈中。如果匹配就pop。遍历结束后输出result。 下面是C,JAVA和Python的实现。
class Solution {
public:string removeDuplicates(string S) {string result;for (char s: S){if(result.empty() || s!result.back()) result.push_back(s);else result.pop_back();}return result;}
};class Solution {public String removeDuplicates(String S) {ArrayDequeCharacter deque new ArrayDeque();char ch;for (int i 0; i S.length(); i){ch S.charAt(i);if(deque.isEmpty() || deque.peek() ! ch) deque.push(ch);else deque.pop();}String str ;while(!deque.isEmpty()){str deque.pop() str;}return str;}}class Solution(object):def removeDuplicates(self, s)::type s: str:rtype: strres list()for item in s:if res and res[-1] item:res.pop()else:res.append(item)return .join(res)参考的文章
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
