代码随想录day10 || 232 栈实现队列， 225 队列实现栈，20 删除有效括号，1047 删除字符串相邻重复项

232 实现队列

// go本身并不支持原生的栈和队列结构，都是通过切片实现的
//leetcode submit region begin(Prohibit modification and deletion)
type MyQueue struct {
	Data []int
	Size int
}


func Constructor() MyQueue {
	return MyQueue{}
}


func (this *MyQueue) Push(x int)  {
	this.Data = append(this.Data, x)
	this.Size++
}


func (this *MyQueue) Pop() int {
	// 弹出首位
	if this.Size == 0 {
		return 0
	}
	temp := this.Data[0]
	this.Data = this.Data[1:]
	this.Size--
	return temp
}


func (this *MyQueue) Peek() int {
	// 弹出首位
	if this.Size == 0 {
		return 0
	}
	return this.Data[0]
}


func (this *MyQueue) Empty() bool {
	return this.Size == 0
}

225 实现栈

// 尝试通过链表方式实现栈
type LinkNode struct {
	Data int
	Next *LinkNode
}

type MyStack struct {
	Data *LinkNode
	Size int
}


func Constructor() MyStack {
	return MyStack{
		Data: &LinkNode{},
		Size: 0,
	}
}


func (this *MyStack) Push(x int)  {
	node := &LinkNode{x, nil}
	cur := this.Data  // 指针类型引用可以修改原变量
	for cur != nil && cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = node
	this.Size++
}


func (this *MyStack) Pop() int {
	// 栈顶就是最后的元素
	cur := this.Data
	for cur.Next != nil && cur.Next.Next != nil {
		cur = cur.Next
	}
	// 此时cur是倒数第二个位置
	num := cur.Next.Data
	cur.Next = nil
	this.Size--
	return num
}


func (this *MyStack) Top() int {
	cur := this.Data
	for cur.Next != nil {
		cur = cur.Next
	}
	return cur.Data
}


func (this *MyStack) Empty() bool {
	return this.Size == 0
}

20 删除有效括号

// 本题目使用stack是魔改上面的栈，将数据类型转换为rune
func isValid(s string) bool {
	// 思考 栈结构，依次入栈，匹配之后出栈，如果遍历结束之后还存留元素，那么返回fasle
	// 存储映射
	var maps = map[rune]rune{
		'}': '{',
		')': '(',
		']': '[',
	}
	stack := Constructor()
	for _, val := range s { // for range 遍历字符串，val是rune = []int32 类型
		if stack.Size > 0 {
			// fmt.Println(maps[val] ,stack.Top())
			if maps[val] == stack.Top() { // 匹配
				stack.Pop()
				continue // 进入下一个循环
			}
		}
		// 栈为空，或者元素不匹配
		stack.Push(val)
	}
	return stack.Empty()
}

// 时间遍历n次*每次top操作查询n = n^2 (优化方案就是尝试将栈结构里面的节点存储为尾节点，那么每次top操作的复杂度就是1), 空间n

1047 删除重复

func removeDuplicates(s string) string {
	// 使用栈的特性进行遍历对比
	// 规则，如果栈顶元素 == 遍历元素，那么就弹出，如果不等 入栈
	var res string
	stack := Constructor()
	for _, val := range s{
		// fmt.Println(stack.Size, string(stack.Top()), string(val))
		if stack.Size>0 && stack.Top() == val {
			stack.Pop()
			continue
		}
		stack.Push(val)
	}
	// 最后将栈里面元素反序打印
	for stack.Size != 0 {
		res = string(stack.Pop()) + res
	}
	return res
}

// 实现一个存储尾节点的链表实现的栈
type LinkNode struct{
	Data rune
	Prev *LinkNode
	Next *LinkNode
}

type Stack struct {
	Node *LinkNode
	Size int
}

func Constructor() *Stack {
	return &Stack{
		Node: &LinkNode{},
		Size: 0,
	}
}

func (s *Stack) Push(x rune) {
	node := &LinkNode{x, nil, nil}
	node.Prev = s.Node
	s.Node.Next = node // 连接到链表
	s.Node = node // 指向尾节点
	s.Size++
}

func (s *Stack) Pop() rune {
	next := s.Node.Prev // 前一个节点
	data := s.Node.Data
	next.Next = nil // 将最后一个节点断开连接
	s.Node.Prev = nil // 节点完全断开，防止还有悬挂指针，导致意料之外的内存泄漏
	s.Node = next // 重新指向前一个结点
	s.Size--
	return data
}

func (s *Stack) Top() rune {
	if s.Size == 0 {
		return ' ' // 单引号里面必须有一个字符不然就是非法的
	}
	return s.Node.Data
}

func (s *Stack) Empty() bool {
	return s.Size == 0
}

// 时间 n层遍历 * top 1 = n , 空间n