栈
栈的概念和结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）加粗样式的原则。
入栈：从栈顶放入数据的操作。
出栈：从栈顶取出元素的操作。
栈的实现
栈用链表和顺序表两种数据结构都可以实现，我们要确定选择哪一种更优，我们来分析一下。
链表栈：如果选择单链表的话，我们应该选择头当栈顶，尾当栈底，不然的话，每次存取数据都要遍历一遍链表。所以选双链表会比较好一点。
数组栈：访问栈顶的时间复杂度为O(1)，相比链表栈比较优。
所以下面我们用顺序表来实现栈的这种数据结构。
结构如下：初始化栈的大小为5
#define InitSize 5 template <class DateType> class Stack { public: private: DateType* data;//栈空间指针 int size;//栈容量 int top;//栈顶，栈中元素个数 }; 栈的接口
栈要实现的接口有以下几个：
Stack();//初始化栈，初始化的大小是5 Stack(const Stack& stack);//拷贝构造函数 Stack& operator=(const Stack& stack);//等号运算符的重载 ~Stack();//销毁栈 bool ifFull();//判断栈是否满了 bool isEmpty();//判断栈是否为空 void Push(const DateType& val);//入栈 bool Pop(DateType &item);//出栈，并获取出栈元素 void ExpandStack();//扩容 void PrintStack();//打印 栈的初始化
初始化栈就是把结构体中的成员都初始化一下，方便后续的扩容等操作。
具体实现如下：
//初始化栈，初始化的大小是5 Stack() { data = new DateType[InitSize]; if (data == NULL) { cout << "内存分配失败" << endl; exit(-1); } size = InitSize; top = 0; } 拷贝构造
//拷贝构造函数 Stack(const Stack& stack) { this->data = new DateType[stack.size]; if (data == NULL) { cout << "内存分配失败" << endl; exit(-1); } for (int i = 0; i < stack.size; i++) { this->data[i] = stack.data[i]; } this->size = stack.size; this->top = stack.top; } 判断栈满
//判断栈是否满了 bool ifFull() { if (top == size) { return true; } return false; } 扩容
//扩容 void ExpandStack() { this->size = this->size == 0 ? 4 : 2 * this->size; DateType* tmp = new DateType[this->size]; if (tmp == NULL) { cout << "内存分配失败" << endl; exit(-1); } for (int i = 0; i < top; i++) { tmp[i] = data[i]; } delete[] data; data = tmp; } 判断栈空
//判断栈是否为空 bool isEmpty() { if (top == 0) { return true; } return false; } 入栈
压栈就是在栈顶插入元素，其中是肯定要考虑到扩容的问题，当this->top == this->size时，就要考虑到扩容了，扩容也是像之前顺序表那样每次扩一倍，这样可以一定程度地减少扩容次数，但同时是会带来一定的空间消耗的。
//入栈 void Push(const DateType& val) { if (ifFull()) { ExpandStack(); } data[top++] = val; } 出栈
出栈就是在栈顶pop掉一个元素，也就是top-1指向的位置，只需要将top进行一个减1的操作即可。
与此同时，我们要确保此次栈不为空，所以要进行判断栈空的操作，防止程序崩溃。
//出栈，并获取出栈元素 bool Pop(DateType &item) { if (isEmpty()) { cout << "栈为空，无法出栈" << endl; return false; } item = data[--top]; return true; } 赋值运算符重载
运算符重载的注意事项在前面的博客我已经介绍过了，尤其是赋值运算符，感兴趣的小伙伴可以去看看，这里要注意几点
- 返回的是*this，对象本身
- 不要自己给自己赋值
- 要防止内存泄漏
- 防止浅拷贝的发生
//等号运算符的重载 Stack& operator=(const Stack& stack) { //防止自赋值 if (this == &stack) { return *this; } //防止内存泄漏 if (data != NULL) { delete[] data; } //防止浅拷贝 this->data = new DateType[stack.size]; if (data == NULL) { cout << "内存分配失败" << endl; exit(-1); } for (int i = 0; i < stack.top; i++) { this->data[i] = stack.data[i]; } this->size = stack.size; this->top = stack.top; return *this; } 打印
//打印 void PrintStack() { for (int i = 0; i < top; i++) { cout << data[i] << " "; } cout << endl; } 整体代码以及测试
#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 #define InitSize 5 /* 栈,利用顺序表实现 */ template <class DateType> class Stack { public: //初始化栈，初始化的大小是5 Stack() { data = new DateType[InitSize]; if (data == NULL) { cout << "内存分配失败" << endl; exit(-1); } size = InitSize; top = 0; } //拷贝构造函数 Stack(const Stack& stack) { this->data = new DateType[stack.size]; if (data == NULL) { cout << "内存分配失败" << endl; exit(-1); } for (int i = 0; i < stack.size; i++) { this->data[i] = stack.data[i]; } this->size = stack.size; this->top = stack.top; } //等号运算符的重载 Stack& operator=(const Stack& stack) { //防止自赋值 if (this == &stack) { return *this; } //防止内存泄漏 if (data != NULL) { delete[] data; } //防止浅拷贝 this->data = new DateType[stack.size]; if (data == NULL) { cout << "内存分配失败" << endl; exit(-1); } for (int i = 0; i < stack.top; i++) { this->data[i] = stack.data[i]; } this->size = stack.size; this->top = stack.top; return *this; } //销毁栈 ~Stack() { if (data != NULL) { delete[] data; data = NULL; } } //判断栈是否满了 bool ifFull() { if (top == size) { return true; } return false; } //判断栈是否为空 bool isEmpty() { if (top == 0) { return true; } return false; } //入栈 void Push(const DateType& val) { if (ifFull()) { ExpandStack(); } data[top++] = val; } //出栈，并获取出栈元素 bool Pop(DateType &item) { if (isEmpty()) { cout << "栈为空，无法出栈" << endl; return false; } item = data[--top]; return true; } //扩容 void ExpandStack() { this->size = this->size == 0 ? 4 : 2 * this->size; DateType* tmp = new DateType[this->size]; if (tmp == NULL) { cout << "内存分配失败" << endl; exit(-1); } for (int i = 0; i < top; i++) { tmp[i] = data[i]; } delete[] data; data = tmp; } //打印 void PrintStack() { for (int i = 0; i < top; i++) { cout << data[i] << " "; } cout << endl; } private: DateType* data;//栈空间指针 int size;//栈容量 int top;//栈顶，栈中元素个数 }; int main() { Stack<int> stack; stack.Push(1); stack.Push(2); stack.Push(3); stack.Push(4); stack.Push(5); stack.PrintStack(); cout << "-------------------------" << endl; int b = 0; stack.Pop(b); cout << b << endl; stack.Pop(b); cout << b << endl; stack.PrintStack(); cout << "-------------------------" << endl; Stack<int> stack2(stack); stack2.PrintStack(); cout << "-------------------------" << endl; Stack<int> stack3; stack3 = stack2; stack3.PrintStack(); cout << "-------------------------" << endl; system("pause"); return EXIT_SUCCESS; } 队列
队列的概念和结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
队列的结构，我们选取单链表来实现，秩序进行头删和为插的不足即可。如果选数组，那么每一次删头我们都要挪动一遍数据，这种方式不优，所以我们还是选取用单链表来实现。
定义的结构如下：
template<class DateType> //链队的结点类型 struct Node { DateType data; Node<DateType> *next; Node(Node<DateType>* p = NULL) { next = p; } //构造函数 Node(DateType val, Node<DateType>* p = NULL) { data = val; next = p; } }; template <class DateType> class Queue { public: private: //声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化 //队头指针 Node<DateType>* front; //队尾指针 Node<DateType>* rear; }; 队列的实现
队列的接口
Queue();//构造函数，初始化队列 ~Queue();//析构函数 bool QueuePush(const DateType& val);//队尾入队 bool QueuePop(DateType& val);//对头出队列 bool getFront(DateType& val) const;//获取对头元素的值 bool getRear(DateType& val);//获取队尾元素的值 void MakeEmpty();//将队列清空 bool isEmpty() const;//判断队列是否为NULL int getSize() const;//返回队列元素的个数 void PrintQueue();//输出队列元素 队列的初始化
初始化很简单，只要将头指针和尾指针都置空。
//构造函数 Queue() { front = NULL; rear = NULL; } 判断队列是否为空
//判断队列是否为NULL bool isEmpty() const { if (front == NULL) { return true; } else { return false; } } 入队
出队就是进行单链表尾删的操作，要考虑链表为空时不能进行删除，还要注意的是只有一个节点进行删除是要改变尾指针的指向。
//队尾入队列 bool QueuePush(const DateType& val) { if (front == NULL) { //如果队列为空，直接用指针开辟结点 front = rear = new Node<DateType>(val); if (front == NULL) { cout << "内存分配失败" << endl; return false; } } else { Node<DateType>* p = new Node<DateType>(val); rear->next = p; if (rear->next == NULL) { cout << "内存分配失败" << endl; return false; } //更新尾结点 rear = rear->next; } return true; } 出队
出队就是进行单链表尾删的操作，要考虑链表为空时不能进行删除，还要注意的是只有一个节点进行删除是要改变尾指针的指向。
bool QueuePop(DateType& val) { //如果队列为空，不允许出列 if (isEmpty()) { return false; } else { Node<DateType>* p = front; val = front->data; front = front->next; delete p; return true; } } 获取队头元素和队尾元素
首先要确保链表不为空，对头就是返回头节点的大小，队尾就是返回尾节点的大小。
具体实现如下：
//获取对头元素的值 bool getFront(DateType& val) const { if (isEmpty()) { return false; } val = front->data; return true; } //获取队尾元素的值 bool getRear(DateType& val) { if (isEmpty()) { return false; } val = rear->data; return true; } 获取队列元素个数
遍历一遍链表，同时进行计数操作，最后返回计数结果即可。
//返回队列元素的个数 int getSize() const { //函数返回队列元素的个数 Node<DateType>* p = front; int count = 0; while (p != NULL) { ++count; p = p->next; } return count; } 队列的销毁
为了防止内存泄漏，动态内存申请的空间一定要我们自己手动释放，养成一个良好的习惯。所以要将链表的空间逐个释放。
//将队列清空 void MakeEmpty() { //置空队列，释放链表中所有的结点 Node<DateType>* current; if (front != NULL) { current = front; front = front->next; delete current; } } 打印队列
//输出队列元素 void PrintQueue() { Node<DateType>* p = front; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << endl; } 整体代码以及测试
#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 /* 队列，单链表实现 */ template<class DateType> //链队的结点类型 struct Node { DateType data; Node<DateType> *next; Node(Node<DateType>* p = NULL) { next = p; } //构造函数 Node(DateType val, Node<DateType>* p = NULL) { data = val; next = p; } }; template <class DateType> class Queue { public: //构造函数 Queue() { front = NULL; rear = NULL; } //析构函数 ~Queue() { MakeEmpty(); } //队尾入队列 bool QueuePush(const DateType& val) { if (front == NULL) { //如果队列为空，直接用指针开辟结点 front = rear = new Node<DateType>(val); if (front == NULL) { cout << "内存分配失败" << endl; return false; } } else { Node<DateType>* p = new Node<DateType>(val); rear->next = p; if (rear->next == NULL) { cout << "内存分配失败" << endl; return false; } //更新尾结点 rear = rear->next; } return true; } //对头出队列 bool QueuePop(DateType& val) { //如果队列为空，不允许出列 if (isEmpty()) { return false; } else { Node<DateType>* p = front; val = front->data; front = front->next; delete p; return true; } } //获取对头元素的值 bool getFront(DateType& val) const { if (isEmpty()) { return false; } val = front->data; return true; } //获取队尾元素的值 bool getRear(DateType& val) { if (isEmpty()) { return false; } val = rear->data; return true; } //将队列清空 void MakeEmpty() { //置空队列，释放链表中所有的结点 Node<DateType>* current; if (front != NULL) { current = front; front = front->next; delete current; } } //判断队列是否为NULL bool isEmpty() const { if (front == NULL) { return true; } else { return false; } } //返回队列元素的个数 int getSize() const { //函数返回队列元素的个数 Node<DateType>* p = front; int count = 0; while (p != NULL) { ++count; p = p->next; } return count; } //输出队列元素 void PrintQueue() { Node<DateType>* p = front; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << endl; } private: //声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化 //队头指针 Node<DateType>* front; //队尾指针 Node<DateType>* rear; }; int main() { Queue<int> que; que.QueuePush(1); que.QueuePush(2); que.QueuePush(3); que.QueuePush(4); que.PrintQueue(); cout << "----------------------" << endl; int b = 0; que.QueuePop(b); cout << b << endl; que.QueuePop(b); cout << b << endl; que.PrintQueue(); cout << "----------------------" << endl; int c = 0; que.getFront(c); cout << c << endl; que.PrintQueue(); cout << que.getSize() << endl; cout << "----------------------" << endl; system("pause"); return EXIT_SUCCESS; } 
