单链表

todo AcWing 826. 单链表

双链表

todo AcWing 827. 双链表

栈

AcWing 828. 模拟栈

package main

import (
	"bufio" // io
	"fmt"
	"os" // io
)

func _debug() {
	stk := []int{}

	n := ri()

	for i := 0; i < n; i++ {
		op := string(rs())

		if op == "push" {
			x := ri()
			stk = append(stk, x)
		} else if op == "pop" {
			stk = stk[:len(stk)-1]
		} else if op == "empty" {
			if len(stk) != 0 {
				fmt.Fprintln(out, "NO")
			} else {
				fmt.Fprintln(out, "YES")
			}
		} else if op == "query" {
			fmt.Fprintln(out, stk[len(stk)-1])
		}
	}
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

const eof = 0

var (
	in  *bufio.Scanner
	out *bufio.Writer

	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB
)

// 读一个仅包含小写字母的字符串
func rs() (s []byte) {
	b := rc()
	for ; 'a' > b || b > 'z'; b = rc() { // 'A' 'Z'
	}
	for ; 'a' <= b && b <= 'z'; b = rc() { // 'A' 'Z'
		s = append(s, b)
	}
	return
}

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

// suggest
func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

// ===== ===== fast io ===== =====

func main() {
	// ===== ===== fast io ===== =====
	in = bufio.NewScanner(os.Stdin)
	// in.Split(bufio.ScanWords) // 分割
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

AcWing 3302. 表达式求值

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func _debug() {
	var s string
	fmt.Fscan(in, &s)

	fmt.Fprintln(out, backCalc(mid2back(s)))
}

// 中缀转后缀
func mid2back(s string) []string {
	priority := func(x byte) int {
		if x == '*' || x == '/' {
			return 2
		} else if x == '+' || x == '-' {
			return 1
		}
		return 0
	}

	stk := []byte{}
	ans := []string{}
	for i := 0; i < len(s); i++ {
		if s[i] >= '0' && s[i] <= '9' { // 数字直接输出 处理多位数字
			var j int
			for j = i; j < len(s) && s[j] >= '0' && s[j] <= '9'; j++ {
			}
			ans = append(ans, s[i:j])
			i = j - 1
		} else if s[i] == '(' {
			stk = append(stk, s[i])
		} else if s[i] == ')' {
			for len(stk) > 0 && stk[len(stk)-1] != '(' {
				ans = append(ans, string(stk[len(stk)-1]))
				stk = stk[:len(stk)-1]
			}
			stk = stk[:len(stk)-1]
		} else { // 运算符 要判断优先级
			// 只要栈顶 符号的优先级不低于新符号，就不断取出栈顶并输出
			for len(stk) > 0 && priority(stk[len(stk)-1]) >= priority(s[i]) {
				ans = append(ans, string(stk[len(stk)-1]))
				stk = stk[:len(stk)-1]
			}
			stk = append(stk, s[i])
		}
	}
	for len(stk) > 0 {
		ans = append(ans, string(stk[len(stk)-1]))
		stk = stk[:len(stk)-1]
	}
	return ans
}

// 后缀计算
func backCalc(s []string) (ans int) {
	op := func(b, a int, x string) int {
		if x == "+" {
			return b + a
		} else if x == "-" {
			return b - a
		} else if x == "*" {
			return b * a
		} else if x == "/" {
			return b / a
		}
		return -1 << 31
	}

	stk := []int{}
	for _, x := range s {
		if x == "+" || x == "-" || x == "*" || x == "/" {
			a := stk[len(stk)-1]
			b := stk[len(stk)-2]
			stk = stk[:len(stk)-2]
			stk = append(stk, op(b, a, x))
		} else {
			ii, _ := strconv.Atoi(x)
			stk = append(stk, ii)
		}
	}
	return stk[0] // 最后肯定只剩一个
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

var (
	in *bufio.Reader
	out *bufio.Writer
)

func main() {
	in = bufio.NewReader(os.Stdin) // 搭配Fscan使用
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

队列

AcWing 829. 模拟队列

package main

import (
	"bufio" // io
	"fmt"
	"os" // io
)

func _debug() {
	queue := []int{}

	n := ri()

	for i := 0; i < n; i++ {
		op := string(rs())

		if op == "push" {
			x := ri()
			queue = append(queue, x)
		} else if op == "pop" {
			queue = queue[1:]
		} else if op == "empty" {
			if len(queue) != 0 {
				fmt.Fprintln(out, "NO")
			} else {
				fmt.Fprintln(out, "YES")
			}
		} else if op == "query" {
			fmt.Fprintln(out, queue[0])
		}
	}
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>
const eof = 0

var (
	out *bufio.Writer

	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

// 读一个仅包含小写字母的字符串，必要时进行修改
func rs() (s []byte) {
	b := rc()
	for ; 'a' > b || b > 'z'; b = rc() { // 'A' 'Z'
	}
	for ; 'a' <= b && b <= 'z'; b = rc() { // 'A' 'Z'
		s = append(s, b)
	}
	return
}

// suggest
func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

func main() {
	// ===== ===== fast io ===== =====
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

单调栈

AcWing 830. 单调栈

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	stk := []int{}
	n := ri()
	nums := make([]int, n)

	for i := range nums {
		nums[i] = ri()
	}

	for _, x := range nums {
		for len(stk) > 0 && stk[len(stk)-1] >= x {
			stk = stk[:len(stk)-1]
		}
		if len(stk) == 0 {
			fmt.Fprint(out, -1, " ")
		} else {
			fmt.Fprint(out, stk[len(stk)-1], " ")
		}
		stk = append(stk, x)
	}
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

const eof = 0

var (
	// in  *bufio.Scanner
	out *bufio.Writer

	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

// 读一个仅包含小写/大写字母的字符串，必要时进行修改
func rs() (s []byte) {
	b := rc()
	for ; 'A' > b || b > 'Z'; b = rc() { // 'A' 'Z'	// 把非必要字符过滤掉
	}
	for ; 'A' <= b && b <= 'Z'; b = rc() { // 'A' 'Z'
		s = append(s, b)
	}
	return
}

// 读一个长度为 n 的仅包含小写/大写字母的字符串，必要时进行修改
func rsn(n int) []byte {
	b := rc()
	// 只读取大小写字母和数字
	for ; !('a' <= b && b <= 'z') && !('A' <= b && b <= 'Z') && !('0' <= b && b <= '9'); b = rc() { // 'A' 'Z'
	}
	s := make([]byte, 0, n)
	s = append(s, b)
	for i := 1; i < n; i++ {
		s = append(s, rc())
	}
	return s
}

func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

func main() {
	// ===== ===== fast io ===== =====
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

单调队列

AcWing 154. 滑动窗口

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	n, k := ri(), ri()

	nums := make([]int, n)
	for i := range nums {
		nums[i] = ri()
	}

	q := []int{}
	mins := []int{}
	maxs := []int{}

	for i := 0; i < len(nums); i++ {
		for len(q) > 0 && nums[i] <= nums[q[len(q)-1]] {
			q = q[:len(q)-1]
		}
		q = append(q, i)
		left := i - k + 1
		for q[0] < left {
			q = q[1:]
		}
		if i >= k-1 {
			mins = append(mins, nums[q[0]])
		}
	}

	q = []int{}
	for i := 0; i < len(nums); i++ {
		for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] {
			q = q[:len(q)-1]
		}
		q = append(q, i)
		left := i - k + 1
		for q[0] < left {
			q = q[1:]
		}
		if i >= k-1 {
			maxs = append(maxs, nums[q[0]])
		}
	}
	for _, x := range mins {
		fmt.Fprint(out, x, " ")
	}
	fmt.Fprintln(out)
	for _, x := range maxs {
		fmt.Fprint(out, x, " ")
	}
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

const eof = 0

var (
	out *bufio.Writer
	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

// 读一个仅包含小写/大写字母的字符串，必要时进行修改
func rs() (s []byte) {
	b := rc()
	for ; 'A' > b || b > 'Z'; b = rc() { // 'A' 'Z'	// 把非必要字符过滤掉
	}
	for ; 'A' <= b && b <= 'Z'; b = rc() { // 'A' 'Z'
		s = append(s, b)
	}
	return
}

// 读一个长度为 n 的仅包含小写/大写字母的字符串，必要时进行修改
func rsn(n int) []byte {
	b := rc()
	// 只读取大小写字母和数字
	for ; !('a' <= b && b <= 'z') && !('A' <= b && b <= 'Z') && !('0' <= b && b <= '9'); b = rc() { // 'A' 'Z'
	}
	s := make([]byte, 0, n)
	s = append(s, b)
	for i := 1; i < n; i++ {
		s = append(s, rc())
	}
	return s
}

func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

func main() {
	// ===== ===== fast io ===== =====
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}