前言
棧是以先進后出,后進先出,隊列是先進先出的原則,一端隊尾插入另一端隊頭取出,雙向隊列相當兩頭都可以插入數(shù)據(jù),兩頭都可以取出數(shù)據(jù)蛙讥。前文了解了ArrayList與LinkedList的實現(xiàn)后,棧與堆的實現(xiàn)就比較簡單了
一：棧的實現(xiàn)
棧
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];
}
/**
* 這里忽略擴充數(shù)組后大小超過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的實現(xiàn)
前文中LinkedList已經(jīng)實現(xiàn)了鏈表式的Deque
1：單向數(shù)組隊列原理
隊列不會像ArrayList那樣會有操作中間某個index的數(shù)據(jù),如果按照ArrayList那種原理的話,每次彈出第一個元素的時候,數(shù)組都要整體移動,這樣大大降低了效率,所以要用到循環(huán)雙向的數(shù)組原理
循環(huán)數(shù)組
單向隊列的添加與刪除
在隊列中數(shù)組的大小必須為2的冥次, 在擴充的時候數(shù)組大小 <<1 原因可以參考前文位運算技巧
單向的添加與刪除
單向隊列擴充
單向隊列擴充
雙向隊列的添加與刪除
雙向隊列
2：ArrayDeque代碼實現(xiàn)
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;
/**
* 擴充數(shù)組
*/
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);
/**
* 彈出隊尾數(shù)據(jù)
*/
E popBack();
E peekBack();
};
/**
* 這里忽略擴充數(shù)組后大小超過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];
}
