前言
栈是以先进后出,后进先出,队列是先进先出的原则,一端队尾插入另一端队头取出,双向队列相当两头都可以插入数据,两头都可以取出数据。前文了解了ArrayList与LinkedList的实现后,栈与堆的实现就比较简单了
一：栈的实现
栈
1：Stack基类
template <class E>
class Stack {
protected:
int len = 0;
public:
virtual ~Stack();
virtual int size();
virtual bool isEmpty();
//弹出
virtual E pop() = 0;
//获取栈顶不弹出
virtual E peek() = 0;
//栈中添加元素
virtual bool push(const E &e) = 0;
};
template <class E>
Stack<E>::~Stack() {
}
template <class E>
int Stack<E>::size() {
return len;
}
template <class E>
bool Stack<E>::isEmpty() {
return len <= 0;
}
2： ArrayStack类
template <class E>
class ArrayStack : public Stack<E> {
private:
int capacity = 10;
E *datas = NULL;
public:
ArrayStack();
~ArrayStack();
E pop();
E peek();
bool push(const E &e);
};
template <class E>
ArrayStack<E>::ArrayStack() {
this->datas = (E*) malloc(sizeof(E) * capacity);
}
template <class E>
ArrayStack<E>::~ArrayStack() {
if (this->datas) {
free(this->datas);
this->datas = NULL;
}
}
template <class E>
E ArrayStack<E>::pop() {
assert(Stack<E>::len > 0);
int index = Stack<E>::len - 1;
E data = datas[index];
Stack<E>::len--;
return data;
}
template <class E>
E ArrayStack<E>::peek() {
assert(Stack<E>::len > 0);
return datas[Stack<E>::len - 1];
}
/**
* 这里忽略扩充数组后大小超过int最大值
* @tparam E
* @param e
* @return
*/
template <class E>
bool ArrayStack<E>::push(const E &e) {
if (Stack<E>::len == capacity) //需要扩充
{
capacity += capacity >> 1;//扩充成原先的1.5倍
this->datas = (E*) realloc(this->datas, sizeof(E) * capacity);
}
datas[Stack<E>::len] = e;
Stack<E>::len++;
return true;
}
3：LinkedStack类
template <class E>
class LinkedStack : public Stack<E> {
private:
struct Node {
E data;
Node *next = NULL;
Node(const E &data, Node *next) : data(data) {
this->next = next;
}
};
Node *popNode = NULL;
public:
~LinkedStack();
E pop();
E peek();
bool push(const E& e);
};
template <class E>
LinkedStack<E>::~LinkedStack() {
if (this->popNode) {
Node *curr = this->popNode;
while (curr)
{
Node *next = curr->next;
delete curr;
curr = next;
}
this->popNode = NULL;
}
}
template <class E>
E LinkedStack<E>::pop() {
assert(Stack<E>::len > 0 && this->popNode);
Node *next = this->popNode->next;
E data = this->popNode->data;
delete this->popNode;
this->popNode = next;
Stack<E>::len--;
return data;
}
template <class E>
E LinkedStack<E>::peek() {
assert(Stack<E>::len > 0 && this->popNode);
return this->popNode->data;
}
template <class E>
bool LinkedStack<E>::push(const E &e) {
Node *newNode = new Node(e, this->popNode);
this->popNode = newNode;
Stack<E>::len++;
return true;
}
二：这里介绍双向队列ArrayDeuqe的实现
前文中LinkedList已经实现了链表式的Deque
1：单向数组队列原理
队列不会像ArrayList那样会有操作中间某个index的数据,如果按照ArrayList那种原理的话,每次弹出第一个元素的时候,数组都要整体移动,这样大大降低了效率,所以要用到循环双向的数组原理
循环数组
单向队列的添加与删除
在队列中数组的大小必须为2的冥次, 在扩充的时候数组大小 <<1 原因可以参考前文位运算技巧
单向的添加与删除
单向队列扩充
单向队列扩充
双向队列的添加与删除
双向队列
2：ArrayDeque代码实现
template <class E>
class ArrayDeque {
private:
static const int DEF_CAPACITY = 16;
/**
* 阀值
*/
int initialCapacity;
int len = 0;
/**
* 队列头位置与尾位置
*/
int headIndex = 0;
int backIndex = 0;
E *datas;
/**
* 扩充数组
*/
void grow();
public:
ArrayDeque();
ArrayDeque(int numElements);
~ArrayDeque();
bool isEmpty();
int size();
/**
* 从队列尾部添加
*/
bool push(const E &e);
/**
* 弹出队首
*/
E pop();
/**
* 取队首不弹出
*/
E peek();
/**
* 从队列首部添加
*/
bool pushFront(const E &e);
/**
* 弹出队尾数据
*/
E popBack();
E peekBack();
};
/**
* 这里忽略扩充数组后大小超过int最大值
* @tparam E
*/
template <class E>
void ArrayDeque<E>::grow() {
int new_size = initialCapacity << 1;
E *newDatas = (E*) malloc(sizeof(E) * new_size);
int copyIndex = initialCapacity - backIndex;
for (int i = 0; i < backIndex; i++) {
newDatas[copyIndex + i] = datas[i];
}
for (int i = 0; i < copyIndex; i++) {
newDatas[i] = datas[i + backIndex];
}
headIndex = 0;
backIndex = initialCapacity;
initialCapacity = new_size;
free(this->datas);
datas = newDatas;
}
template <class E>
ArrayDeque<E>::ArrayDeque() {
initialCapacity = DEF_CAPACITY;
this->datas = (E*) malloc(sizeof(E) * initialCapacity);
}
template <class E>
ArrayDeque<E>::ArrayDeque(int numElements) {
if (numElements > DEF_CAPACITY) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >> 1);
initialCapacity |= (initialCapacity >> 2);
initialCapacity |= (initialCapacity >> 4);
initialCapacity |= (initialCapacity >> 8);
initialCapacity |= (initialCapacity >> 16);
initialCapacity++;
}
this->datas = (E*) malloc(sizeof(E) * initialCapacity);
}
template <class E>
ArrayDeque<E>::~ArrayDeque() {
if (this->datas) {
free(this->datas);
this->datas = NULL;
}
}
template <class E>
bool ArrayDeque<E>::isEmpty() {
return headIndex == backIndex;
}
template <class E>
int ArrayDeque<E>::size() {
return this->len;
}
template <class E>
bool ArrayDeque<E>::push(const E &e) {
headIndex = (headIndex - 1) & (initialCapacity - 1);
datas[headIndex] = e;
if (headIndex == backIndex) {//需要扩充
grow();
}
this->len++;
return true;
}
template <class E>
E ArrayDeque<E>::pop() {
assert(this->len > 0);
backIndex = (backIndex - 1) & (initialCapacity - 1);
E data = datas[backIndex];
this->len--;
return data;
}
template <class E>
E ArrayDeque<E>::peek() {
assert(this->len > 0);
int popIndex = (backIndex - 1) & (initialCapacity - 1);
return datas[popIndex];
}
template <class E>
bool ArrayDeque<E>::pushFront(const E &e) {
datas[backIndex] = e;
backIndex = (backIndex + 1) & (initialCapacity - 1);
if (headIndex == backIndex) {//需要扩充
grow();
}
this->len++;
return true;
}
template <class E>
E ArrayDeque<E>::popBack() {
assert(this->len > 0);
E data = datas[headIndex];
headIndex = (headIndex + 1) & (initialCapacity - 1);
this->len--;
return data;
}
template <class E>
E ArrayDeque<E>::peekBack() {
assert(this->len > 0);
return datas[headIndex];
}
