一.简介
栈是一种特殊操作规则的数据结构-后进先出(FIFO),这也是栈的最重要的一个特点,栈又叫堆栈(Stack),栈有两个操作一个进栈(Push),另一个出栈(Pop)。
二.示例
2.1 有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
空字符串可被认为是有效字符串。
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
//标记匹配成对的字符串
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
//存储括号前缀
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
//
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
复制代码
2.2 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(push、pop、peek、empty)
实现 MyQueue 类
说明
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
public class MyQueue {
//存储压栈的
Stack<Integer> s1= new Stack<>();
//处理弹栈
Stack<Integer> s2= new Stack<>();
int front = 0;
//
public void push(int x) {
if(s1.isEmpty()) front = x;
s1.push(x);
}
//把存储在s1数据都取出,压人获取队列的顺序
public int pop() {
if(s2.isEmpty()){
while (!s1.isEmpty()){
s2.push(s1.pop());
}
}
//弹栈并移除数据
return s2.pop();
}
//弹栈数据,不移除
public int peek() {
if(!s2.isEmpty()){
return s2.peek();
}
return front;
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
复制代码
参考
https://leetcode-cn.com/problems/implement-queue-using-stacks/
https://leetcode-cn.com/problems/valid-parentheses/
评论