栈和队列

1. 栈的实现

1.1 基于链表实现

将链表的尾节点视为栈顶，头节点视为栈底

入栈操作: 将元素插入链表尾部

出栈操作: 删除链表的尾节点

// 基于链表实现的栈
type LinkedListStack struct {
	// 使用内置包list来实现
	data *list.List
}

// 初始化一个栈
func NewLinkedListStacg() *LinkedListStack {
	return &LinkedListStack{
		// 使用list包初始化一个链表
		data: list.New(),
	}
}

// Push 向栈中压入一个元素
func (stack *LinkedListStack) Push(data int) {
	stack.data.PushBack(data)
}

// PoP 弹出一个栈顶元素
func (stack *LinkedListStack) PoP() any {
	// 首先判断栈是为空
	if stack.IsEmpty() {
		return nil
	}
	element := stack.data.Back()
	stack.data.Remove(element)
	// 断言
	return element.Value.(int)
}

// Peek 访问栈顶元素
func (stack *LinkedListStack) Peek() any {
	// 首先判断栈是为空
	if stack.IsEmpty() {
		return nil
	}
	return stack.data.Back().Value.(int)
}

// Len 获取栈的长度
func (stack *LinkedListStack) Len() int {
	return stack.data.Len()
}

// IsEmpty 判断栈是否为空
func (stack LinkedListStack) IsEmpty() bool {
	return stack.data.Len() == 0
}

// Tolist 打印栈
func (stack *LinkedListStack) Tolist() {
	for i := stack.data.Front(); i != nil; i = i.Next() {
		fmt.Printf("%v ->  ", i.Value)
	}
	fmt.Printf("\n")
}

测试

func TestLinkedListStack_Push(t *testing.T) {
	stack := NewLinkedListStacg()
	stack.Push(1)
	stack.Push(36)
	stack.Push(64)
	stack.Push(12)
	stack.Push(90)

	fmt.Println("栈顶元素为: ", stack.Peek())
	fmt.Println("弹出的元素为:", stack.PoP())

	// 查看栈元素
	stack.Tolist()
}

1.2 基于数组实现

type ArrayStack struct {
	data []int
}

// NewArrayStack 初始化栈
func NewArrayStack() *ArrayStack {
	return &ArrayStack{
		data: make([]int, 0),
	}
}

// Push 将一个元素压入栈中
func (stack *ArrayStack) Push(element int) {
	stack.data = append(stack.data, element)
}

// Pop 弹出站顶元素
func (stack *ArrayStack) Pop() any {
	if stack.IsEmpty() {
		return nil
	}
	value := stack.data[len(stack.data)-1]
	stack.data = stack.data[:len(stack.data)-1]
	return value
}

// Peek 返回栈顶元素
func (stack *ArrayStack) Peek() any {
	if stack.IsEmpty() {
		return nil
	}
	return stack.data[len(stack.data)-1]
}

// IsEmpty 判断栈是否为空
func (stack *ArrayStack) IsEmpty() bool {
	return len(stack.data) == 0
}

// Tolist 查看栈中元素
func (stack *ArrayStack) Tolist() {
	for _, value := range stack.data {
		fmt.Printf("%v -> ", value)
	}
	fmt.Printf("\n")
}

测试

func TestIsValid(t *testing.T) {
	//var Test []int
	//
	//for i := 0; i < 1000; i++ {
	//	Test = append(Test, i)
	//	fmt.Println("切片的容量为:", cap(Test))
	//}

	stack := NewArrayStack()

	stack.Push(10)
	stack.Push(19)
	stack.Push(20)
	stack.Push(26)
	stack.Push(13)

	fmt.Println("返回栈顶元素为: ", stack.Peek())
	fmt.Println("弹出栈顶元素为: ", stack.Pop())

	stack.Tolist()
}

2. 队列的实现

2.1 基于链表实现

将链表的头节点和尾节点视为队头和队尾

对头删除元素

对尾添加元素

type LinkedListQueue struct {
	// 使用 list实现队列
	data *list.List
}

// NewLinkedListQueue 初始化队列
func NewLinkedListQueue() *LinkedListQueue {
	return &LinkedListQueue{
		data: list.New(),
	}
}

// Push 入队
func (queue *LinkedListQueue) Push(data int) {
	queue.data.PushBack(data)
}

// Pop 出队
func (queue *LinkedListQueue) Pop() any {
	if queue.IsEmpty() {
		return nil
	}
	element := queue.data.Front()
	queue.data.Remove(element)
	return element.Value
}

// IsEmpty 判断队列元素是否为空
func (queue *LinkedListQueue) IsEmpty() bool {
	return queue.data.Len() == 0
}

// Peek 返回队头元素
func (queue *LinkedListQueue) Peek() any {
	return queue.data.Front().Value
}

测试

func TestLinkedListQueue_Pop(t *testing.T) {
	queue := NewLinkedListQueue()

	queue.Push(89)
	queue.Push(100)
	queue.Push(500)
	queue.Push(256)
	queue.Push(128)
	fmt.Println("队头元素为:", queue.Peek())
	fmt.Println("出队:", queue.Pop())
	for i := queue.data.Front(); i != nil; i = i.Next() {
		fmt.Printf("%v -> ", i.Value)
	}
	fmt.Printf("\n")
}

2.2 基于数组实现

思路: 使用 front 指向队尾元素的索引，size 为队列的长度
rear = front + size rear 永远指向队尾元素的下一个位置

入队操作：将元素赋值给 rear，size + 1

出队操作：将 front + 1，size - 1

为了解决 front 和 rear 到达队列尾部的问题，可以将队列视为环形数组

让 front 或 rear 越过数据尾部是，回到开头，rear = (front + size) % queue.capacity

type ArrayQueue struct {
	data     []any
	front    int // 队首指针,指向队首元素
	size     int // 队列长度
	capacity int // 队列容量
}

// 初始化队列
func NewArrayQueue(capacity int) *ArrayQueue {
	return &ArrayQueue{
		data:     make([]any, capacity),
		front:    0,
		size:     0,
		capacity: capacity,
	}
}

// Push 入队
func (queue *ArrayQueue) Push(element any) error {
	if queue.size == queue.capacity {
		return errors.New("queue already full")
	}
	// rear 指向队尾元素后的下一个位置
	// 取余的操作可以将数组看做是首尾向连的环形数组
	rear := (queue.front + queue.size) % queue.capacity
	queue.data[rear] = element
	queue.size++
	return nil
}

// Peek 访问队首元素
func (queue *ArrayQueue) Peek() (any, error) {
	if queue.size == 0 {
		return nil, errors.New("queue is empty")
	}
	return queue.data[queue.front], nil
}

// Pop 出队
func (queue *ArrayQueue) Pop() (any, error) {
	data, err := queue.Peek()
	// 队首指针+1,超出范围返回队列头部
	queue.front = (queue.front + 1) % queue.capacity
	queue.size--
	return data, err
}

// Tolist 队列元素为
func (queue *ArrayQueue) Tolist() []any {

	rear := queue.front + queue.size

	if rear > queue.capacity {
		rear %= queue.capacity
		return append(queue.data[queue.front:queue.size], queue.data[:rear]...)
	}
	return queue.data[queue.front:rear]
}

测试

func TestNewArrayQueue(t *testing.T) {
	queue := NewArrayQueue(5)
	queue.Push(10)
	queue.Push("sakura")
	queue.Push("Golang")
	queue.Push("LF")
	queue.Push("9s")
	peek, _ := queue.Peek()
	fmt.Println("队首元素为", peek)
	queue.Pop()
	queue.Pop()
	queue.Pop()

	queue.Push(10)
	queue.Push(11)
	queue.Push(12)

	fmt.Println("----------")
	fmt.Println(queue.front)
	fmt.Println(queue.size)

	//fmt.Println(queue.data[queue.front:queue.size])
	//fmt.Println(queue.data[:3])
	fmt.Println(queue.Tolist())
}

3. Leetcode 算法题

20.有效的括号

20. 有效的括号 - 力扣（LeetCode）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

# 示例 1：
输入：s = "()"
输出：true

# 示例 2：
输入：s = "()[]{}"
输出：true

# 示例 3：
输入：s = "(]"
输出：false

第一种解法：栈

思路: 遇到正括号入栈，遇到反括号匹配栈顶元素与反括号，不匹配，直接返回 false，如果全部括号一一匹配，则栈中元素个数为 0
len(stack)>0 是为了判断开头就是反括号的情况

func isValid(s string) bool {
	var stack []string
	for _, v := range s {
		// 正括号的情况 ( { [
		if string(v) == "{" || string(v) == "(" || string(v) == "[" {
			stack = append(stack, string(v))
		} else {
			// 反括号 ) } ]
			if len(stack) > 0 && stack[len(stack)-1] == "{" && string(v) == "}" {
				// 相当于栈的Pop操作
				stack = stack[:len(stack)-1]
			} else if len(stack) > 0 && stack[len(stack)-1] == "(" && string(v) == ")" {
				stack = stack[:len(stack)-1]
			} else if len(stack) > 0 && stack[len(stack)-1] == "[" && string(v) == "]" {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		}
	}
	return len(stack) == 0
}

第二种解法：栈 + 哈希表

这种写法代码整体会简洁一些
思路：使用 map 存储括号对应关系，直接用栈顶元素Peek() -> "("和map[")"]匹配，就不要上面代码一样多次 else if
同样，len(stack)>0 也是为了判断开头就是反括号的情况

func isValid(s string) bool {
	// 创建map,k,v,对应左右括号
	hash := map[byte]byte{')':'(', ']':'[', '}':'{'}
	stack := make([]byte, 0)

	for _, value := range s {
		if value == '(' || value == '[' || value == '{'{
			stack = append(stack, byte(value))
		} else if len(stack) > 0 && stack[len(stack)-1] == hash[byte(value)]{
			stack = stack[:len(stack)-1]
		} else {
			return false
		}
	}
	return len(stack) == 0
}

目录CONTENT

算法学习-栈和队列