栈和队列

Oct 08 2022, Sat

定义

栈：后进先出（LIFO），最后插入的元素最先出来。栈是一种“操作受限”的线性表：只允许在一端插入和删除数据。

队列：先进先出（FIFO），队列是一种使用两端的结构：一端用来加入新元素，另一端用来删除元素。

实现

栈和队列，既可以用数组来实现，也可以用链表来实现。用数组实现的栈/队列，叫顺序栈/队列，用链表实现的栈，叫链式栈/队列。

对于栈来说，基本操作入栈、出栈只涉及栈顶数据的操作，时间复杂度都是O(1)。而对于队列来说，入队的时间复杂度都是O(1)，出队一般情况下时间复杂度也是O(1)，但是如果产生数据移动就是O(n)了。

那么有没有一种实现，可以避免数据移动呢？

题目

有效的括号

https://leetcode.cn/problems/valid-parentheses/

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

有效字符串需满足：

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

示例 1：输入：s = “()” 输出：true

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

示例 3：输入：s = “(]” 输出：false

func isValid(s string) bool {
    l := len(s)
    if l == 0 {
        return true
    }

    if (l & 1) == 1 {
        return false
    }

    p := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    res := []byte{}

    for i :=0; i < l; i++ {
        if p[s[i]] > 0 {
            if len(res) == 0 || res[len(res) - 1] != p[s[i]] {
                return false
            }
            res = res[:len(res) - 1]
        } else {
            res = append(res, s[i])
        }
    }

    return len(res) == 0
}

用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false 说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

type MyQueue struct {
    inStack []int
    outStack []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int)  {
    this.inStack = append(this.inStack, x)
}

func (this *MyQueue) in2out() {
    for len(this.inStack) > 0 {
        this.outStack = append(this.outStack, this.inStack[len(this.inStack) - 1])
        this.inStack = this.inStack[:len(this.inStack) - 1]
    }
}

func (this *MyQueue) Pop() int {
    if len(this.outStack) == 0 {
        this.in2out()
    }

    x := this.outStack[len(this.outStack) - 1]
    this.outStack = this.outStack[:len(this.outStack) - 1]
    return x
}

func (this *MyQueue) Peek() int {
    if len(this.outStack) == 0 {
        this.in2out()
    }

    return this.outStack[len(this.outStack) - 1]
}

func (this *MyQueue) Empty() bool {
    return len(this.inStack) == 0 && len(this.outStack) == 0
}

用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

type MyStack struct {
    queue1 []int
    queue2 []int
}

func Constructor() (s MyStack) {
    return
}

func (s *MyStack) Push(x int) {
    s.queue2 = append(s.queue2, x)
    for len(s.queue1) > 0 {
        s.queue2 = append(s.queue2, s.queue1[0])
        s.queue1 = s.queue1[1:]
    }
    s.queue1, s.queue2 = s.queue2, s.queue1
}

func (s *MyStack) Pop() int {
    v := s.queue1[0]
    s.queue1 = s.queue1[1:]
    return v
}

func (s *MyStack) Top() int {
    return s.queue1[0]
}

func (s *MyStack) Empty() bool {
    return len(s.queue1) == 0
}

关注和赞赏都是对小欧莫大的支持！ 🤝 🤝 🤝
公众号