代码随想录算法训练营第十天 232.用栈实现队列、225. 用队列实现栈。

代码随想录算法训练营第十天 232.用栈实现队列、225. 用队列实现栈。

232.用栈实现队列

题目链接：力扣题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：栈的基本操作！ | LeetCode：232.用栈实现队列

状态：AC

思路

  • 初始化两个栈，一个作为主栈Stack1、一个作为副栈Stack2
  • 主栈存放数据、副栈临时放数据
  • Push操作：将数据放入Stack1中
  • Pop操作：
    • 将Stack1中所有元素退栈，并入栈Stack2。
    • 将Stack2的栈顶元素出栈
    • 将Stack2中所有元素退栈，并入栈Stack1。
  • Peek操作：
    • 将Stack1中所有元素退栈，并入栈Stack2。
    • 取Stack2的栈顶元素
    • 将Stack2中所有元素退栈，并入栈Stack1。
  • Empty操作：
    • 查看Stack1是否为空即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type MyQueue struct {
	Stack1 arraystack.Stack
	Stack2 arraystack.Stack
}

func Constructor() MyQueue {
	return MyQueue{
		Stack1: *arraystack.New(),
		Stack2: *arraystack.New(),
	}
}

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

func (this *MyQueue) Pop() int {
	for !this.Stack1.Empty() {
		if v, ok := this.Stack1.Pop(); ok {
			this.Stack2.Push(v)
		}
	}
	value, _ := this.Stack2.Pop()
	for !this.Stack2.Empty() {
		if v, ok := this.Stack2.Pop(); ok {
			this.Stack1.Push(v)
		}
	}
	return value.(int)
}

func (this *MyQueue) Peek() int {
	for !this.Stack1.Empty() {
		if v, ok := this.Stack1.Pop(); ok {
			this.Stack2.Push(v)
		}
	}
	value, _ := this.Stack2.Peek()
	for !this.Stack2.Empty() {
		if v, ok := this.Stack2.Pop(); ok {
			this.Stack1.Push(v)
		}
	}
	return value.(int)
}

func (this *MyQueue) Empty() bool {
	return this.Stack1.Empty()
}

225. 用队列实现栈

题目链接：力扣题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：队列的基本操作！ | LeetCode：225. 用队列实现栈

状态：AC

思路

  • 初始化一个队列Queue1
  • 主栈存放数据、副栈临时放数据
  • Push操作：将数据入队Queue1
  • Pop操作：
    • 将Queue1前n-1个元素出队，随后入队在队尾
    • 最后一个元素出队，返回
  • Top操作：
    • 将Queue每个出队，随后入队在队尾
    • 如果是最后一个元素出队，保存该值，并入队
    • 返回那个值
  • Empty操作：
    • 查看Queue1是否为空即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
type MyStack struct {
	Queue1 arrayqueue.Queue
}

func Constructor() MyStack {
	return MyStack{
		Queue1: *arrayqueue.New(),
	}
}

func (this *MyStack) Push(x int) {
	this.Queue1.Enqueue(x)
}

func (this *MyStack) Pop() int {
	for i := 0; i < this.Queue1.Size()-1; i++ {
		v, _ := this.Queue1.Dequeue()
		value := v.(int)
		this.Queue1.Enqueue(value)
	}
	v, _ := this.Queue1.Dequeue()
	value := v.(int)
	return value
}

func (this *MyStack) Top() int {
	top := 0
	for i := 0; i < this.Queue1.Size(); i++ {
		v, _ := this.Queue1.Dequeue()
		value := v.(int)
		this.Queue1.Enqueue(value)
		if i == this.Queue1.Size()-1 {
			top = value
		}
	}
	return top
}

func (this *MyStack) Empty() bool {
	return this.Queue1.Empty()
}

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