栈与队列算法（1）——用栈实现队列

参考资料： 🔗代码随想录_用栈实现队列 🔗稀土掘金_golang 栈数据结构的实现和应用

[toc]

232. 用栈实现队列

232. 用栈实现队列

简单

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：

1 <= x <= 9

最多调用 100 次 push、pop、peek 和 empty

假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

用栈实现队列，需要一个输入栈，一个输出栈。

需要先用 Go 实现一个栈（这里使用 slice），然后再用该栈模拟队列。

原本需要在 stack.Len() 中加读锁，但在 LeetCode 中再多加一个读锁就会时间超限。。

下面动画模拟以下队列的执行过程：

执行语句： queue.push(1); queue.push(2); queue.pop(); 注意此时的输出栈的操作 queue.push(3); queue.push(4); queue.pop(); queue.pop();注意此时的输出栈的操作 queue.pop(); queue.empty();

push 数据，只要把数据放进输入栈即可。

pop 数据：如果输出栈为空，就把输入栈的数据全部导入输出栈，再从输出栈 Pop 数据。

fillStackOut：将数据全部导入输出栈写成一个方法

peek 和 empty：如果输出栈为空，就把输入栈的数据全部导入输出栈，再查看 stackOut 的栈顶元素、判断 stackOut 是否为空。

见详细代码：

// 用 slice 实现栈
type myStack struct {
    Ints []int
    Lock sync.RWMutex
}

func NewStack() *myStack {
    return &myStack{
        Ints: []int{}, // 字面量 []int{} 已经分配好内存空间
    }
}

// Push 入栈
func (s *myStack) Push(t int) {
    s.Lock.Lock()
    defer s.Lock.Unlock()
    s.Ints = append(s.Ints, t)
}

// Pop 出栈
func (s *myStack) Pop() int {
    s.Lock.Lock()
    defer s.Lock.Unlock()
    if s.Empty() {
        return 0
    }
    val := s.Ints[s.Len()-1]
    s.Ints = s.Ints[:s.Len()-1]
    return val
}

// Len 栈内存储的元素数量
func (s *myStack) Len() int {
    return len(s.Ints)
}

// Peek 查看栈顶元素
func (s *myStack) Peek() int {
    if s.Empty() {
        return 0
    }
    return s.Ints[s.Len()-1]
}

// Empty 检查栈是否为空
func (s *myStack) Empty() bool {
    return s.Len() == 0
}


// ==========分割线==========

type MyQueue struct {
    stackIn *myStack
    stackOut *myStack
}


func Constructor() MyQueue {
    return MyQueue {
        stackIn: NewStack(),
        stackOut: NewStack(),
    }
}


func (q *MyQueue) Push(x int)  {
    q.stackIn.Push(x)
}


func (q *MyQueue) Pop() int {
    // 如果 q.stackOut 中没有元素，把 stackIn 元素全部 Push 到 stackOut 中
    q.fillStackOut()
    // 如果 q.stackOut 中有元素则直接 Pop 元素
    return q.stackOut.Pop()

}


func (q *MyQueue) Peek() int {
    q.fillStackOut()
    return q.stackOut.Peek()
}


func (q *MyQueue) Empty() bool {
    q.fillStackOut()
    return q.stackOut.Empty()
}

func (q *MyQueue) fillStackOut() {
    if q.stackOut.Empty() {
        for !q.stackIn.Empty() {
            val := q.stackIn.Pop()
            q.stackOut.Push(val)
        }
    }
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

# 栈与队列算法（1）——用栈实现队列

232. 用栈实现队列

# 字符串算法（3）

# 栈与队列算法（2）——用队列实现栈