用链表实现队列-栈

labuladong原创约 1276 字

用链表实现栈

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

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

java 🟢

// 用链表作为底层数据结构实现栈
public class MyLinkedStack<E> {
    private 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();
    }
}

cpp 🤖

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

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();
    }
};

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)

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()
}

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;
    }
}

提示

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

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

用链表实现队列

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

java 🟢

// 用链表作为底层数据结构实现队列
public class MyLinkedQueue<E> {
    private 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();
    }
}

cpp 🤖

// 用链表作为底层数据结构实现队列
#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();
    }
};

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)

go 🤖

import "container/list"

// 用链表作为底层数据结构实现队列
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()
}

javascript 🤖

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

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

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

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

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

提示

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

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

文末思考

通过前面的代码实现，你应该可以理解，为什么我在学习数据结构和算法的框架思维中说的：数据结构的存储方式只有顺序存储（数组）和链式存储（链表）两种，其他数据结构都是基于这两种基本数据结构玩出的花样。

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

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

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