写点什么

精选算法面试 - 栈

用户头像
李孟
关注
发布于: 2021 年 01 月 10 日
精选算法面试-栈

一.简介

栈是一种特殊操作规则的数据结构-后进先出(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 类

  • void push(int x) 将元素 x 推到队列的末尾

  • int pop() 从队列的开头移除并返回元素

  • int peek() 返回队列开头的元素

  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明

  • 你只能使用标准的栈操作 —— 也就是只有 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/

用户头像

李孟

关注

还未添加个人签名 2017.10.18 加入

数据工程师 https://limeng.blog.csdn.net/

评论

发布
暂无评论
精选算法面试-栈