栈与队列理论基础

队列是先进先出，栈是先进后出

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是我们可以控制使用哪种容器来实现栈的功能）

我们常用的SGL STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

栈提供push和pop接口，所有元素必须符合先进后出的规则，所以栈不提供走访功能，也不提供迭代器。不像set或者map提供迭代器iterator来遍历所有元素。

deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

232.用栈实现队列

文章：2. 用栈实现队列

题目：232. 用栈实现队列

视频：栈的基本操作！ | LeetCode：232.用栈实现队列_哔哩哔哩_bilibili

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

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

【思路】

队列：先入先出

栈，需要借助另一个栈。关键在于如何模拟出栈的顺序，需要两个栈，一个输入栈，一个输出栈。

在push数据的时候，只要数据全部放进输入栈就好，但在pop的时候，就要把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空？如果进栈和出栈队列都为空的话， 说明模拟的队列也为空了。

  • Java实现
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
class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {  
        dumpstackIn();
        return stackOut.pop();
    }
    
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty()&&stackOut.isEmpty();
    }

    private void dumpstackIn(){
        if(!stackOut.isEmpty()){
            return ;
        }
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
  • Go实现
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 {
    stackIn []int
    stackOut []int
}


func Constructor() MyQueue {
    return MyQueue{
        stackIn: make([]int,0),
        stackOut: make([]int,0),
    }
}

func (this *MyQueue) Push(x int)  {
    this.stackIn = append(this.stackIn,x)
}


func (this *MyQueue) Pop() int {
    inlen , outlen := len(this.stackIn),len(this.stackOut)
    if outlen == 0{
        if inlen == 0{
            return -1
        }
        for i:=inlen-1;i>=0;i--{
            this.stackOut = append(this.stackOut,this.stackIn[i])
        }
        outlen = len(this.stackOut)
        this.stackIn = []int{}
    }
    val := this.stackOut[outlen-1]
    this.stackOut = this.stackOut[:outlen-1]
    return val
}


func (this *MyQueue) Peek() int {
    val := this.Pop()
    if val == -1{
        return -1
    }
    this.stackOut = append(this.stackOut,val)
    return val
}


func (this *MyQueue) Empty() bool {
    return len(this.stackIn) == 0 && len(this.stackOut)==0
}

225.用队列实现栈

文章：3. 用队列实现栈

题目：225. 用队列实现栈

视频：队列的基本操作！ | LeetCode：225. 用队列实现栈_哔哩哔哩_bilibili

【思路】

用一个队列来模拟栈的进出。

把元素提出来再加入队列即可。

  • Java实现

使用了Deque类型来完成该题，使用的函数有：

​ addLast()添加至队列最后元素

​ peekFirst()查看顶层元素

​ pollFirst()弹出顶层元素

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
class MyStack {

    Deque<Integer> que1;
    public MyStack() {
        que1 = new ArrayDeque<>();
    }
    
    public void push(int x) {
        que1.addLast(x);
    }
    
    public int pop() {
        int size = que1.size();
        size--;
        while(size-- >0){
            que1.addLast(que1.peekFirst());
            que1.pollFirst();
        }
        int res = que1.pollFirst();
        return res;
    }
    
    public int top() {
        return que1.peekLast();
    }
    
    public boolean empty() {
        return que1.isEmpty();
    }
}
  • Go

使用了切片模拟队列来进行入栈出栈的操作

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
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 {
    l := len(this.queue)-1
    for l != 0{
        val := this.queue[0]
        this.queue = this.queue[1:]
        this.queue = append(this.queue,val)
        l--
    }
    val := this.queue[0]
    this.queue = this.queue[1:]
    return val
}


func (this *MyStack) Top() int {
    val := this.Pop();
    this.queue = append(this.queue,val)
    return val
}


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

【算法总结】

  • 用栈实现队列：使用了两个栈（输入栈和输出栈）来模拟队列的操作，将输入栈的内容顺序放出输出栈即为队列的形式。
  • 用队列实现栈：使用了一个队列来模拟栈的操作，将队列的元素弹出后再放入，循环下来即模拟了栈的形式。

【语法总结】

  • Java使用了Stack和Deque来模拟队列和栈：

栈（Stack）的函数：

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

队列（Deque）的函数-

​ addLast()添加至队列最后元素

​ peekFirst()查看顶层元素

​ pollFirst()弹出顶层元素

  • Go使用了切片来模拟队列和栈，还是相对来说非常灵活的。