欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法之队列

程序员文章站 2022-05-04 12:37:08
...

队列

数据结构与算法之队列

定义

**队列(Queue)**是一种操作受限的线性表,操作特性是“先进先出”,类似于日常生活中的排队。

实现

队列的实现可以使用数组也可以使用链表(以下代码均用c++实现)。

数组实现

.h

/**
 * Created by Liam Huang (Liam0205) on 2018/10/10.
 */

#ifndef QUEUE_ARRAY_QUEUE_HPP_
#define QUEUE_ARRAY_QUEUE_HPP_

template <typename T>
class ArrayQueue {
  private:
    T*     items_    = nullptr;
    size_t capacity_ = 0;
    size_t head_     = 0;
    size_t tail_     = 0;

  public:
    ArrayQueue() = delete;
    ArrayQueue(const size_t capacity) : capacity_(capacity) {
        items_ = new T[capacity_];
    }
    ~ArrayQueue() {
        if (nullptr != items_) {
            delete[] items_;
            items_ = nullptr;
        }
    }
    ArrayQueue(const ArrayQueue& other) : capacity_(other.capacity_) {
        items_ = new T[capacity_];
        for (size_t i = other.head_; i != other.tail_; ++i) {
            enqueue(other.items_[i]);
        }
    }
    ArrayQueue& operator=(const ArrayQueue& rhs) {
        delete[] items_;
        head_     = 0;
        tail_     = 0;
        capacity_ = rhs.capacity_;
        items_    = new T[capacity_];
        for (size_t i = rhs.head_; i != rhs.tail_; ++i) {
            enqueue(rhs.items_[i]);
        }
        return *this;
    }
    ArrayQueue(ArrayQueue&& other) : items_(other.items_),
                                     capacity_(other.capacity_),
                                     head_(other.head_),
                                     tail_(other.tail_) {
        other.items_    = nullptr;
        other.capacity_ = 0;
        other.head_     = 0;
        other.tail_     = 0;
    }
    ArrayQueue& operator=(ArrayQueue&& rhs) {
        delete[] items_;
        items_        = rhs.items_;
        capacity_     = rhs.capacity_;
        head_         = rhs.head_;
        tail_         = rhs.tail_;
        rhs.items_    = nullptr;
        rhs.capacity_ = 0;
        rhs.head_     = 0;
        rhs.tail_     = 0;
        return *this;
    }

  public:
    void enqueue(T item) {
        if (capacity_ == tail_) {
            throw "Push data into a full queue!";
        }
        items_[tail_++] = item;
    }
    T head() const {
        if (head_ != tail_) {
            return items_[head_];
        } else {
            throw "Fetch data from an empty queue!";
        }
    }
    void dequeue() {
        if (head_ != tail_) {
            ++head_;
        } else {
            throw "Pop data from an empty queue!";
        }
    }

  public:
    template <typename UnaryFunc>
    void traverse(UnaryFunc do_traverse) {
        for (size_t i = head_; i != tail_; ++i) {
            do_traverse(items_[i]);
        }
    }
};

#endif  // QUEUE_ARRAY_QUEUE_HPP_

.cpp

  
#include <iostream>
#include "array_queue.hpp"

int main() {
    auto do_traverse = [&](auto item){ std::cout << item << ' '; };

    ArrayQueue<int> array_queue_1(3);
    array_queue_1.enqueue(1);
    array_queue_1.enqueue(2);
    array_queue_1.enqueue(3);
    // array_queue_1.enqueue(4);  // throw
    array_queue_1.traverse(do_traverse);
    std::cout << std::endl;

    ArrayQueue<int> array_queue_2(array_queue_1);  // copy constructor
    array_queue_2.traverse(do_traverse);
    std::cout << std::endl;

    ArrayQueue<int> array_queue_3(std::move(array_queue_2));  // move constructor
    array_queue_3.traverse(do_traverse);
    std::cout << std::endl;
    array_queue_2.traverse(do_traverse);
    std::cout << std::endl;

    std::cout << array_queue_3.head() << std::endl;
    array_queue_3.dequeue();
    std::cout << array_queue_3.head() << std::endl;
    array_queue_3.dequeue();
    std::cout << array_queue_3.head() << std::endl;
    array_queue_3.dequeue();
    // std::cout << array_queue_3.head() << std::endl;  // throw
    // array_queue_3.dequeue();  // throw

    ArrayQueue<int> array_queue_4(1);
    array_queue_4 = array_queue_1;  // copy assignment
    array_queue_4.traverse(do_traverse);
    std::cout << std::endl;

    ArrayQueue<int> array_queue_5(100);
    array_queue_5 = std::move(array_queue_4);  // move assignment
    array_queue_5.traverse(do_traverse);
    std::cout << std::endl;
    array_queue_4.traverse(do_traverse);
    std::cout << std::endl;

    std::cout << array_queue_5.head() << std::endl;
    array_queue_5.dequeue();
    std::cout << array_queue_5.head() << std::endl;
    array_queue_5.dequeue();
    std::cout << array_queue_5.head() << std::endl;
    array_queue_5.dequeue();
    // std::cout << array_queue_5.head() << std::endl;  // throw
    // array_queue_5.dequeue();  // throw

    return 0;
}

若队列末尾没有空间了,但前面还有,则对数据进行搬移。

//数据搬移

   // 入队操作,将item放入队尾
  public boolean enqueue(String item) {
    // tail == n表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0,表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新head和tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

用链表实现

.h

/**
 * Created by Liam Huang (Liam0205) on 2018/10/10.
 */

#ifndef QUEUE_LINKED_QUEUE_HPP_
#define QUEUE_LINKED_QUEUE_HPP_

#include <memory>

template <typename T>
struct Node {
    using ptr_t = std::shared_ptr<Node<T>>;
    T     data;
    ptr_t next;

    Node(T data_) : data(data_), next(nullptr) {}
    Node() : next(nullptr) {}
};

template <typename T>
class LinkedQueue {
  public:
    using node_type  = Node<T>;
    using node_ptr_t = typename node_type::ptr_t;

  private:
    node_ptr_t head_        = nullptr;
    node_ptr_t before_tail_ = nullptr;

  public:
    LinkedQueue()  = default;
    ~LinkedQueue() = default;
    LinkedQueue(const LinkedQueue& other) = default;
    LinkedQueue& operator=(const LinkedQueue& rhs) = default;
    LinkedQueue(LinkedQueue&& other) = default;
    LinkedQueue& operator=(LinkedQueue&& rhs) = default;

  public:
    void enqueue(T item) {
        if (nullptr == head_) {
            head_ = std::make_shared<node_type>(item);
            before_tail_ = head_;
        } else {
            before_tail_->next = std::make_shared<node_type>(item);
            before_tail_ = before_tail_->next;
        }
    }
    T head() const {
        if (nullptr != head_) {
            return head_->data;
        } else {
            throw "Fetch data from an empty queue!";
        }
    }
    void dequeue() {
        if (nullptr != head_) {
            head_ = head_->next;
            if (nullptr == head_) {
                before_tail_ = nullptr;
            }
        } else {
            throw "Pop data from an empty queue!";
        }
    }

  public:
    template <typename UnaryFunc>
    void traverse(UnaryFunc do_traverse) {
        for (node_ptr_t work = head_; nullptr != work; work = work->next) {
            do_traverse(work->data);
        }
    }
};

#endif  // QUEUE_LINKED_QUEUE_HPP_

.cpp

#include <iostream>
#include "linked_queue.hpp"

int main() {
    auto do_traverse = [&](auto item){ std::cout << item << ' '; };

    LinkedQueue<int> linked_queue_1;
    linked_queue_1.enqueue(1);
    linked_queue_1.enqueue(2);
    linked_queue_1.enqueue(3);
    linked_queue_1.traverse(do_traverse);
    std::cout << std::endl;

    LinkedQueue<int> linked_queue_2(linked_queue_1);  // copy constructor
    linked_queue_2.traverse(do_traverse);
    std::cout << std::endl;

    LinkedQueue<int> linked_queue_3(std::move(linked_queue_2));  // move constructor
    linked_queue_3.traverse(do_traverse);
    std::cout << std::endl;
    linked_queue_2.traverse(do_traverse);
    std::cout << std::endl;

    std::cout << linked_queue_3.head() << std::endl;
    linked_queue_3.dequeue();
    std::cout << linked_queue_3.head() << std::endl;
    linked_queue_3.dequeue();
    std::cout << linked_queue_3.head() << std::endl;
    linked_queue_3.dequeue();
    // std::cout << linked_queue_3.head() << std::endl;  // throw
    // linked_queue_3.dequeue();  // throw

    LinkedQueue<int> linked_queue_4;
    linked_queue_4 = linked_queue_1;  // copy assignment
    linked_queue_4.traverse(do_traverse);
    std::cout << std::endl;

    LinkedQueue<int> linked_queue_5;
    linked_queue_5 = std::move(linked_queue_4);  // move assignment
    linked_queue_5.traverse(do_traverse);
    std::cout << std::endl;
    linked_queue_4.traverse(do_traverse);
    std::cout << std::endl;

    std::cout << linked_queue_5.head() << std::endl;
    linked_queue_5.dequeue();
    std::cout << linked_queue_5.head() << std::endl;
    linked_queue_5.dequeue();
    std::cout << linked_queue_5.head() << std::endl;
    linked_queue_5.dequeue();
    // std::cout << linked_queue_5.head() << std::endl;  // throw
    // linked_queue_5.dequeue();  // throw

    return 0;
}

应用

队列的应用主要有循环队列、阻塞队列、并发队列以及阻塞并发队列。

循环队列把顺序队列从逻辑上视作一个环状队列,而要实现一个循环队列,要着重注意以下几点:

1.队空:head == tail

2.队满:队满:(tail+1)%n == head

3.入队时队尾指针进1:tail = ( tail+1)% n

4.出队时队首指针进1:head = (head + 1) % n

5.循环队列会浪费一个存储空间,因为tail指向的位置是不存放数据的。

循环队列实现

.h

/**
 * Created by Liam Huang (Liam0205) on 2018/10/10.
 */

#ifndef QUEUE_CIRCULAR_QUEUE_HPP_
#define QUEUE_CIRCULAR_QUEUE_HPP_

template <typename T>
class CircularQueue {
  private:
    T*     items_    = nullptr;
    size_t capacity_ = 0;
    size_t head_     = 0;
    size_t tail_     = 0;

  public:
    CircularQueue() = delete;
    CircularQueue(const size_t capacity) : capacity_(capacity) {
        items_ = new T[capacity_];
    }
    ~CircularQueue() {
        if (nullptr != items_) {
            delete[] items_;
            items_ = nullptr;
        }
    }
    CircularQueue(const CircularQueue& other) : capacity_(other.capacity_) {
        items_ = new T[capacity_];
        for (size_t i = other.head_; i != other.tail_; ++i) {
            enqueue(other.items_[i]);
        }
    }
    CircularQueue& operator=(const CircularQueue& rhs) {
        delete[] items_;
        head_     = 0;
        tail_     = 0;
        capacity_ = rhs.capacity_;
        items_    = new T[capacity_];
        for (size_t i = rhs.head_; i != rhs.tail_; ++i) {
            enqueue(rhs.items_[i]);
        }
        return *this;
    }
    CircularQueue(CircularQueue&& other) : items_(other.items_),
                                     capacity_(other.capacity_),
                                     head_(other.head_),
                                     tail_(other.tail_) {
        other.items_    = nullptr;
        other.capacity_ = 0;
        other.head_     = 0;
        other.tail_     = 0;
    }
    CircularQueue& operator=(CircularQueue&& rhs) {
        delete[] items_;
        items_        = rhs.items_;
        capacity_     = rhs.capacity_;
        head_         = rhs.head_;
        tail_         = rhs.tail_;
        rhs.items_    = nullptr;
        rhs.capacity_ = 0;
        rhs.head_     = 0;
        rhs.tail_     = 0;
        return *this;
    }

  public:
    void enqueue(T item) {
        if ((tail_ + 1) % capacity_ == head_) {
            throw "Push data into a full queue!";
        }
        items_[tail_] = item;
        tail_ = (tail_ + 1) % capacity_;
    }
    T head() const {
        if (head_ != tail_) {
            return items_[head_];
        } else {
            throw "Fetch data from an empty queue!";
        }
    }
    void dequeue() {
        if (head_ != tail_) {
            head_ = (head_ + 1) % capacity_;
        } else {
            throw "Pop data from an empty queue!";
        }
    }

  public:
    template <typename UnaryFunc>
    void traverse(UnaryFunc do_traverse) {
        if (0 == capacity_) return;
        for (size_t i = head_; i % capacity_ != tail_; ++i) {
            do_traverse(items_[i % capacity_]);
        }
    }
};

#endif  // QUEUE_CIRCULAR_QUEUE_HPP_

.cpp

#include <iostream>
#include "circular_queue.hpp"

int main() {
    auto do_traverse = [&](auto item){ std::cout << item << ' '; };

    CircularQueue<int> circular_queue_1(4);
    circular_queue_1.enqueue(1);
    circular_queue_1.enqueue(2);
    circular_queue_1.enqueue(3);
    // circular_queue_1.enqueue(4);  // throw
    circular_queue_1.traverse(do_traverse);
    std::cout << std::endl;

    CircularQueue<int> circular_queue_2(circular_queue_1);  // copy constructor
    circular_queue_2.traverse(do_traverse);
    std::cout << std::endl;

    CircularQueue<int> circular_queue_3(std::move(circular_queue_2));  // move constructor
    circular_queue_3.traverse(do_traverse);
    std::cout << std::endl;
    circular_queue_2.traverse(do_traverse);
    std::cout << std::endl;

    std::cout << circular_queue_3.head() << std::endl;
    circular_queue_3.dequeue();
    std::cout << circular_queue_3.head() << std::endl;
    circular_queue_3.dequeue();
    std::cout << circular_queue_3.head() << std::endl;
    circular_queue_3.dequeue();
    // std::cout << circular_queue_3.head() << std::endl;  // throw
    // circular_queue_3.dequeue();  // throw

    CircularQueue<int> circular_queue_4(1);
    circular_queue_4 = circular_queue_1;  // copy assignment
    circular_queue_4.traverse(do_traverse);
    std::cout << std::endl;

    CircularQueue<int> circular_queue_5(100);
    circular_queue_5 = std::move(circular_queue_4);  // move assignment
    circular_queue_5.traverse(do_traverse);
    std::cout << std::endl;
    circular_queue_4.traverse(do_traverse);
    std::cout << std::endl;

    std::cout << circular_queue_5.head() << std::endl;
    circular_queue_5.dequeue();
    std::cout << circular_queue_5.head() << std::endl;
    circular_queue_5.dequeue();
    std::cout << circular_queue_5.head() << std::endl;
    circular_queue_5.dequeue();
    // std::cout << circular_queue_5.head() << std::endl;  // throw
    // circular_queue_5.dequeue();  // throw

    for (size_t i = 0; i != 4; ++i) {
        circular_queue_1.dequeue();
        circular_queue_1.enqueue(i + 4);
        circular_queue_1.traverse(do_traverse);
        std::cout << std::endl;
    }
    return 0;
}