用数组实现队列/栈

labuladong原创约 694 字

前置知识

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

队列/栈基本原理

这篇文章带大家用数组作为底层数据结构实现队列和栈。

用数组实现栈

先用数组实现栈，这个不难，你把动态数组的尾部作为栈顶，然后调用动态数组的 API 就行了。因为数组尾部增删元素的时间复杂度都是 $O(1)$ ，符合栈的要求。

注意我这里用的是 Java 标准库的 ArrayList，如果你想用之前我们实现的 MyArrayList，也是一样的：

java 🟢

// 用数组作为底层数据结构实现栈
public class MyArrayStack<E> {
    private ArrayList<E> list = new ArrayList<>();

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

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

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

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

cpp 🤖

// 用数组作为底层数据结构实现栈
#include <vector>

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

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

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

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

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

python 🤖

# 用数组作为底层数据结构实现栈
class MyArrayStack:
    def __init__(self):
        self.list = []

    # 向栈顶加入元素，时间复杂度 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 "fmt"

// MyArrayStack 用数组切片作为底层数据结构实现栈
type MyArrayStack[T any] struct {
    list []T
}

// 向栈顶加入元素，时间复杂度 O(1)
func (s *MyArrayStack[T]) Push(e T) {
    s.list = append(s.list, e)
}

// 从栈顶弹出元素，时间复杂度 O(1)
func (s *MyArrayStack[T]) Pop() T {
    if len(s.list) == 0 {
        var zero T
        return zero
    }
    e := s.list[len(s.list)-1]
    s.list = s.list[:len(s.list)-1]
    return e
}

// 查看栈顶元素，时间复杂度 O(1)
func (s *MyArrayStack[T]) Peek() T {
    if len(s.list) == 0 {
        var zero T
        return zero
    }
    return s.list[len(s.list)-1]
}

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

javascript 🤖

// 用数组作为底层数据结构实现栈
class MyArrayStack {
    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;
    }
}

能否让数组的头部作为栈顶？

按照我们之前实现 MyArrayList 的逻辑，是不行的。因为数组头部增删元素的时间复杂度都是 $O(n)$ ，不符合要求。

但是我们可以改用前文环形数组技巧中实现的 CycleArray 类，这个数据结构在头部增删元素的时间复杂度是 $O(1)$ ，符合栈的要求。

你直接调用 CycleArray 的 addFirst 和 removeFirst 方法实现栈的 API 就行，我这里就不写了。

用数组实现队列

有了前文环形数组中实现的 CycleArray 类，用数组作为底层数据结构实现队列就不难了吧。直接复用我们实现的 CycleArray，就可以实现标准队列了。当然，一些编程语言也有内置的环形数组实现，你也可以自行搜索使用：

java 🟢

public class MyArrayQueue<E> {
    private CycleArray<E> arr;

    public MyArrayQueue() {
        arr = new CycleArray<>();
    }

    public void push(E t) {
        arr.addLast(t);
    }

    public E pop() {
        return arr.removeFirst();
    }

    public E peek() {
        return arr.getFirst();
    }

    public int size() {
        return arr.size();
    }
}

cpp 🤖

#include <iostream>
#include <deque>

template <typename E>
class MyArrayQueue {
private:
    CycleArray<E> arr;

public:
    MyArrayQueue() {
        arr = CycleArray<E>();
    }

    void push(E t) {
        arr.addLast(t);
    }

    E pop() {
        return arr.removeFirst();
    }

    E peek() {
        return arr.getFirst();
    }

    int size() {
        return arr.size();
    }
};

python 🤖

class MyArrayQueue:
    def __init__(self):
        self.arr = CycleArray()

    def push(self, t):
        self.arr.add_last(t)

    def pop(self):
        return self.arr.remove_first()

    def peek(self):
        return self.arr.get_first()

    def size(self):
        return self.arr.size()

go 🤖

type MyArrayQueue[E any] struct {
    arr *CycleArray[E]
}

func NewMyArrayQueue[E any]() *MyArrayQueue[E] {
    return &MyArrayQueue[E]{
        arr: NewCycleArray[E](),
    }
}

func (q *MyArrayQueue[E]) Push(t E) {
    q.arr.AddLast(t)
}

func (q *MyArrayQueue[E]) Pop() E {
    return q.arr.RemoveFirst()
}

func (q *MyArrayQueue[E]) Peek() E {
    return q.arr.GetFirst()
}

func (q *MyArrayQueue[E]) Size() int {
    return q.arr.Size()
}

javascript 🤖

class MyArrayQueue {
    constructor() {
        this.arr = new CycleArray();
    }

    push(t) {
        this.arr.addLast(t);
    }

    pop() {
        return this.arr.removeFirst();
    }

    peek() {
        return this.arr.getFirst();
    }

    size() {
        return this.arr.size();
    }
}