每周一篇算法02：栈与队列

戳这里【总目录】回到算法系列总目录

---

一、栈

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。与数组相比有很多的类似之处，但是数组或链表对外暴露了太多的操作接口，灵活性的同时也容易误操作，变得不可控。当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应首选“栈”的数据结构。

栈的实现既可以用数组，也可以用链表。用数组实现的栈为顺序栈，用链表实现的栈为链式栈。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。在java和go语言的stack类下，都是采用数组形式实现的栈结构。java栈的经典应用场景比如有：JVM函数计算时的线程栈，括号匹配以及浏览器。

1.JVM线程栈
java的计算编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

操作数栈和运算符栈

2.括号匹配
用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

3.浏览器
使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

二、队列

队列是一种可以实现“先进先出”的存储结构，队列跟栈非常相似，支持的操作也很有限。 主要为两个操作：入队（尾部入队），出队（头部出队） 。队列主要有三种：循环队列、阻塞队列和并发队列。主要说一下后两者。

java中非阻塞队列抽象的公共方法：

• add(E e)：将元素e插入到队列末尾，如果插入成功，则返回true；如果插入失败（即队列已满），则会抛出异常；
• remove()：移除队首元素，若移除成功，则返回true；如果移除失败（队列为空），则会抛出异常；
• offer(E e)：将元素e插入到队列末尾，如果插入成功，则返回true；如果插入失败（即队列已满），则返回false；
• poll()：移除并获取队首元素，若成功，则返回队首元素；否则返回null；
• peek()：获取队首元素，若成功，则返回队首元素；否则返回null

阻塞队列是在队列基础上增加了阻塞操作，在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

阻塞队列提供的方法，所呈现的结果和非阻塞有很大的差别：

• put(E e)：put方法用来向队尾存入元素，如果队列满，则等待；
• take()：take方法用来从队首取元素，如果队列为空，则等待；
• offer(E e,long timeout, TimeUnit unit)：offer方法用来向队尾存入元素，如果队列满，则等待一定的时间，当时间期限达到时，如果还没有插入成功，则返回false；否则返回true；
• poll(long timeout, TimeUnit unit)：poll方法用来从队首取元素，如果队列空，则等待一定的时间，当时间期限达到时，如果取到，则返回null；否则返回取得的元素；

三、算法考察

1.线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。那如何存储排队的请求呢？

• 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，链式队列的线程池不适合响应时间敏感的系统。

• 而基于数组实现的有界队列（bounded queue），队列的大小有限，当线程池中排队的请求超过队列大小时，后面的请求就会被拒绝，这种方式对响应时间敏感的系统来说，会更加合理。不过，需要平衡好队列的大小，队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

2.括号匹配
【LetCode括号匹配原题-Valid Parentheses】：给定一个只包含'('，')'，'{'，'}'，'['和']'的字符串，判断字符串是否有效。有效的条件为：括号必须有相同的括号对应， 且括号必须以正确的顺序对应。

解题思路：遍历字符串每个字符，当字符属于'('，'{'，'['时，将字符压入栈。若字符不属于，则将当前字符与栈顶元素比较，如果括号对应说明正确并弹出栈顶元素，否则返回错误。

func main(){
    str :=string("{[)]}")
    result := isValidOp(str)
    fmt.Printf("the result is:%v",result)
}

//采用切片实现栈操作
func isValid(s string) bool {
    brackets := map[rune]rune{')': '(', ']': '[', '}': '{'}
    var stack []rune

    for _, char := range s {
        fmt.Println(reflect.TypeOf(char))
        if char == '(' || char == '{' || char == '[' {
            // 入栈
            stack = append(stack, char)
            // 循环中，stack不能为空
        } else if len(stack) > 0 && brackets[char] == stack[len(stack) - 1] {
            // 栈中有数据，且此元素与栈尾元素相同
            stack = stack[:len(stack) - 1]
        } else {
            return false
        }
    }
    // 循环结束，栈中还有数据则 false
    return len(stack) == 0
}

//采用golang中list包实现栈操作
func isValidOp(s string) bool {
    brackets := map[rune]rune{')': '(', ']': '[', '}': '{'}
    stack := list.New()
    for _, char := range s {
        fmt.Println(reflect.TypeOf(char))
        if char == '(' || char == '{' || char == '[' {
            // 入栈
            stack.PushBack(char)
            // 循环中，stack不能为空且此元素与栈尾元素相同
        } else if stack.Len() > 0 && brackets[char] == stack.Back().Value {
            //出栈
            stack.Remove(stack.Back())
        } else {
            return false
        }
    }
    // 循环结束，栈中还有数据则 false
    return stack.Len() == 0
}

3. 链式栈的实现，这里还是采用go语言实现

//栈-先进后出，像电梯
type Stack struct {
    size int64 //容量
    top  int64 //栈顶
    data []interface{}
}

func MakeStack(size int64) Stack {
    q := Stack{}
    q.size = size
    q.data = make([]interface{}, size)
    return q
}

//入栈，栈顶升高
func (t *Stack) Push(element interface{}) bool {
    if t.IsFull() {
        log.Printf("栈已满，无法完成入栈")
        return false
    }
    t.data[t.top] = element
    t.top++
    return true
}

//出栈，栈顶下降
func (t *Stack) Pop() (r interface{}, err error) {
    if t.IsEmpty() {
        err = fmt.Errorf("栈已满，无法完成入栈")
        log.Println("栈已满，无法完成入栈")
        return
    }
    t.top--
    r = t.data[t.top]
    return
}

//栈长度, 已有容量的长度
func (t *Stack) StackLength() int64 {
    return t.top
}

//清空, 不需要清空值 ，再入栈，覆盖即可
func (t *Stack) Clear() {
    t.top = 0
}

//判空
func (t *Stack) IsEmpty() bool {
    return t.top == 0
}

//判满
func (t *Stack) IsFull() bool {
    return t.top == t.size
}

//遍历
func (t *Stack) Traverse(fn func(node interface{}), isTop2Bottom bool) {
    if isTop2Bottom {
        var i int64 = 0
        for ; i < t.top; i++ {
            fn(t.data[i])
        }
    } else {
        for i := t.top - 1; i >= 0; i-- {
            fn(t.data[i])
        }
    }
}

当然go语言本身已经提供了很好的容器工具包，在list包下已经封装了栈和队列的操作方法，使用方式也较为简单，可以参考该文：Go用list实现stack和queue