栈和队列都可以看做插入和删除受限制的线性表,通过继承线性表可以实现栈和队列。
Github: https://github.com/yalewoo/cpp-data-structure
栈(Stack)
从Vector派生而来,新增的接口有入栈、出栈和返回栈顶元素。直接通过线性表的接口来实现。
C++实现
stack.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#ifndef MY_STACK_H #define MY_STACK_H #include "Vector.h" template <typename T> class Stack : public Vector<T> { public: using Vector<T>::size; void push(T const & e) { this->insert(size(), e); } T pop() { return this->remove(size()-1); } T top() {return this->get(size()-1); } }; #endif |
stack.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include "Stack.h" using namespace std; template <typename T> class MyPrint { public: void operator()(T e) { cout << e << " "; } }; int main() { Stack<int> s; s.push(4); s.push(5); s.push(7); s.push(8); s.push(9); s.push(11); MyPrint<int> visit; s.travser(visit); s.empty(); return 0; } |
队列(Queue)
从List派生而来,目前没有检查有效性,因此队列为空时队首和队尾元素未知,队列为空时出队操作会带来错误。
新增接口有入队、出队和返回队首或队尾元素。
C++实现
queue.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#ifndef MY_QUEUE_H #define MY_QUEUE_H #include "List.h" template <typename T> class Queue : public List<T> { public: void enqueue(T const & e) { this->insertAsLast(e); } T rear() { return this->last()->data; } T dequeue() { return this->remove(this->first()); } T front() { return this->first->data; } }; #endif |
queue.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include "Queue.h" #include <iostream> using namespace std; template <typename T> class MyPrint { public: void operator()(T e) { cout << e << " "; } }; int main() { Queue<int> q; q.enqueue(4); q.enqueue(5); q.enqueue(6); q.enqueue(7); q.enqueue(8); q.enqueue(9); MyPrint<int> visit; q.travser(visit); cout << endl << q.dequeue() << endl; q.travser(visit); return 0; } |