用链表实现队列/栈

labuladong原创约 1281 字

前置知识

阅读本文前，你需要先学习：

队列/栈基本原理

用链表实现栈

一些读者应该已经知道该怎么用链表作为底层数据结构实现队列和栈了。因为实在是太简单了，直接调用双链表的 API 就可以了。

注意我这里是直接用的 Java 标准库的 LinkedList，如果你用之前我们实现的 MyLinkedList，也是一样的。

java 🟢

import java.util.LinkedList;

// 用链表作为底层数据结构实现栈
public class MyLinkedStack<E> {
    private final LinkedList<E> list = new LinkedList<>();

    // 向栈顶加入元素，时间复杂度 O(1)
    public void push(E e) {
        list.addLast(e);
    }

    // 从栈顶弹出元素，时间复杂度 O(1)
    public E pop() {
        return list.removeLast();
    }

    // 查看栈顶元素，时间复杂度 O(1)
    public E peek() {
        return list.getLast();
    }

    // 返回栈中的元素个数，时间复杂度 O(1)
    public int size() {
        return list.size();
    }

    public static void main(String[] args) {
        MyLinkedStack<Integer> stack = new MyLinkedStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.peek()); // 3
        System.out.println(stack.pop()); // 3
        System.out.println(stack.peek()); // 2
    }
}

cpp 🤖

// 用链表作为底层数据结构实现栈
#include <list>
#include <iostream>

template<typename E>
class MyLinkedStack {
private:
    std::list<E> list;

public:
    // 向栈顶加入元素，时间复杂度 O(1)
    void push(const E &e) {
        list.push_back(e);
    }

    // 从栈顶弹出元素，时间复杂度 O(1)
    E pop() {
        E value = list.back();
        list.pop_back();
        return value;
    }

    // 查看栈顶元素，时间复杂度 O(1)
    E peek() const {
        return list.back();
    }

    // 返回栈中的元素个数，时间复杂度 O(1)
    int size() const {
        return list.size();
    }
};

int main() {
    MyLinkedStack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    while (stack.size() > 0) {
        std::cout << stack.pop() << std::endl;
    }
    return 0;
}

python 🤖

from collections import deque

# 用链表作为底层数据结构实现栈
# Python 的 deque 就是双链表
class MyLinkedStack:
    def __init__(self):
        self.list = deque()

    # 向栈顶加入元素，时间复杂度 O(1)
    def push(self, e):
        self.list.append(e)

    # 从栈顶弹出元素，时间复杂度 O(1)
    def pop(self):
        return self.list.pop()

    # 查看栈顶元素，时间复杂度 O(1)
    def peek(self):
        return self.list[-1]

    # 返回栈中的元素个数，时间复杂度 O(1)
    def size(self):
        return len(self.list)


if __name__ == "__main__":
    stack = MyLinkedStack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print(stack.pop())
    print(stack.peek())
    print(stack.size())

go 🤖

import "container/list"

// 用链表作为底层数据结构实现栈
type MyLinkedStack struct {
    list *list.List
}

func NewMyLinkedStack() *MyLinkedStack {
    return &MyLinkedStack{list: list.New()}
}

// 向栈顶加入元素，时间复杂度 O(1)
func (s *MyLinkedStack) Push(e interface{}) {
    s.list.PushBack(e)
}

// 从栈顶弹出元素，时间复杂度 O(1)
func (s *MyLinkedStack) Pop() interface{} {
    element := s.list.Back()
    if element != nil {
        s.list.Remove(element)
        return element.Value
    }
    return nil
}

// 查看栈顶元素，时间复杂度 O(1)
func (s *MyLinkedStack) Peek() interface{} {
    element := s.list.Back()
    if element != nil {
        return element.Value
    }
    return nil
}

// 返回栈中的元素个数，时间复杂度 O(1)
func (s *MyLinkedStack) Size() int {
    return s.list.Len()
}

// test
func main() {
    stack := NewMyLinkedStack()
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    fmt.Println(stack.Pop()) // 3
    fmt.Println(stack.Pop()) // 2
    fmt.Println(stack.Peek()) // 1
}

javascript 🤖

// 用链表作为底层数据结构实现栈
// JavaScript 没有内置的双链表，这里只能用数组代替
// 不过你也可以参照前文双链表的实现，自己实现一个 JS 双链表
class MyLinkedStack {
    constructor() {
        this.list = [];
    }

    // 向栈顶加入元素，时间复杂度 O(1)
    push(e) {
        this.list.push(e);
    }

    // 从栈顶弹出元素，时间复杂度 O(1)
    pop() {
        return this.list.pop();
    }

    // 查看栈顶元素，时间复杂度 O(1)
    peek() {
        return this.list[this.list.length - 1];
    }

    // 返回栈中的元素个数，时间复杂度 O(1)
    size() {
        return this.list.length;
    }
}

// test
const stack = new MyLinkedStack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.pop()); // 2
console.log(stack.peek()); // 1

提示

上面这段代码相当于是把双链表的尾部作为栈顶，在双链表尾部增删元素的时间复杂度都是 O(1)，符合要求。

当然，你也可以把双链表的头部作为栈顶，因为双链表头部增删元素的时间复杂度也是 O(1)，所以这样实现也是一样的。只要做几个修改 addLast -> addFirst，removeLast -> removeFirst，getLast -> getFirst 就行了。

用链表实现队列

同理，用链表实现队列也是一样的，也直接调用双链表的 API 就可以了：

java 🟢

import java.util.LinkedList;

// 用链表作为底层数据结构实现队列
public class MyLinkedQueue<E> {
    private final LinkedList<E> list = new LinkedList<>();

    // 向队尾插入元素，时间复杂度 O(1)
    public void push(E e) {
        list.addLast(e);
    }

    // 从队头删除元素，时间复杂度 O(1)
    public E pop() {
        return list.removeFirst();
    }

    // 查看队头元素，时间复杂度 O(1)
    public E peek() {
        return list.getFirst();
    }

    // 返回队列中的元素个数，时间复杂度 O(1)
    public int size() {
        return list.size();
    }

    public static void main(String[] args) {
        MyLinkedQueue<Integer> queue = new MyLinkedQueue<>();
        queue.push(1);
        queue.push(2);
        queue.push(3);

        System.out.println(queue.peek()); // 1
        System.out.println(queue.pop()); // 1
        System.out.println(queue.pop()); // 2
        System.out.println(queue.peek()); // 3
    }
}

cpp 🤖

// 用链表作为底层数据结构实现队列
#include <iostream>
#include <list>


template<typename E>
class MyLinkedQueue {
private:
    std::list<E> list;

public:
    // 向队尾插入元素，时间复杂度 O(1)
    void push(const E &e) {
        list.push_back(e);
    }

    // 从队头删除元素，时间复杂度 O(1)
    E pop() {
        E front = list.front();
        list.pop_front();
        return front;
    }

    // 查看队头元素，时间复杂度 O(1)
    E peek() {
        return list.front();
    }

    // 返回队列中的元素个数，时间复杂度 O(1)
    int size() {
        return list.size();
    }
};

int main() {
    MyLinkedQueue<int> queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);

    std::cout << queue.peek() << std::endl; // 1
    std::cout << queue.pop() << std::endl; // 1
    std::cout << queue.pop() << std::endl; // 2
    std::cout << queue.peek() << std::endl; // 3

    return 0;
}

python 🤖

# deque 是 Python 的双链表
from collections import deque

# 用链表作为底层数据结构实现队列
# Python 的 deque 就是双链表
class MyLinkedQueue:
    def __init__(self):
        self.list = deque()

    # 向队尾插入元素，时间复杂度 O(1)
    def push(self, e):
        self.list.append(e)

    # 从队头删除元素，时间复杂度 O(1)
    def pop(self):
        return self.list.popleft()

    # 查看队头元素，时间复杂度 O(1)
    def peek(self):
        return self.list[0]

    # 返回队列中的元素个数，时间复杂度 O(1)
    def size(self):
        return len(self.list)

if __name__ == "__main__":
    queue = MyLinkedQueue()
    queue.push(1)
    queue.push(2)
    queue.push(3)
    print(queue.peek()) # 1
    print(queue.pop()) # 1
    print(queue.pop()) # 2
    print(queue.peek()) # 3

go 🤖

import (
	"container/list"
	"fmt"
)

// 用链表作为底层数据结构实现队列
type MyLinkedQueue struct {
	list *list.List
}

// 构造函数
func NewMyLinkedQueue() *MyLinkedQueue {
	return &MyLinkedQueue{list: list.New()}
}

// 向队尾插入元素，时间复杂度 O(1)
func (q *MyLinkedQueue) Push(e interface{}) {
	q.list.PushBack(e)
}

// 从队头删除元素，时间复杂度 O(1)
func (q *MyLinkedQueue) Pop() interface{} {
	front := q.list.Front()
	if front != nil {
		return q.list.Remove(front)
	}
	return nil
}

// 查看队头元素，时间复杂度 O(1)
func (q *MyLinkedQueue) Peek() interface{} {
	front := q.list.Front()
	if front != nil {
		return front.Value
	}
	return nil
}

// 返回队列中的元素个数，时间复杂度 O(1)
func (q *MyLinkedQueue) Size() int {
	return q.list.Len()
}


func main() {
	queue := NewMyLinkedQueue()
	queue.Push(1)
	queue.Push(2)
	queue.Push(3)
	fmt.Println(queue.Peek()) // 1
	fmt.Println(queue.Pop())  // 1
	fmt.Println(queue.Pop())  // 2
	fmt.Println(queue.Peek()) // 3
}

javascript 🤖

// 用链表作为底层数据结构实现队列
// JavaScript 没有内置的双链表，这里先用数组代替
// 但是需要注意，数组的头部增删元素的时间复杂度是 O(n)，即 shift() 方法的复杂度是 O(n)
// 当然，如果你参照前文自己实现一个 JS 双链表，就能真正实现队列的 O(1) 复杂度了
class MyLinkedQueue {
    constructor() {
        this.list = [];
    }

    // 向队尾插入元素，时间复杂度 O(1)
    push(e) {
        this.list.push(e);
    }

    // 从队头删除元素，理论时间复杂度是 O(1)
    // 但由于我们这里底层使用的 JavaScript 数组，所以实际的时间复杂度是 O(n)
    pop() {
        return this.list.shift();
    }

    // 查看队头元素，时间复杂度 O(1)
    peek() {
        return this.list[0];
    }

    // 返回队列中的元素个数，时间复杂度 O(1)
    size() {
        return this.list.length;
    }
}

// test
const queue = new MyLinkedQueue();
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue.peek()); // 1
console.log(queue.pop()); // 1
console.log(queue.pop()); // 2
console.log(queue.peek()); // 3

提示

上面这段代码相当于是把双链表的尾部作为队尾，把双链表的头部作为队头，在双链表的头尾增删元素的复杂度都是 O(1)，符合队列 API 的要求。

当然，你也可以反过来，把双链表的头部作为队尾，双链表的尾部作为队头。类似栈的实现，只要改一改 list 的调用方法就行了。

文末思考

双链表他比较牛，队列和栈的 API 考不倒它。但是你想一下，数组实现队列的时候，会不会有问题？

队列 API 要求一端增加元素，一端删除元素，而数组的头部无论是增加还是删除元素，时间复杂度都是 $O(n)$ 。这种情况下，有没有办法优化呢？

你可以思考一下，下一章我会告诉你答案。