线性表是最基本、最简单、也是最常用的一种数据结构。之前我已经写了几次线性表了，分别是顺序表和链表，这两个以各种形式实现了多次，那么今天我么就再来看两种线性表，两种特殊的线性表——栈和队列
栈（stack）
首先说一下栈的概念：栈又叫后进先出的线性表（LIFO），不明白？那就再看一下它的结构吧，栈是只在一端进行插入和删除操作的，这也是它的特殊之处，这一段就是栈顶（top）。
既然栈是线性表，那么肯定有顺序栈和链式栈的区分。
顺序栈和顺序表差不多，不过，区别在于，顺序栈只在栈顶不进行插入和删除操作。如果说顺序表有头插、头删和尾插、尾删，那么顺序栈只有尾插、尾删。
链式栈也是这样，那么问题来了，我们是要将栈顶放在链式栈的头部，还是尾部，哪一个好呢？
首先来说一下，将栈顶放在头部，也就是，可以进行头插、头删，那么，也没什么；再看将栈顶放在尾部，我们要进行插入元素，那需要将尾部节点链接到新的节点，但是，尾节点在哪，还是得遍历找到尾结点，那么时间复杂度是不是就增加了。所以还是建议将栈顶放在头部，也就是说，链式栈可以进行的操作是：头插和头删
简单介绍一下栈，那么我们就来模拟实现stack吧：
#include<iostream>
using namespace std;
#include<assert.h>
template<class T>
class Stack
{
public:
Stack()
:_pdata(NULL)
, _size(0)
, _capacity(0)
{}
~Stack()
{
if (NULL != _pdata)
{
delete []_pdata;
_pdata = NULL;
}
_size = 0;
_capacity = 0;
}
bool Empty()
{
return 0 == _size;
}
size_t Size()
{
return _size;
}
T& Top()
{
assert(_size>0);
return _pdata[_size - 1];
}
void CapacityIsFull()
{
if (_size == _capacity)
{
size_t new_capacity = _capacity * 2 + 3;
//new一个空间一定要记准了，不要弄错。
T* temp = new T[new_capacity];
for (size_t i = 0; i < _size; ++i)
{
temp[i] = _pdata[i];
}
delete [] _pdata;
_pdata = temp;
_capacity = new_capacity;
}
}
void Push(const T& data)
{
CapacityIsFull();
_pdata[_size] = data;
++_size;
}
void Pop()
{
if (!Empty())
{
--_size;
}
else
{
cout << "栈已空" << endl;
return;
}
}
protected:
T * _pdata;
size_t _size;
size_t _capacity;
};
void FunTest()
{
Stack<int> s;
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);
s.Push(5);
s.Push(6);
cout << "stack size:" << s.Size() << endl;
cout << "stack top:" << s.Top() << endl;
s.Pop();
cout << "stack size:" << s.Size() << endl;
cout << "stack top:" << s.Top() << endl;
}
int main()
{
FunTest();
return 0;
}
队列（queue）
还是先说一下它的概念：队列又称先进先出的线性表（FIFO），想想你去吃饭排的队，是不是明白许多，那么我们再来声明一下，队列的特殊之处在于：它是在一端进行删除操作，这一端称为：对头（front）;在另一端进行插入操作，这一端称为：队尾（rear）。
同样，我们先来看一下顺序队列，也就是上图显示的那样，我们要进行插入元素的时候，会从尾部开始，现在，队列中有8个空间，如果插入三个元素，在删除三个元素，那么队列满了吗？
看样子是没满的，但是，你还可以在进行插入操作吗？显然是不可以的，这种现象就是“假溢出”，明明有空间，却不能进行插入元素，是不是很浪费，那么如何解决这个问题呢？
想想平时垃圾是怎么处理的，当然是回收了，我们将这个队列的头部和尾部相连，那么，在进行插入的时候，直接就会插入到原来a1的位置，然后，就可以继续进行操作了，直到队列满了。
队列满了，那么无非就是front和rear相遇了，但是如果队列中没有元素的时候，也是这个现象，这就要像个办法来区分一下了。
怎样区分队列满了，队列是空的
最简单也是最常用的方法就是定义一个计数器，这样我们就可以根据计数器显示的元素个数是不是0，来判断是不是空的，同样我们还可以根据这个来看有效元素的个数。
同样的，队列也有链式的，不过。队列的链式只能进行尾插，和头删操作。
#include<iostream>
using namespace std;
template<class T>
struct QueueNode
{
QueueNode(const T& data)
:_data(data)
, _next(NULL)
{}
T _data;
QueueNode<T> * _next;
};
template<class T>
class Queue
{
public:
typedef QueueNode<T> Node;
Queue()
:_front(NULL)
, _rear(NULL)
{}
~Queue()
{
if (_front)
{
Node* del = _front;
_front = _front->_next;
delete del;
del = NULL;
}
}
bool Empty()
{
return NULL == _front;
}
size_t Size()
{
return _size;
}
T& Front()
{
return _front->_data;
}
T& Rear()
{
return _rear->_data;
}
void Push(const T& data)//在队尾插入元素
{
if (Empty())//一定要分开讨论，不然会有访问冲突的问题
{
Node* node = new Node(data);
_front = _rear = node;
++_size;
}
else
{
Node* node = new Node(data);
_rear->_next = node;
_rear = _rear->_next;
++_size;
}
}
void Pop()//在对头删除元素
{
if (!Empty())
{
Node *del = _front;
_front = _front->_next;
delete del;
del = NULL;
}
else
{
cout << "队列已空" << endl;
}
}
private:
Node* _front;
Node* _rear;
size_t _size;
};
void FunTest()
{
Queue<int> q;
q.Push(1);
q.Push(2);
q.Push(3);
q.Push(4);
q.Push(5);
q.Push(6);
cout <<"the front is:"<< q.Front() << endl;
cout << "the rear is:" << q.Rear() << endl;
cout << "the size is:" << q.Size() << endl;
q.Pop();
cout << "the front is:" << q.Front() << endl;
cout << "the rear is:" << q.Rear() << endl;
cout << "the size is:" << q.Size() << endl;
}
int main()
{
FunTest();
return 0;
}