数据结构与算法之队列
程序员文章站
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;
}
上一篇: JSP 中EL表达式用法详解
下一篇: day26-python之封装