并发数据结构:Stack

并发数据结构:Stack2011-08-07 博客园 Angel Lucifer在叙述并发Stack前，我们先来了解下非线程安全的Stack。

Stack是一种线性数据结构，只能访问它的一端来存储或读取数据。Stack很像餐厅中的一叠盘子：将新盘子堆在最上面，并从最上面取走盘子。最后一个堆在上面的盘子第一个被取走。因此Stack也被称为后进先出结构（LIFO）。

Stack有两种实现方式：数组和列表。下面我们分别用这两种方式来实现一个简单的Stack。采用数组实现代码如下：

using System;
using System.Collections.Generic;

namespace Lucifer.DataStructure
{
   public class ArrayStack<T>
   {
     private T[] array;
     private int topOfStack;
     private const int defaultCapacity = 16;

     public ArrayStack（） : this（defaultCapacity）
     {
     }

     public ArrayStack（int initialCapacity）
     {

   if （initialCapacity < 0）
         throw new ArgumentOutOfRangeException（）;
       array = new T[initialCapacity];
       topOfStack = -1;
     }

     /// <summary>
     /// 查看Stack是否为空
     /// </summary>
     public bool IsEmpty（）
     {
       return topOfStack == -1;
     }

     /// <summary>
     /// 进栈
     /// </summary>
     public void Push（T item）
     {
       if （this.Count == array.Length）
       {
         T[] newArray = new T[this.Count == 0 ？ defaultCapacity : 2 *  array.Length];
         Array.Copy（array, 0, newArray, 0, this.Count）;
         array = newArray;
       }
       this.array[++topOfStack] = item;
     }
     /// <summary>
     /// 出栈
     /// </summary>
     public T Pop（）
     {
       if （this.IsEmpty（））
         throw new InvalidOperationException（"The stack is empty."）;
       T popped = array[topOfStack];
       array[topOfStack] = default（T）;
       topOfStack--;
       return popped;
     }
     /// <summary>
     /// 返回栈顶，但不删除栈顶的值。
     /// </summary>
     public T Peek（）
     {
       if （this.IsEmpty（））
         throw new InvalidOperationException（"The stack is empty."）;
       return array[topOfStack];
     }
     /// <summary>
     /// Stack内元素的数量
     /// </summary>
     public int Count
     {
       get
       {
         return this.topOfStack + 1;
       }
     }
   }
}