算法day09-栈与队列（1）
目录[*]力扣232. 用栈实现队列
[*]力扣225. 用队列实现栈
[*]力扣20. 有效的括号
[*]力扣1047. 删除字符串中的所有相邻重复项
一、用栈实现队列
主要思路：我们使用两个栈来实现一个队列的功能：其中一个作为输入栈，用于接收通过 push 操作传入的数据；另一个作为输出栈，专门用于处理 pop 和 peek 操作。当需要执行 pop 或 peek 时，如果输出栈为空，我们就将输入栈中的所有元素依次弹出，并按顺序压入输出栈。这样一来，输出栈的栈顶元素就对应了队列的队首，实现了先进先出的队列行为。
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
//初始化两个栈
inStack = new ArrayDeque<Integer>();
outStack = new ArrayDeque<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if(outStack.isEmpty()){ //当辅助栈里面镁元素时，要把入栈的元素倒压进出栈
in2out();
}
return outStack.pop();
}
public int peek() {
if(outStack.isEmpty()){
in2out();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
public void in2out(){
while(!inStack.isEmpty()){
outStack.push(inStack.pop()); //把入栈的元素压进出栈
}
}
}
//时间复杂度：O(1)
//空间复杂度：O(N)二、用队列实现栈
主要思路：这里可以用两个队列来实现一个栈。首先我们定义两个队列，一个用作辅助。当我们push一个元素时，先将元素放到队列2中，然后将队列 1的所有元素出队加到队列2的末尾，然后再将队列2的所有元素出队放到队列1中。这样可以确保每次入栈操作都确保队列1的前端为栈顶元素，出栈和获得栈顶元素操作都可以简单实现。
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
public void push(int x) {
queue2.offer(x);
while(!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
//交换queue1和queue2的元素
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
//时间复杂度：O(n）入栈，O（1）：出栈、查看队首元素、判断为空
//空间复杂度：O(N) 方法二：用一个队列也可以实现栈。只需要修改：在每次入栈的时候，先统计此时队列的长度，然后将元素加入到队列的尾部，然后把本来有的几个元素都从对头弹出并从队尾压入，这样就能保持每次push 的元素都在最开头。
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}三、有效的括号
主要思路：首先用一个哈希表记录右-左括号匹配对，然后去遍历输入的字符串，当前字符若是左括号则直接压入栈，若是右括号则进行判断：若栈为空，或者这个右括号与此时栈顶元素不匹配，则说明此字符串不是有效括号字符串。否则弹出字符。
class Solution { public boolean isValid(String s) { int n = s.length(); if( n % 2 == 1 ){ //如果长度为奇数，则一定不能匹配 return false; } Map map = new HashMap(); map.put(')', '('); map.put(']', '['); map.put('}', '{'); Deque stack = new ArrayDeque(); for(int i=0; i
页:
[1]