戳这里【总目录】回到算法系列总目录
一、栈
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。与数组相比有很多的类似之处，但是数组或链表对外暴露了太多的操作接口，灵活性的同时也容易误操作，变得不可控。当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应首选“栈”的数据结构。
栈的实现既可以用数组，也可以用链表。用数组实现的栈为顺序栈，用链表实现的栈为链式栈。不管基于数组还是链表，入栈、出栈的时间复杂度都为 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
网友评论