1.栈
1.1栈的抽象父类
#pragma once templateclass T> class Stack { public: // 析构函数 virtual ~Stack() {} // 栈是否为空 virtual bool empty() const = 0; // 栈的大小 virtual int size() const = 0; // 栈顶元素 virtual T& top() = 0; // 出栈 virtual void pop() = 0; // 入栈 virtual void push(const T& theElement) = 0; };
1.2栈的数组实现
【数据结构】1.线性表的数组描述和链式描述 – imXuan – 博客园 (cnblogs.com)
#pragma once #include"stack.h" #include"arrayList.hpp" #include using namespace std; templateclass T> class DerivedArrayStack :private ArrayList, public Stack { public: DerivedArrayStack(int initialCapacity = 10) :ArrayList(initialCapacity) {} // 栈是否为空 bool empty() const { return ArrayList::empty(); } // 栈的大小 int size() const { return ArrayList::size(); } // 栈顶元素 T& top() { if (ArrayList::empty()) cout "栈为空" endl; else return ArrayList::get(ArrayList::size() - 1); } // 出栈 void pop() { if (ArrayList::empty()) cout "栈为空" endl; else { cout "出栈元素为:" ::get(ArrayList::size() - 1) endl; ArrayList::erase(ArrayList::size() - 1); } } // 入栈 void push(const T& theElement) { ArrayList::insert(ArrayList::size(), theElement); } };
1.3栈的链式实现
【数据结构】1.线性表的数组描述和链式描述 – imXuan – 博客园 (cnblogs.com)
#pragma once #include"chain.hpp" #include"stack.h" #include using namespace std; templateclass T> class DerivedLinkedStack :private Chain, public Stack { public: DerivedLinkedStack(int initialCapacity = 10) :Chain(initialCapacity) {} // 栈是否为空 bool empty() const { return Chain::empty(); } // 栈的大小 int size() const { return Chain::size(); } // 栈顶元素 T& top() { if (Chain::empty()) cout "栈为空" endl; else return Chain::get(Chain::listSize - 1); } // 出栈 void pop() { if (Chain::empty()) cout "栈为空" endl; else { cout "出栈元素为:" ::get(Chain::listSize - 1) endl; Chain::erase(Chain::listSize - 1); } } // 入栈 void push(const T& theElement) { Chain::insert(Chain::size(), theElement); } };
2.队列
2.1队列的抽象父类
#pragma once templateclass T> class queue { public: virtual ~queue() {} virtual bool empty() const = 0; virtual int size() const = 0; virtual T& front() = 0; virtual T& back() = 0; virtual void pop() = 0; virtual void push(const T& theElement) = 0; };
2.2队列的数组实现
队列由一个数组来描述,队首指针是队首的前一个元素,队尾指针是队尾所在元素,当队首和队尾指针重叠时表示队列为空;当 (队尾指针+1)%数组长度 等于队首指针时队列为满
假设push数据时队列已满,需要为存储队列的数组进行扩充,我们将AB首先移动到起始位置,然后将C~G移动到AB之后,具体代码参见 push()
#pragma once #include"queue.h" #include"arrayList.hpp" #include using namespace std; templateclass T> class arrayQueue :public queue { private: int theFront; // 第一个元素的前一个 int theBack; // 最后一个元素 int arrayLength; // 队列长度 T* queue; // 队列本体 public: arrayQueue(int initialCapacity = 10); ~arrayQueue() { delete[] queue; } bool empty() const { return theFront == theBack; } int size() const { return (theBack - theFront + arrayLength) % arrayLength; } T& front() { if (theFront == theBack) { cout "队列为空" endl; } return queue[(theFront + 1) % arrayLength]; } T& back() { if (theFront == theBack) { cout "队列为空" endl; } return queue[theBack]; } void pop() { if (theFront == theBack) { cout "队列为空" endl; return; } cout 1) % arrayLength]; theFront = (theFront + 1) % arrayLength; queue[theFront].~T(); } void push(const T& theElement); }; templateclass T> arrayQueue::arrayQueue(int initialCapacity) { if (initialCapacity 1) { cout "initialCapacity 必须为正整数" endl; return; } arrayLength = initialCapacity; queue = new T[arrayLength]; theFront = 0; theBack = 0; } templateclass T> void arrayQueue::push(const T& theElement) { if ((theBack + 1) % arrayLength == theFront) { T* newQueue = new T[2 * arrayLength]; int start = (theFront + 1) % arrayLength; if (start 2) copy(queue + start, queue + start + arrayLength - 1, newQueue); else { copy(queue + start, queue + arrayLength, newQueue); copy(queue, queue + theBack + 1, newQueue + arrayLength - start); } theFront = 2 * arrayLength - 1; theBack = arrayLength - 2; arrayLength *= 2; queue = newQueue; } theBack = (theBack + 1) % arrayLength; queue[theBack] = theElement; }
2.3队列的链式实现
【数据结构】1.线性表的数组描述和链式描述 – imXuan – 博客园 (cnblogs.com)
#pragma once #include "queue.h" #include "chainNode.hpp" #include using namespace std; templateclass T> class linkedQueue : public queue { private: chainNode* queueFront; // 头指针 chainNode* queueBack; // 尾指针 int queueSize; // 队列大小 public: linkedQueue(int initialCapacity = 10) { queueFront = NULL; queueSize = 0; } ~linkedQueue(); bool empty() const {return queueSize == 0;} int size() const { return queueSize;} T& front() { if (queueSize == 0) cout "队列为空" endl; return queueFront->element; } T& back() { if (queueSize == 0) cout "队列为空" endl; return queueBack->element; } void pop(); void push(const T&); }; templateclass T> linkedQueue::~linkedQueue() { while (queueFront != NULL) { chainNode* nextNode = queueFront->next; delete queueFront; queueFront = nextNode; } } templateclass T> void linkedQueue::pop() { if (queueFront == NULL) { cout "队列为空" endl; return; } chainNode* nextNode = queueFront->next; delete queueFront; queueFront = nextNode; queueSize--; } templateclass T> void linkedQueue::push(const T& theElement) { chainNode* newNode = new chainNode(theElement, NULL); if (queueSize == 0) queueFront = newNode; else queueBack->next = newNode; queueBack = newNode; queueSize++; }
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net