最近晚上在家里看Algorithems，4th Edition，我买的英文版，觉得这本书写的比较浅显易懂，而且“图码并茂”，趁着这次机会打算好好学习做做笔记，这样也会印象深刻，这也是写这一系列文章的原因。另外普林斯顿大学在Coursera 上也有这本书同步的公开课，还有另外一门算法分析课，这门课程的作者也是这本书的作者，两门课都挺不错的。
计算机程序离不开算法和数据结构，本文简单介绍栈(Stack)和队列(Queue)的实现，.NET中与之相关的数据结构，典型应用等，希望能加深自己对这两个简单数据结构的理解。
1. 基本概念
概念很简单，栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构，而队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构，如下图：
2. 实现
现在来看如何实现以上的两个数据结构。在动手之前，Framework Design Guidelines这本书告诉我们，在设计API或者实体类的时候，应当围绕场景编写API规格说明书。
1.1 Stack的实现
栈是一种后进先出的数据结构，对于Stack 我们希望至少要对外提供以下几个方法：
| Stack<T>() | 创建一个空的栈 |
| void Push(T s) | 往栈中添加一个新的元素 |
| T Pop() | 移除并返回最近添加的元素 |
| boolean IsEmpty() | 栈是否为空 |
| int Size() | 栈中元素的个数 |
要实现这些功能，我们有两中方法，数组和链表，先看链表实现：
栈的链表实现：
我们首先定义一个内部类来保存每个链表的节点，该节点包括当前的值以及指向下一个的值，然后建立一个节点保存位于栈顶的值以及记录栈的元素个数;
|
1 2 3 4 5 |
class Node { public T Item{get;set;} public Node Next { get; set; } } |
|
1 2 |
private Node first = null; private int number = 0; |
现在来实现Push方法，即向栈顶压入一个元素，首先保存原先的位于栈顶的元素，然后新建一个新的栈顶元素，然后将该元素的下一个指向原先的栈顶元素。整个Pop过程如下:
实现代码如下：
|
1 2 3 4 5 6 7 8 |
void Push(T node) { Node oldFirst = first; first = new Node(); first.Item= node; first.Next = oldFirst; number++; } |
Pop方法也很简单，首先保存栈顶元素的值，然后将栈顶元素设置为下一个元素：
|
1 2 3 4 5 6 7 |
T Pop() { T item = first.Item; first = first.Next; number--; return item; } |
基于链表的Stack实现，在最坏的情况下只需要常量的时间来进行Push和Pop操作。
栈的数组实现：
我们可以使用数组来存储栈中的元素Push的时候，直接添加一个元素S[N]到数组中，Pop的时候直接返回S[N-1].
首先，我们定义一个数组，然后在构造函数中给定初始化大小，Push方法实现如下，就是集合里添加一个元素：
|
1 2 3 4 5 6 7 |
T[] item; int number = 0; public StackImplementByArray(int capacity) { item = new T[capacity]; } |
|
1 2 3 4 5 |
public void Push(T _item) { if (number == item.Length) Resize(2 * item.Length); item[number++] = _item; } |
Pop方法：
|
1 2 3 4 5 6 7 |
public T Pop() { Edition，我买的英文版，觉得这本书写的比较浅显易懂，而且“图码并茂”，趁着这次机会打算好好学习做做笔记，这样也会印象深刻，这也是写这一系列文章的原因。另外普林斯顿大学在Coursera 上也有这本书同步的公开课，还有另外一门算法分析课，这门课程的作者也是这本书的作者，两门课都挺不错的。
计算机程序离不开算法和数据结构，本文简单介绍栈(Stack)和队列(Queue)的实现，.NET中与之相关的数据结构，典型应用等，希望能加深自己对这两个简单数据结构的理解。 1. 基本概念概念很简单，栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构，而队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构，如下图：
2. 实现现在来看如何实现以上的两个数据结构。在动手之前，Framework Design Guidelines这本书告诉我们，在设计API或者实体类的时候，应当围绕场景编写API规格说明书。 1.1 Stack的实现 栈是一种后进先出的数据结构，对于Stack 我们希望至少要对外提供以下几个方法：
要实现这些功能，我们有两中方法，数组和链表，先看链表实现： 栈的链表实现： 我们首先定义一个内部类来保存每个链表的节点，该节点包括当前的值以及指向下一个的值，然后建立一个节点保存位于栈顶的值以及记录栈的元素个数;
现在来实现Push方法，即向栈顶压入一个元素，首先保存原先的位于栈顶的元素，然后新建一个新的栈顶元素，然后将该元素的下一个指向原先的栈顶元素。整个Pop过程如下:
实现代码如下：
Pop方法也很简单，首先保存栈顶元素的值，然后将栈顶元素设置为下一个元素：
基于链表的Stack实现，在最坏的情况下只需要常量的时间来进行Push和Pop操作。 栈的数组实现： 我们可以使用数组来存储栈中的元素Push的时候，直接添加一个元素S[N]到数组中，Pop的时候直接返回S[N-1].
首先，我们定义一个数组，然后在构造函数中给定初始化大小，Push方法实现如下，就是集合里添加一个元素：
Pop方法：
|
