leetcode 232 栈实现队列

栏目: 编程工具 · 发布时间: 6年前

内容简介:使用栈实现队列的下列操作:

232. 用栈实现队列

使用栈实现队列的下列操作:

  • push(x) -- 将一个元素放入队列的尾部。
  • pop() -- 从队列首部移除元素。
  • peek() -- 返回队列首部的元素。
  • empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

  • 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

解题思路

  • 在Golang中,本身未提供栈数据结构,先基于数组实现栈结构
  • 优化: 入队时,将元素压入s1,出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队
  • 避免反复"倒"栈,仅在需要时才"倒"一次
  • 细节: 考虑没有元素可供出队时的处理(2个栈都为空的时候,出队操作一定会引起异常)

代码实现

/**
 * 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();
 */

// MyQueue defines Stack1 queue by two stacks
type MyQueue struct {
    Stack1, Stack2 *stack
}

// Constructor Initialize your data structure here.
func Constructor() MyQueue {
    return MyQueue{
        Stack1: newStack(),
        Stack2: newStack(),
    }
}

// Push element x to the back of queue.
func (queue *MyQueue) Push(x int) {
    queue.Stack1.push(x)
}

// Pop Removes the element from in front of queue and returns that element.
func (queue *MyQueue) Pop() int {
    if queue.Stack2.isEmpty() {
        //优化: 栈a中留一个元素供pop,可以少一次操作
        for queue.Stack1.len() > 1 {
            queue.Stack2.push(queue.Stack1.pop())
        }
        return queue.Stack1.pop()
    }
    return queue.Stack2.pop()
}

// Peek Get the front element.
func (queue *MyQueue) Peek() int {
    if queue.Stack2.isEmpty() {
        if queue.Stack1.isEmpty() {
            return -1
        }
        return queue.Stack1.nums[0]
    }
    return queue.Stack2.nums[queue.Stack2.len()-1]
}

// Empty Returns whether the queue is empty.
func (queue *MyQueue) Empty() bool {
    return queue.Stack1.isEmpty() && queue.Stack2.isEmpty()
}

// stack defines Stack1 stack
type stack struct {
    nums []int
}

// newStack creates a empty stack
func newStack() *stack {
    return &stack{
        nums: []int{},
    }
}

func (s *stack) push(n int) {
    s.nums = append(s.nums, n)
}

func (s *stack) pop() int {
    if s.isEmpty() {
        return -1
    }
    res := s.nums[len(s.nums)-1]
    s.nums = s.nums[:len(s.nums)-1]
    return res
}

func (s *stack) len() int {
    return len(s.nums)
}
func (s *stack) isEmpty() bool {
    return s.len() == 0
}

GitHub

  • 源码在这里
  • 项目中会提供各种数据结构及算法的Golang实现,以及 LeetCode 解法

参考资料

用两个栈实现一个队列——我作为面试官的小结


以上所述就是小编给大家介绍的《leetcode 232 栈实现队列》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

国家窃听

国家窃听

真溱 / 中信出版社 / 2015-8 / 48.00元

《国家窃听》以轻松而略带调侃的“冷幽默”风格,讲述了美国情报监视帝国大量不为人知的故事。本书以严谨而专业的视角,将“斯诺登事件”放在21世纪以来美国“全球反恐战争”以及美国情报界几十年发展的大背景下进行考察,揭示出这一事件的内在逻辑和历史必然。作者前期搜集、筛选、整理的一手素材在故事叙述过程中清晰而多层次地呈现,令本书堪称一部非虚构的美国情报界演义。一起来看看 《国家窃听》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

MD5 加密
MD5 加密

MD5 加密工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具