1.栈是操作限定在表的尾端进行的线性表，表尾要进行插入，删除等操作。我们把表尾称为栈顶，另一端叫做栈底。栈的操作是按照后进先出（LIFO：Last
In First Out）或是先进后出（FILO）的原则进行的，所以也叫做LIFO表或FILO表。
2.我们将栈的几个常用操作用接口表示如下：
public interface IStack<T>
{
int GetLength();
bool IsEmpty();
void Clear();
void Push(T item);//入栈
T Pop();//出栈
T GetTop()
}
3.使用连续空间来存储栈中的元素我们称为顺序栈，我们就实现一个简单的顺序栈，代码如下：
public class SeqStack<T>:IStack<T>
{
private int maxsize;
private T[] data;
private int top;
public T this[int index]
{
get { return data[index];}
set { data[index] = value; }
}
public int Maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
public int Top
{
get { return top; }
set { top = value; }
}
public SeqStack(int size)
{
data = new T[size];
maxsize = size;
top = -1;
}
public int GetLength()
{
return top + 1;
}
public void Clear()
{
top = -1;
}
public bool IsEmpty()
{
if (top == -1)
return true;
else
return false;
}
public bool IsFull()
{
if (top == maxsize - 1)
return true;
else
return false;
}
public void Push(T item)
{
if (IsFull())
{
Console.WriteLine("Stack is full");
return;
}
data[++top] = item;
}
public T Pop()
{
T tmp = default(T);
if (IsEmpty())
{
Console.WriteLine("Stack is empty");
return tmp;
}
tmp = data[top];
--top;
return tmp;
}
public T GetTop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty");
return default(T);
}
return data[top];
}
}
4.还有一种就是链式存储，实际上就是简化的单链表，节点和单链表的节点也是一样的如下：
public class Node<T>
{
private T data;
private Node<T> next;
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
public Node(Node<T> p)
{
next = p;
}
public Node()
{
data = default(T);
next = null;
}
public T Data
{
get { return data; }
set { data = value; }
}
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
链栈的实现如下：
public class LinkStack<T>:IStack<T>
{
public Node<T> top;
private int num;//栈中结点个数
public Node<T> Top
{
get { return top; }
set { top = value; }
}
public int Num
{
get { return num; }
set { num = value; }
}
public LinkStack()
{
top=null;
num=0;
}
public int GetLength()
{
return num;
}
public void Clear()
{
top = null;
num = 0;
}
public bool IsEmpty()
{
if ((top == null) && (num == 0))
return true;
else
return false;
}
public void Push(T item)
{
Node<T> q = new Node<T>(item);
if (top == null)
top = q;
else
{
q.Next = top;
top = q;
}
++num;
}
public T Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty");
return default(T);
}
Node<T> p = top;
top = top.Next;
--num;
return p.Data;
}
public T GetTop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty");
return default(T);
}
return top.Data;
}
}
5.上面是我们实现的简单的方式，我们下面来看下。Net Framework中的实现方式。C#类库中提供了泛型和非泛型版本的Stack类，主要继承
了IEnumerable和ICollection接口。
我们可以使用Reflector来查看下。Net Framework的实现方式，我们主要看泛型版本Stack<T>
public class Stack<T> : IEnumerable<T>, ICollection, IEnumerable
在。Net Framework中的Stack中的数据以数组形式存在,当数据空间不够时，扩大1倍空间,将数据从原有缓冲区复制到新的缓冲区中会带来O(n)的数据
复制开销，最坏可能带来sizeof(T)*(n-1)的空间浪费。数据Push，Pop的复杂度为O(1)。
我们来看下Push操作，当空间不够的时候会扩大一倍的空间。有数组复制的开销:
{
if (this._size == this._array.Length)
{
T[] destinationArray = new T[(this._array.Length == 0) ? 4 : (2 * this._array.Length)];
Array.Copy(this._array, 0, destinationArray, 0, this._size);
this._array = destinationArray;
}
this._array[this._size++] = item;
this._version++;
}
另外在Pop的时候，可能出现Stack中只有一个元素，有数组的数据都在，这时就浪费了空间，我们可以使用提供的下面函数来释放,如果元素数小于
当前容量的 90%，将容量设置为 Stack<(Of <(T>)>) 中的实际元素数。
public void TrimExcess()
{
int num = (int) (this._array.Length * 0.9);
if (this._size < num)
{
T[] destinationArray = new T[this._size];
Array.Copy(this._array, 0, destinationArray, 0, this._size);
this._array = destinationArray;
this._version++;
}
}
6.栈，堆区别
栈负责保存我们的代码执行（或调用）路径,而堆则负责保存对象或者说数据。
NET框架包含一个托管堆，所有的.NET语言在分配引用类型对象时都要使用它。像值类型这样的轻量级对象始终分配在栈中，但是所有的类实例和
数组都被生成在一个内存池中，这个内存池就是托管堆。
垃圾收集器的基本算法很简单：
● 将所有的托管内存标记为垃圾
● 寻找正被使用的内存块，并将他们标记为有效
● 释放所有没有被使用的内存块
● 整理堆以减少碎片
本文转自生鱼片博客园博客，原文链接：http://www.cnblogs.com/carysun/archive/2009/10/09/Stack.html，如需转载请自行联系原作者
