栈的概念和结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）加粗样式的原则。
入栈：从栈顶放入数据的操作。
出栈：从栈顶取出元素的操作。

栈的实现

栈用链表和顺序表两种数据结构都可以实现，我们要确定选择哪一种更优，我们来分析一下。
链表栈：如果选择单链表的话，我们应该选择头当栈顶，尾当栈底，不然的话，每次存取数据都要遍历一遍链表。所以选双链表会比较好一点。
数组栈：访问栈顶的时间复杂度为O(1)，相比链表栈比较优。
所以下面我们用顺序表来实现栈的这种数据结构。
结构如下：初始化栈的大小为5

#define InitSize  5
template 
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 //引入头文件
#include//C++中的字符串
using namespace std; //标准命名空间
#define InitSize  5
/*
栈,利用顺序表实现
*/
template 
class Stack
{
public://初始化栈，初始化的大小是5Stack(){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 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 stack2(stack);stack2.PrintStack();cout << "-------------------------" << endl;Stack stack3;stack3 = stack2;stack3.PrintStack();cout << "-------------------------" << endl;system("pause");return EXIT_SUCCESS;
}

队列

队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。

队列的结构，我们选取单链表来实现，秩序进行头删和为插的不足即可。如果选数组，那么每一次删头我们都要挪动一遍数据，这种方式不优，所以我们还是选取用单链表来实现。
定义的结构如下：

template
//链队的结点类型
struct Node
{DateType data;Node *next;Node(Node* p = NULL){next = p;}//构造函数Node(DateType val, Node* p = NULL){data = val;next = p;}
};

template 
class Queue
{
public:
private://声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化//队头指针Node* front;//队尾指针Node* 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(val);if (front == NULL){cout << "内存分配失败" << endl;return false;}}else{Node* p = new Node(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* 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* p = front;int count = 0;while (p != NULL){++count;p = p->next;}return count;
}

队列的销毁

为了防止内存泄漏，动态内存申请的空间一定要我们自己手动释放，养成一个良好的习惯。所以要将链表的空间逐个释放。

//将队列清空
void MakeEmpty()
{//置空队列，释放链表中所有的结点Node* current;if (front != NULL){current = front;front = front->next;delete current;}
}

打印队列

//输出队列元素
void PrintQueue()
{Node* p = front;while (p != NULL){cout << p->data << "  ";p = p->next;}cout << endl;
}

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include //引入头文件
#include//C++中的字符串
using namespace std; //标准命名空间
/*
队列，单链表实现
*/
template
//链队的结点类型
struct Node
{DateType data;Node *next;Node(Node* p = NULL){next = p;}//构造函数Node(DateType val, Node* p = NULL){data = val;next = p;}
};
template 
class Queue
{
public://构造函数Queue(){front = NULL;rear = NULL;}//析构函数~Queue(){MakeEmpty();}//队尾入队列bool QueuePush(const DateType& val){if (front == NULL){//如果队列为空，直接用指针开辟结点front = rear = new Node(val);if (front == NULL){cout << "内存分配失败" << endl;return false;}}else{Node* p = new Node(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* 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* current;if (front != NULL){current = front;front = front->next;delete current;}}//判断队列是否为NULLbool isEmpty() const{if (front == NULL){return true;}else{return false;}}//返回队列元素的个数int getSize() const{//函数返回队列元素的个数Node* p = front;int count = 0;while (p != NULL){++count;p = p->next;}return count;}//输出队列元素void PrintQueue(){Node* p = front;while (p != NULL){cout << p->data << "  ";p = p->next;}cout << endl;}
private://声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化//队头指针Node* front;//队尾指针Node* rear;
};
int main()
{Queue 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;
}