算法：栈和队列-实战
实战的题目都是leetcode的题。
leetcode:20有效的括号
解题思路
既然文章的标题都说了是栈和队列了，那我们仔细想，题目的意思就是相聚的（）要两两配对，是否全部都可以完全配对，就像我们有编辑器写代码的时候，我们用的{ }括号，编辑器又是怎么帮我们匹配上的。就比如（{}）这个是怎么配对的， 先{} 配对成功，先去除{} ，那么剩下的就是（） 再配对最后一堆括号。
根据这个配对规则，很容易想到是用栈。先进后出的顺序，依此匹配完成。
第一种方法：使用栈
class Solution {
public boolean isValid(String s) {
Map<String, String> map = new HashMap<String, String>();
Stack stack = new Stack();
map.put(")","("); //把右括号设置为KEY，更方便匹配
map.put("}","{");
map.put("]","[");
char num[] = s.toCharArray();
for (int i = 0 ; i < num.length ; i++) {
String str = String.valueOf(num[i]);
if (map.get(str) == null) { //假如左括号就存入栈，右括号匹配栈
stack.push(str);
}else if (stack.empty() || !map.get(str).equals(stack.pop())){ //栈是否为空，右边括号是否等于出栈的第一个。
return false;
}
}
return stack.empty();
}
}第二种方法，实现栈的方式？？
栈是怎么实现的呢，栈是通过数组实现的，不知道的可以看这里，so，第二种方法是用数组。
public boolean isValid(String s) {
char[] array = new char[s.length()]; //相当栈的作用
int top = 0; //数组下标
for (char a : s.toCharArray()) {
if (a == '(') { //判断是否等于左边
array[top++] = (char) (a + 1); //把左括号转变为右括号
} else if (a == '{' || a == '[') {
array[top++] = (char) (a + 2);
} else if (top == 0 || a != array[--top]) {//数组是否为空，是否等于右括号
return false;
}
}
return top == 0;
}栈的底层是数组，所以这种数组实现方式是特别快的。
leetcode:232用栈实现队列
解题思路
栈是先入后出的，队列是先入先出的，那么这两个怎么转变呢？ 其实题目讲的很明白，你不能改变一个栈的内容，所以你只能使用多个栈去模拟队列，那要怎么做，我做了一张简图。
第一种方法：出队容易，入队难
//出队容易，入队难，每次入队后，都把栈整理为方便输出形式
Stack<Integer> inputStack, outputStack;
/** Initialize your data structure here. */
public MyQueue() {
inputStack = new Stack<>();
outputStack = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
while (!outputStack.isEmpty()) {
inputStack.push(outputStack.pop());
}
inputStack.push(x);
while (!inputStack.isEmpty()) {
outputStack.push(inputStack.pop());
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
return outputStack.pop();
}
/** Get the front element. */
public int peek() {
return outputStack.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return outputStack.isEmpty();
}第二种方法：入队容易，出队难
//不管入队还是出队，每次操作后都保存入队状态
Stack<Integer> s1, s2;
/** Initialize your data structure here. */
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
if (s1.isEmpty() && s2.isEmpty()) {
s1.push(x);
}
else if (s1.isEmpty()) {
s2.push(x);
}
else {
s1.push(x);
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
int output;
if (!s1.isEmpty()) {
while (!s1.isEmpty()){
s2.push(s1.pop());
}
output = s2.pop();
while (!s2.isEmpty()){
s1.push(s2.pop());
}
}
else {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
output = s1.pop();
while (!s1.isEmpty()){
s2.push(s1.pop());
}
}
return output;
}
/** Get the front element. */
public int peek() {
int output;
if (!s1.isEmpty()) {
while (!s1.isEmpty()){
s2.push(s1.pop());
}
output = s2.peek();
while (!s2.isEmpty()){
s1.push(s2.pop());
}
}
else {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
output = s1.peek();
while (!s1.isEmpty()){
s2.push(s1.pop());
}
}
return output;
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/07/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
