Skip to content

Latest commit

 

History

History

0232.Implement-Queue-using-Stacks

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
Solution.go
Solution.go
 
 
Solution_test.go
Solution_test.go
 
 

README.md

232. Implement Queue using Stacks

Description

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.

pop() -- Removes the element from in front of queue.

peek() -- Get the front element.

empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

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

NOTES

  • You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Tags: Queue, Stack

题意

使用栈来实现队列

主要体现为实现四个函数

  • push(x) 在队列的末尾增加元素
  • pop() 在队列的头部删除元素
  • peek() 获取队列的第一个元素
  • empty() 返回队列是否是空队列

思路1

定义结构体MyQueue, 包含一个切片array用来存储队列元素，主要逻辑在于定义中间元素来移动切片，从而达到去栈底元素的目的。

type MyQueue struct {
	array []int
}

思路2

  1. 首选封装一个栈的结构

  2. 定义队列包含两个栈，分别是输入栈s1和输出栈s2,入对数据都存入s1中，出对数据都从s2来。

具体实现如下：

// 封装栈结构
type Stack []int
func (s *Stack) Empty() bool {return len(*s) == 0}
func (s *Stack) Push(x int) {*s = append(*s, x)}
func (s *Stack) Peek() int {return (*s)[len(*s)-1]}
func (s *Stack) Pop() int {
    x := (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return x
}

type MyQueue struct {
    s1, s2 Stack
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue{}
}


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


/** Removes the element from in front of queue and returns that element. */
func (q *MyQueue) Pop() int {
    if q.s2.Empty() {
        for !q.s1.Empty() {
            x := q.s1.Pop()
            q.s2.Push(x)
        }
    }
    return q.s2.Pop()
}


/** Get the front element. */
func (q *MyQueue) Peek() int {
    if q.s2.Empty() {
        for !q.s1.Empty() {
            x := q.s1.Pop()
            q.s2.Push(x)
        }
    }
    return q.s2.Peek()
}


/** Returns whether the queue is empty. */
func (q *MyQueue) Empty() bool {
    return q.s1.Empty() && q.s2.Empty()
}

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-letcode