一.简介
栈是一种特殊操作规则的数据结构-后进先出（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/
评论