用数组实现队列/栈

labuladong原创

前置知识

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

队列/栈基本原理

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

用数组实现栈

先用数组实现栈，这个不难，你把动态数组的尾部作为栈顶，然后调用动态数组的 API 就行了。因为数组尾部增删元素的时间复杂度都是 $O (1) 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)

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) O(n)$ ，不符合要求。

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

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

用数组实现队列

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