浅析并实现栈(stack)和对列(queue)

栈和队列都是我们在数据结构阶段学习的典型数据结构。栈的处理数据时的特点：后进先出，对列的特点：先进先出。
栈除了处理数据，还有函数栈帧以及用来分析递归问题，关于这点，我将在后面的文章中给出自己的总结。
栈和队列的实现函数是参考源代码的实现代码，有些库中未实现的，我在这里面也忽略了。
因为栈是顺序存储的，所以栈的实现采用数组的结构，这样可以更好的体会到栈在操作时的特点，实现过程也比较明了。
栈的结构

数据入栈和出栈时的操作示意图

参考示意图可发现，栈在处理数据时必须（插入和删除数据都在栈顶）

stack源代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

template<class T>
class Stack
{
public:
Stack()
 :_array(NULL)
 , _size(0)
 , _capacity(0)
 {}

 void Push(const T& x)
 {
CheckCapacity();
 _array[_size] = x;
 _size++;
 }

 void Pop()
 {
 assert(_size > 0);
--_size;
 }

 void CheckCapacity()
 {
 if (_size == _capacity)
 {
 size_t newcapacity = _capacity * 2 + 3;
T* tmp = new T[newcapacity];
 for (size_t i = 0; i < _size; i++)
 {
 tmp[i] = _array[i];
 }
 delete[] _array;
 _array = tmp;
 _capacity = newcapacity;
 }
 }

 size_t Size()
 {
 return _size;
 }

 bool Empty()
 {
 return _size == 0;
 }

T& Top()
 {
 return _array[_size-1];
 }

 void Print()
 {
 for (size_t i = 0; i < _size; i++)
 {
 cout << _array[i] << " ";
 }
 cout << endl;
 }
protected:
T* _array;
 size_t _size;
 size_t _capacity;

};

void TestStack()
{
Stack<int> s;
 s.Push(1);
 s.Push(2);
 s.Push(3);
 s.Push(4);
 s.Push(5);
 s.Print();

 s.Pop();
 s.Pop();
 s.Pop();
 s.Print();

 cout << s.Size() << endl;;
 cout << s.Top() << endl;
}

对列的实现采用链表实现，函数实现参考库中实现。
对列处理数据时的操作示意图

依据对列先进先出的特点，所以对列处理数据时必须（在对头删除数据，在对尾插入数据）。
queue源代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

template<class T>
struct QueueNode 
{
public:
    QueueNode()
       :_data(0)
       ,_next(NULL)
    {}

    T _data;
    QueueNode<T>* _next;
};

template<class T>

class Queue
{
    typedef QueueNode<T> Node;
public:
Queue()
        :_head(NULL)
        ,_tail(NULL)
    {}

    ~Queue()
    {
        Node* cur = _head;
while (cur)
        {
            Node* del = cur;
            cur = cur->_next;
            delete del;
            del = NULL;
        }
    }

void Push(const T& x)
    {
if (_head == NULL)
        {
            _head = new Node;
            _head->_data = x;
            _tail = _head;

        }
else
        {
            Node* tmp = new Node;
            tmp->_data = x;
            tmp->_next = NULL;
            _tail->_next = tmp;
            _tail = _tail->_next;
        }

    }

void Pop()
        {
            assert(_head && _tail);
if (_head == _tail) //为空
            {
                delete _head;
                _head = _tail = NULL;
            }
else
            {
                Node* tmp = _head->_next;
                delete _head;
                _head = tmp;
            }
        }

        size_t Size()
        {
            Node* cur = _head;
            size_t count = 0;
while (cur)
            {
                count++;
                cur = cur->_next;
            }
return count;
        }

        bool Empty()
        {
return _head == NULL;
        }

        T& Front()
        {
            assert(_head);
return _head->_data;
        }

        T& Back()
        {
            assert(_tail);
return _tail->_data;
        }

void Print()
        {
            Node*  _cur = _head;
while (_cur)
            {
                cout << _cur->_data << " ";
                _cur = _cur->_next;
            }
            cout << endl;
        }
protected:
    Node* _head;
    Node* _tail;
};

void TestQueue()
{
Queue<int> q;
    q.Push(1);
    q.Push(2);
    q.Push(3);
    q.Push(4);
    q.Push(5);
    q.Print();

    q.Pop();
    q.Pop();
    q.Pop();
    q.Print();
//cout << q.Size() << endl;
//cout << q.Empty() << endl; 
//cout << q.Front() << endl;
//cout << q.Back() << endl;


}