队列是一种特殊的线性表，只能在头尾两端进行操作；
先进先出的原则；
简单队列
使用两个栈去实现一个简单队列
template <class E>
class Queue {
public:
void push(E e) {
inStacker.push(e);
}
void pop() {
if (outStacker.empty()) {
while (!inStacker.empty()) {
E value = inStacker.top();
inStacker.pop();
outStacker.push(value);
}
}
outStacker.pop();
}
E peek() {
if (outStacker.empty()) {
while (!inStacker.empty()) {
E value = inStacker.top();
inStacker.pop();
outStacker.push(value);
}
}
return outStacker.top();
}
bool empty() {
return outStacker.empty() && inStacker.empty();
}
private:
std::stack<E> inStacker;
std::stack<E> outStacker;
};
双端队列
// 使用链表去实现双端队列
#include "LinkList.hpp"
template<class E>
class Deque {
public:
Deque() {
m_list = new LinkList<E>;
}
~Deque() {
delete m_list;
m_list = nullptr;
}
int size() {
return m_list->size();
}
bool isEmpey() {
return m_list->isEmpty();
}
void enQueueFront(E e) {
m_list->add(0, e);
}
E deQueueFront() {
return m_list->remove(0);
}
void enQueueRear(E e) {
m_list->add(e);
}
E deQueueRear() {
return m_list->remove(m_list->size()-1);
}
E front() {
return m_list->top();
}
E rear() {
return m_list->bottom();
}
private:
LinkList<E> *m_list;
};
循环队列
/* ArrayList存在哪些问题？
* 问题1 ：首位置移除元素时，其余全部元素需要移动
* 问题2 ：首位置添加元素时，其余全部元素需要移动
* 问题3 ：首位置添加多个元素，其余全部元素需要移动多次
* 问题4 ：中间添加元素/删除元素时，其后面的全部元素需要移动
*
* 进一步优化ArrayList：
* 解决：
* a添加first成员 记录首位置
* b构造为循环数组
* c插入/删除中间元素，比较两侧较少元素，只移动较少的元素
*
* 类似的解决方案：循环队列！
*/
#pragma once
#include <sstream>
static const int DEFAULT_CAPACITY_2 = 10;
template<class E>
class CircleQueue {
private:
E * m_elements;
int m_length;//容量
int m_size{0};//元素个数
public:
int m_front{0};//首元素index位置
explicit CircleQueue(int capacity = DEFAULT_CAPACITY_2)
: m_elements(new E[(capacity < DEFAULT_CAPACITY_2) ? DEFAULT_CAPACITY_2 : capacity]),
m_length((capacity < DEFAULT_CAPACITY_2) ? DEFAULT_CAPACITY_2 : capacity) {
}
~CircleQueue() {
delete[] m_elements;
}
//转换索引在循环数组中的真实索引
int index(int i) {
// return (i + m_front) % m_length;
//->优化 去掉%运算
i = i + m_front;
return i - (i >= m_length ? m_length : 0);
}
bool isEmpey() {
return m_size == 0;
}
void enQueue(E e) {
//满了呢？
if (m_size+1 > m_length) {
//进行扩容
ensureCapacity(m_size + 1);
}
m_elements[index(m_size)] = e;
m_size++;
}
E deQueue() {
if (m_size <= 0) {
return E();
}
E old = m_elements[index(0)];
m_elements[index(0)] = E();
m_size--;
if (m_size == 0) {
m_front = 0;
} else {
m_front = index(1);
}
return old;
}
E front() {
return m_elements[index(0)];
}
private:
void ensureCapacity(int capacity) {
int oldCapacity = m_length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E* newElements = new E[newCapacity];
for (int i = 0; i < this->m_size; i++) {
newElements[i] = m_elements[index(i)];
}
delete[] m_elements;
m_elements = newElements;
m_length = newCapacity;
m_front = 0;
std::cout << std::to_string(oldCapacity) << "扩容为" << std::to_string(newCapacity) << std::endl;
}
};
循环双端队列
#pragma once
#include <sstream>
/// 双端循环队列
/*
* 进一步优化方案
* 尽量避免乘* 除/ 模%、浮点数运算，效率低下
*/
static const int DEFAULT_CAPACITY_3 = 10;
template<class E>
class CircleDeque {
private:
E * m_elements;
int m_length;//容量
int m_size{0};//元素个数
public:
int m_front{0};//首元素index位置
explicit CircleDeque(int capacity = DEFAULT_CAPACITY_3)
: m_elements(new E[(capacity < DEFAULT_CAPACITY_3) ? DEFAULT_CAPACITY_3 : capacity]),
m_length((capacity < DEFAULT_CAPACITY_3) ? DEFAULT_CAPACITY_3 : capacity) {
}
~CircleDeque() {
delete[] m_elements;
}
std::string toString() {
std::ostringstream os;
os << "size = " << this->m_size
<< ", capcacity = " << m_length
<< ", front = " << m_front
<< ", 元素 = [";
for (int i = 0; i < this->m_size; i++) {
if (i != 0) {
os << ", ";
}
os << m_elements[index(i)] << "-i" << i << "-ii" << index(i);
}
os << "]" << std::endl;
std::cout << os.str() << std::endl;
return os.str();
}
//转换索引在循环数组中的真实索引
int index(int i) {
// int ii = i + m_front;
// if (ii < 0) {
// ii += m_length;
// }
// return ii % m_length;
//->优化 去掉%运算
i += m_front;
if (i < 0) {
return m_length+i;
}
return i - (i >= m_length ? m_length : 0);
}
bool isEmpey() {
return m_size == 0;
}
void enQueueFront(E e) {
ensureCapacity(m_size + 1);
if (m_size == 0) {
m_elements[0] = e;
m_size++;
} else {
m_front = index(-1);
m_elements[m_front] = e;
m_size++;
}
}
E deQueueFront() {
if (m_size <= 0) {
return E();
}
E old = m_elements[index(0)];
m_elements[index(0)] = E();
m_size--;
if (m_size == 0) {
m_front = 0;
} else {
m_front = index(1);
}
return old;
}
void enQueueRear(E e) {
ensureCapacity(m_size + 1);
m_elements[index(m_size)] = e;
m_size++;
}
E deQueueRear() {
if (m_size <= 0) {
return E();
}
E old = m_elements[index(m_size-1)];
m_elements[index(m_size-1)] = E();
m_size--;
if (m_size == 0) {
m_front = 0;
}
return old;
}
E front() {
return m_elements[index(0)];
}
E rear() {
return m_elements[index(m_size-1)];
}
private:
void ensureCapacity(int capacity) {
int oldCapacity = m_length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E* newElements = new E[newCapacity];
for (int i = 0; i < this->m_size; i++) {
newElements[i] = m_elements[index(i)];
}
delete[] m_elements;
m_elements = newElements;
m_length = newCapacity;
m_front = 0;
std::cout << std::to_string(oldCapacity) << "扩容为" << std::to_string(newCapacity) << std::endl;
}
};
网友评论