今日任务 

• 栈与队列的理论基础 (介绍:代码随想录)
• 232 用栈实现队列(题目:  . - 力扣（LeetCode）)
• 225 用队列实现栈 (题目: . - 力扣（LeetCode） )

---

栈与队列的理论基础

        栈 : 先进后出    队列: 后进先出

        老师给的讲解:代码随想录   这个可能适合于 c++的同学理解,我的 go 看这里是有点不明所以..

---

232 用栈实现队列

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

说明：

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

想法:

        其实我完全理解栈与队列的特性, 先进后出、先进先出嘛, 但是一开始明白这题让干嘛的,在想这是否跟语言有关啊? 下一步直接看题解Go代码,

问题:

        看了题解才明白,其实我们就是可以利用各种语言提供的数据类型, 去模拟实现栈的一个效果,栈就是要具有 push 、pop、top、empty 这几个操作.  然后再用栈去实现 队列的操作:push、pop、peek、empty.

        那么理解了题意后,才是该思考的问题了,如何用拥有栈特性的数据结构去实现拥有队列属性的数据结构呢??🤔🤔

解决思路:

        使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。       

        就是我们将数据 push 到栈里了,这时该如何将第一个 push 到栈的数据通过 pop给先取出来呢? 我们可以借助另一个栈2,将我们另一个栈的数据 全取出来,再 push 到栈 2 里了,这时的栈 2 的元素出栈的顺序就和我们的队列相同了.

        

图片和题解参考:代码随想录

 看代码(Go):

// 先用切片模拟栈,再用两个栈的特性去模拟一个队列的特性
//  1、通过切片实现一个栈的各种操作
type MyStack []int

func (s *MyStack) Push(v int){
    *s = append(*s,v)
}

func (s *MyStack) Pop() int {
    val := (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return val
}

func (s *MyStack) Peek() int {
    val := (*s)[len(*s)-1]
    return val
}

func (s *MyStack) Size() int {
    return len(*s)
}

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


// 2、下面开始用两个栈实现队列
type MyQueue struct {
    inStack *MyStack
    outStack *MyStack
}


func Constructor() MyQueue {
    return MyQueue {
        inStack: &MyStack{},
        outStack: &MyStack{},
    }
}


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

// 在取之前,要先把入栈里的元素全都取出放到出栈里(如果出栈里仍有数据的话,肯定还是可以直接出的)
func (this *MyQueue) Pop() int {
    this.moveStack()
    return this.outStack.Pop()
}


func (this *MyQueue) Peek() int {
    this.moveStack()
    return this.outStack.Peek()
}


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

func (this *MyQueue) moveStack() {
    // 如果出栈为空的时候,再将入栈里的数据全都移动到出栈里,这样保证所有数据一直按照先进先出的顺序来的
    if this.outStack.Empty() {
        for !this.inStack.Empty() {
            this.outStack.Push(this.inStack.Pop())
        }
    }
}

---

225 用队列实现栈

        请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

注意：

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

想法:

        做了上一题后,我们就明白该如何去用语言已有的数据结构去模拟出栈的操作,我直接用切片就能实现栈的操作哎,但是题目还是让我们用两个队列实现,主要还是想要我们理解其中该如何转换.

问题:

       两个队列该如何实现呢? 如果我们像上一题,一个输入一个输出队列模拟还真不行, 因为最后出来的还都是先进先出.

解决思路:

1、两个队列 (题目要求)

        依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1.

2、一个队列 (更优)

        一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

        

 图片和题解参考:代码随想录 

// 使用1个 队列实现栈的效果
 type MyStack struct{  // 初始化
    queue []int
 }

 func Constructor() MyStack {
    return MyStack{
        queue: make([]int,0),
    }
 }


func (this *MyStack) Push(x int){
    // 添加元素
    this.queue = append(this.queue,x)
}

func (this *MyStack) Pop() int {
    // 取出元素,因为我们当前是模拟在队列里的,遵守了一个先进先出的顺序,那么为了实现栈,我们要实现后进先出的效果
    n := len(this.queue)-1  // 判断长度
    // 除了最后一个元素,其余的都重新添加到队列里
    for n != 0{
        val := this.queue[0]
        // 截掉第一个元素,即将加入到队尾
        this.queue=this.queue[1:]
        this.queue=append(this.queue,val)
        n--
    }
    // 弹出元素
    val := this.queue[0]
    this.queue = this.queue[1:]
    return val
}

func (this *MyStack) Top() int {
    val := this.Pop()
    // 先弹出来,再添加进去,虽然这个过程也挺无语的,就是先来了个 for 循环把最后一个元素取出来了,然后再推进去.
    this.Push(val)
    return val
}

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




// 两个队列实现的
type MyStack struct {
    //创建两个队列
    queue1 []int
    queue2 []int
}


func Constructor() MyStack {
    return MyStack{	//初始化
        queue1:make([]int,0),
        queue2:make([]int,0),
    }
}


func (this *MyStack) Push(x int)  {
     //先将数据存在queue2中
    this.queue2 = append(this.queue2,x)	
   //将queue1中所有元素移到queue2中，再将两个队列进行交换
    this.Move() 
}


func (this *MyStack) Move(){    
    if len(this.queue1) == 0{
        //交换，queue1置为queue2,queue2置为空
        this.queue1,this.queue2 = this.queue2,this.queue1
    }else{
        //queue1元素从头开始一个一个追加到queue2中
            this.queue2 = append(this.queue2,this.queue1[0])  
            this.queue1 = this.queue1[1:]	//去除第一个元素
            this.Move()     //重复
    }
}

func (this *MyStack) Pop() int {
    val := this.queue1[0]
    this.queue1 = this.queue1[1:]	//去除第一个元素
    return val

}


func (this *MyStack) Top() int {
    return this.queue1[0]	//直接返回
}


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

我这一开始提交的可以直接通过,但是不是队列实现栈,哈哈...

// 我这下面的栈并不是由队列实现的?  感觉有点奇怪,直接就用了下标索引取值的很 easy
type MyStack struct {
    queue []int
}


func Constructor() MyStack {
    return MyStack{
        queue: make([]int,0),
    }
}


func (this *MyStack) Push(x int)  {
    this.queue = append(this.queue,x)
}


func (this *MyStack) Pop() int {
    val := this.queue[len(this.queue) - 1]
    this.queue = this.queue[0:len(this.queue)-1]
    return val
}


func (this *MyStack) Top() int {
    return this.queue[len(this.queue) - 1]
}


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