用链表实现队列-栈

Implementing a Stack with a Linked List

Some readers may already know how to implement a queue and a stack using a linked list as the underlying data structure. It's quite simple, really; you can just directly use the API of a doubly linked list.

Note that I'm directly using Java's standard library LinkedList here. If you use our previously implemented MyLinkedList, it would work just as well.

java 🟢

// Implement a stack using linked list as the underlying data structure
public class MyLinkedStack<E> {
    private LinkedList<E> list = new LinkedList<>();

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

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

    // Look at the top element of the stack, time complexity O(1)
    public E peek() {
        return list.getLast();
    }

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

cpp 🤖

// Implement a stack using linked list as the underlying data structure
#include <list>

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

public:
    // Add an element to the top of the stack, time complexity O(1)
    void push(const E& e) {
        list.push_back(e);
    }

    // Pop an element from the top of the stack, time complexity O(1)
    E pop() {
        E value = list.back();
        list.pop_back();
        return value;
    }

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

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

python 🤖

from collections import deque

# Implement stack using linked list as underlying data structure
# Python's deque is a double-ended linked list
class MyLinkedStack:
    def __init__(self):
        self.list = deque()

    # 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 "container/list"

// use linked list as the underlying data structure to implement a stack
type MyLinkedStack struct {
    list *list.List
}

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

// push an element to the top of the stack, time complexity O(1)
func (s *MyLinkedStack) Push(e interface{}) {
    s.list.PushBack(e)
}

// pop an element from the top of the stack, time complexity O(1)
func (s *MyLinkedStack) Pop() interface{} {
    element := s.list.Back()
    if element != nil {
        s.list.Remove(element)
        return element.Value
    }
    return nil
}

// peek the top element of the stack, time complexity O(1)
func (s *MyLinkedStack) Peek() interface{} {
    element := s.list.Back()
    if element != nil {
        return element.Value
    }
    return nil
}

// return the number of elements in the stack, time complexity O(1)
func (s *MyLinkedStack) Size() int {
    return s.list.Len()
}

javascript 🤖

// use linked list as the underlying data structure to implement stack
// JavaScript does not have a built-in doubly linked list, so an array is used here instead
// However, you can refer to the previous implementation of a doubly linked list and implement your own JS doubly linked list
class MyLinkedStack {
    constructor() {
        this.list = [];
    }

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

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

    // peek at 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;
    }
}

Tip

The above code essentially treats the tail of the doubly linked list as the top of the stack. The time complexity for adding or removing elements at the end of the doubly linked list is O(1), which meets the requirements.

Of course, you could also use the head of the doubly linked list as the top of the stack, as the time complexity for adding or removing elements at the head is also O(1). The implementation would be just as valid. You only need to make a few changes: addLast -> addFirst, removeLast -> removeFirst, getLast -> getFirst, and you're set.

Implementing a Queue with a Linked List

Similarly, implementing a queue with a linked list is just as straightforward. You can directly use the API of the doubly linked list:

java 🟢

// use LinkedList as the underlying data structure to implement the queue
public class MyLinkedQueue<E> {
    private LinkedList<E> list = new LinkedList<>();

    // insert element to the end of the queue, time complexity O(1)
    public void push(E e) {
        list.addLast(e);
    }

    // remove element from the front of the queue, time complexity O(1)
    public E pop() {
        return list.removeFirst();
    }

    // view the front element of the queue, time complexity O(1)
    public E peek() {
        return list.getFirst();
    }

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

cpp 🤖

// Implement a queue using a linked list as the underlying data structure
#include <list>

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

public:
    // Insert an element at the end of the queue, time complexity O(1)
    void push(const E& e) {
        list.push_back(e);
    }

    // Remove an element from the front of the queue, time complexity O(1)
    E pop() {
        E front = list.front();
        list.pop_front();
        return front;
    }

    // View the front element of the queue, time complexity O(1)
    E peek() {
        return list.front();
    }

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

python 🤖

from collections import deque

# use a linked list as the underlying data structure to implement the queue
# Python's deque is a doubly linked list
class MyLinkedQueue:
    def __init__(self):
        self.list = deque()

    # insert an element at the end of the queue, time complexity O(1)
    def push(self, e):
        self.list.append(e)

    # remove an element from the head of the queue, time complexity O(1)
    def pop(self):
        return self.list.popleft()

    # view the element at the head of the queue, time complexity O(1)
    def peek(self):
        return self.list[0]

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

go 🤖

import "container/list"

// Implement queue using a linked list as the underlying data structure
type MyLinkedQueue struct {
    list *list.List
}

// Constructor
func NewMyLinkedQueue() *MyLinkedQueue {
    return &MyLinkedQueue{list: list.New()}
}

// Insert an element at the end of the queue, time complexity O(1)
func (q *MyLinkedQueue) Push(e interface{}) {
    q.list.PushBack(e)
}

// Remove an element from the front of the queue, time complexity O(1)
func (q *MyLinkedQueue) Pop() interface{} {
    front := q.list.Front()
    if front != nil {
        return q.list.Remove(front)
    }
    return nil
}

// View the front element, time complexity O(1)
func (q *MyLinkedQueue) Peek() interface{} {
    front := q.list.Front()
    if front != nil {
        return front.Value
    }
    return nil
}

// Return the number of elements in the queue, time complexity O(1)
func (q *MyLinkedQueue) Size() int {
    return q.list.Len()
}

javascript 🤖

// Implement a queue using a linked list as the underlying data structure
// JavaScript does not have a built-in doubly linked list, so we use an array here
// However, you can refer to the previous implementation of a doubly linked list and implement a JS doubly linked list yourself
class MyLinkedQueue {
    constructor() {
        this.list = [];
    }

    // Insert an element at the end of the queue, time complexity O(1)
    push(e) {
        this.list.push(e);
    }

    // Remove an element from the front of the queue, time complexity O(1)
    pop() {
        return this.list.shift();
    }

    // Peek at the front element of the queue, time complexity O(1)
    peek() {
        return this.list[0];
    }

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

Hint

The above code essentially treats the tail of a doubly linked list as the rear of a queue and the head as the front. Adding or removing elements at both ends of a doubly linked list has a complexity of O(1), which meets the requirements of the queue API.

Of course, you can also reverse this by treating the head of the doubly linked list as the rear and the tail as the front. Similar to implementing a stack, you only need to change the list's method calls.

Thought at the End

Through the previous code implementation, you should understand why I mentioned in Framework Thinking for Learning Data Structures and Algorithms: There are only two ways to store data structures—sequential storage (arrays) and linked storage (linked lists). Other data structures are variations based on these two fundamental storage methods.

Doubly linked lists are quite powerful; queue and stack APIs cannot stump them. But think about it, when implementing a queue with arrays, could there be a problem?

The queue API requires adding elements at one end and removing elements at the other. However, adding or removing elements at the head of an array has a time complexity of O(n). In this case, is there a way to optimize it?

Think about it, and I will tell you the answer in the next chapter.