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