1.栈的实现
后进先出
自己实现栈的代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections; namespace 数据结构和算法
{
//栈
class CStack
{
private ArrayList list;
private int p_index;
public CStack()
{
list = new ArrayList();
p_index = -1;
}
public int count
{
get { return list.Count; }
} public void Push(object item)
{
list.Add(item);
p_index++;
} public object Pop()
{
object obj = list[p_index];
list.RemoveAt(p_index);
p_index--;
return obj;
} public void Clear()
{
list.Clear();
p_index = -1;
}
//查看
public object Peek()
{
return list[p_index];
} static void Main(string[] args)
{
//回文: sees倒过来还是sees
CStack alist = new CStack();
string ch;
string word = "sees";
bool ispalindrome = true;
for (int i = 0; i < word.Length; i++)
{
alist.Push(word.Substring(i, 1));
}
int pos = 0;
while (alist.count > 0)
{
ch = alist.Pop().ToString();
if (ch!=word.Substring(pos,1))
{
ispalindrome = false;
break;
}
pos++;
}
if (ispalindrome)
{
Console.WriteLine(word+" 是回文.");
}
else
{
Console.WriteLine(word + " 不是回文.");
} Console.ReadKey();
}
}
}
2.Stack类(堆栈)
Stack 类是 ICollection 接口的一个实现。它代表了一个 LIFO 群集或一个堆栈。此类在.NET 框架中是作为循环缓冲来实现的。这使得能动态地分配进栈数据项的空间。
Stack 类包含进栈方法、出栈方法以及取值方法。此外，还有用于确定堆栈内元素数量的方法，清除堆栈全部数值的方法，以及把堆栈数值作为数组返回的方法。
CopyTo 方法和 ToArray 方法
CopyTo 方法会把堆栈内的内容复制到一个数组中。数组必须是 Object 类型，因为这是所有堆栈对象的数据类型。此方法会取走两个参数：一个数组和开始放置堆栈元素的数组的起始索引。堆栈内元素按照 LIFO 的顺序进行复制操作，就好像对它们进行出栈操作一样。下面这段代码说明了 CopyTo 方法的调用：
Stack myStack = new Stack();
for (int i = 20; i > 0; i--)
myStack.Push(i);
object[] myArray = new object[myStack.Count];
myStack.CopyTo(myArray, 0);
ToArray 方法的工作原理与 CopyTo 方法类似。但是用户无法指定数组的起始索引位置，而是需要在赋值语句中创建新的数组。实例如下所示：
Stack myStack = new Stack();
for (int i = 0; i > 0; i++)
myStack.Push(i);
object[] myArray = new object[myStack.Count];
myArray = myStack.ToArray();
堆栈的实际操作
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions; namespace 数据结构和算法
{
class 堆栈的操作
{
static void Main()
{
Stack nums = new Stack();
Stack ops = new Stack();
string expression = "5 + 10 + 15 +20";
Calculate(nums, ops, expression); Console.WriteLine("Pop之前的数据：" + nums.Peek());
nums.Push("1");
Console.WriteLine("Pop的数据：" + nums.Pop());
//nums.Push("1");
Console.WriteLine("Pop之后的数据：" + nums.Peek());
nums.Clear();
if (nums.Count == 0)
{
Console.WriteLine("Clear之后的数据为空");
}
else
Console.WriteLine("Clear之后的数据是否为空" + nums.Peek());
Console.Read();
} //IsNumeric isn'tbuilt into C# so we must define it
static bool IsNumeric(string input)
{
bool flag = true;
string pattern = (@"^\d+$");
Regex validate = new Regex(pattern);
if (!validate.IsMatch(input))
{
flag = false;
}
return flag;
} static void Calculate(Stack N, Stack O, string exp)
{
string ch, token = "";
for (int p = 0; p < exp.Length; p++)
{
ch = exp.Substring(p, 1);
if (IsNumeric(ch))
{
token += ch; //+=
}
if (ch == " " || p == (exp.Length - 1))
{
if (IsNumeric(token))
{
N.Push(token);
token = "";
}
}
else if (ch == "+" || ch == "-" || ch == "*" || ch == "/")
{
O.Push(ch);
}
if (N.Count == 2)
{
Compute(N, O);
}
}
} static void Compute(Stack N, Stack O)
{
int oper1, oper2;
string oper;
oper1 = Convert.ToInt32(N.Pop());
oper2 = Convert.ToInt32(N.Pop());
oper = Convert.ToString(O.Pop());
switch (oper)
{
case "+":
N.Push(oper1 + oper2);
break;
case "-":
N.Push(oper1 - oper2);
break;
case "*":
N.Push(oper1 * oper2);
break;
case "/":
N.Push(oper1 / oper2);
break;
}
}
}
}
3.队列
先进先出
enQueue 排队
deQueue 出队
4.Queue类 （队列）
在对一个新的 Queue 对象实例化的时候，队列默认的容量是 32 个数据项。根据定义，当队列已满时，其容量会双倍增长。这就意味着当队列最初达到满容量时，其新的容量值会变为 64。但是大家可以不用受这些数值的限制。
在实例化对队列时，大家可以指定一个不同的初始容量值。
Queue myQueue = new Queue(100);
这个设置把队列的容量值设为了 100 个数据项。当然，大家也可以改变增长的倍数。增长倍数是传递给构造器的第二个参数，如下所示：
Queue myQueue = new Queue(32, 3);
用队列存储数据
基数排序是通过对一组数据进行两遍排序来操作的。在这种情况下，整数的取值范围是从 0 到 99。第一遍是基于个位上的数字进行排序，而第二遍则是基于十位上的数字进行排序。然后，根据这些位置上的每个数字来把每一个数放置在一个箱子内。
假设有下列这些数： 91、 46、 85、 15、 92、 35、 31、 22。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text; namespace 数据结构和算法
{
class 用队列存储数据
{
enum DigitType {
//个位
ones = 1,
//十位
tens = 10
} //打印排序后的内容
static void DisplayArray(int[] n)
{
for (int x = 0; x <= n.GetUpperBound(0); x++)
Console.Write(n[x] + " ");
} //排序
static void RSort(Queue[] que, int[] n, DigitType digit)
{
int snum;//下标 for (int x = 0; x <= n.GetUpperBound(0); x++)
{
if (digit == DigitType.ones)
snum = n[x] % 10;
else
snum = n[x] / 10;
que[snum].Enqueue(n[x]);
}
} static void BuildArray(Queue[] que, int[] n)
{
int y = 0;
for (int x = 0; x <= 9; x++)
//que的下标count大于0的时候，替换n
while (que[x].Count > 0)
{
n[y] =
Int32.Parse(que[x].Dequeue().ToString());
y++;
}
} static void Main(string[] args)
{
Queue[] numQueue = new Queue[10];
int[] nums = new int[] { 91, 46, 85, 15, 92, 35, 31, 22 };
int[] random = new Int32[99]; DisplayArray(nums); // Display original list
for (int i = 0; i < 10; i++)
numQueue[i] = new Queue(); RSort(numQueue, nums, DigitType.ones);
//numQueue, nums, 1
BuildArray(numQueue, nums);
Console.WriteLine();
Console.WriteLine("第1次排序: ");
//打印排序后的内容
DisplayArray(nums);
// Second pass sort
RSort(numQueue, nums, DigitType.tens);
BuildArray(numQueue, nums);
Console.WriteLine();
Console.WriteLine("第2次排序结果: ");
//打印排序后的内容
DisplayArray(nums);
Console.WriteLine();
Console.Write("Press enter to quit");
Console.Read();
}
}
}
5. Queue 类的优先队列
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text; namespace 数据结构和算法
{
public struct pqItem
{
//优先级
public int priority;
public string name;
} public class PQueue : Queue
{
static void Main()
{
PQueue erwait = new PQueue();
pqItem[] erPatient = new pqItem[3];
pqItem nextPatient;
erPatient[0].name = "刘在锡";
erPatient[0].priority = 1;
erPatient[1].name = "李光洙";
erPatient[1].priority = 0;
erPatient[2].name = "金钟国";
erPatient[2].priority = 3; for (int x = 0; x <= erPatient.GetUpperBound(0); x++)
erwait.Enqueue(erPatient[x]); nextPatient = (pqItem)erwait.Dequeue(); Console.WriteLine(nextPatient.name);
Console.Read();
} public PQueue()
{ } //重写出队
public override object Dequeue()
{
object[] items; int min;
items = this.ToArray();
//假设第1个最小
min = ((pqItem)items[0]).priority; for (int x = 1; x <= items.GetUpperBound(0); x++)
if (((pqItem)items[x]).priority < min)
{
min = ((pqItem)items[x]).priority;
} this.Clear(); int x2; for (x2 = 0; x2 <= items.GetUpperBound(0); x2++)
if (((pqItem)items[x2]).priority == min && ((pqItem)items[x2]).name != "")
this.Enqueue(items[x2]); return base.Dequeue();
}
} }