用数组实现队列-栈

labuladong原创约 1051 字

This article guides you on how to implement a queue and a stack using an array as the underlying data structure.

Implementing a Stack with an Array

Let's start by implementing a stack with an array. This is not difficult. You can use the end of a dynamic array as the top of the stack and then call the dynamic array's API. Since adding and removing elements at the end of an array has a time complexity of O(1), it meets the requirements of a stack.

Note that I am using the Java standard library's ArrayList here. If you want to use the MyArrayList we implemented earlier, that works the same way:

java 🟢

// use array as the underlying data structure to implement stack
public class MyArrayStack<E> {
    private ArrayList<E> list = new ArrayList<>();

    // add element to the top of the stack, time complexity O(1)
    public void push(E e) {
        list.add(e);
    }

    // pop element from the top of the stack, time complexity O(1)
    public E pop() {
        return list.remove(list.size() - 1);
    }

    // peek the top element of the stack, time complexity O(1)
    public E peek() {
        return list.get(list.size() - 1);
    }

    // return the number of elements in the stack, time complexity O(1)
    public int size() {
        return list.size();
    }
}

cpp 🤖

// Implement stack using array as underlying data structure
#include <vector>

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

public:
    // Push element onto stack, time complexity O(1)
    void push(const E& e) {
        list.push_back(e);
    }

    // Pop element from stack, time complexity O(1)
    E pop() {
        E topElement = list.back();
        list.pop_back();
        return topElement;
    }

    // Peek at top element, time complexity O(1)
    E peek() const {
        return list.back();
    }

    // Return the number of elements in stack, time complexity O(1)
    int size() const {
        return list.size();
    }
};

python 🤖

# Implement stack using array as the underlying data structure
class MyArrayStack:
    def __init__(self):
        self.list = []

    # Add element to the top of the stack, time complexity O(1)
    def push(self, e):
        self.list.append(e)

    # Pop element from the top of the stack, time complexity O(1)
    def pop(self):
        return self.list.pop()

    # Peek at the top element of the stack, time complexity O(1)
    def peek(self):
        return self.list[-1]

    # Return the number of elements in the stack, time complexity O(1)
    def size(self):
        return len(self.list)

go 🤖

import "fmt"

// MyArrayStack uses a slice as the underlying data structure to implement a stack
type MyArrayStack[T any] struct {
    list []T
}

// Add an element to the top of the stack, time complexity O(1)
func (s *MyArrayStack[T]) Push(e T) {
    s.list = append(s.list, e)
}

// Pop an element from the top of the stack, time complexity 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
}

// View the top element of the stack, time complexity 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]
}

// Return the number of elements in the stack, time complexity O(1)
func (s *MyArrayStack[T]) Size() int {
    return len(s.list)
}

javascript 🤖

// Implement stack using array as the underlying data structure
class MyArrayStack {
    constructor() {
        this.list = [];
    }

    // Add element to the top of the stack, time complexity O(1)
    push(e) {
        this.list.push(e);
    }

    // Pop element from the top of the stack, time complexity O(1)
    pop() {
        return this.list.pop();
    }

    // Peek the top element of the stack, time complexity O(1)
    peek() {
        return this.list[this.list.length - 1];
    }

    // Return the number of elements in the stack, time complexity O(1)
    size() {
        return this.list.length;
    }
}

Can the Head of an Array Act as the Top of a Stack?

According to our previous implementation of MyArrayList, it's not feasible. Adding or removing elements at the head of an array has a time complexity of O(n), which does not meet the requirements.

However, we can use the CycleArray class implemented in the earlier section Circular Array Technique. This data structure allows adding and removing elements at the head with a time complexity of O(1), which meets the stack requirements.

You just need to call the addFirst and removeFirst methods of CycleArray to implement the stack API. I won't write it out here.

Implementing a Queue with an Array

With the CycleArray class we implemented in the earlier section Circular Array Technique, it shouldn't be difficult to use an array as the underlying data structure to implement a queue. Simply reuse the CycleArray we implemented to create a standard queue. Of course, some programming languages also have built-in circular array implementations, which you can search for and use:

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