客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
理论基础： 栈(Stack)是操作限定在表的尾端进行的线性表。表尾由于要进行插入、删除等操作，所以，它具有特殊的含义，把表尾称为栈顶（Top），另一端是固定的，叫栈底（Bottom）。当栈中没有数据元素时叫空栈(Empty Stack)。 栈可以分为顺序栈和链栈。 用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈(Sequence Stack)。类似于顺序表，用一维数组来存放顺序栈中的数据元素。栈顶指示器top设在数组下标为0的端，top随着插入和删除而变化，当栈为空时，top=-1。 链栈通常用单链表来表示，它的实现是单链表的简化。所以，链栈结点的结构与单链表结点的结构一样，如图3.3所示。由于链栈的操作只是在一端进行，为了操作方便，把栈顶设在链表的头部，并且不需要头结点。
C#实现： 顺序栈 1 接口 用泛型接口来表示栈，接口中的方法成员表示基本操作 1: public interface IStack<T> 2: {
3:
4: /// <summary> 5: /// 求栈的长度 6: /// </summary> 7: /// <returns></returns> 8: int GetLength(); 9: /// <summary> 10: /// 判断栈是否为空 11: /// </summary> 12: /// <returns></returns> 13: bool IsEmpty(); 14: /// <summary> 15: /// 判断栈是否已满 16: /// </summary> 17: /// <returns></returns> 18: bool IsFull(); 19: /// <summary> 20: /// 清空操作 21: /// </summary> 22: void Clear(); 23: /// <summary> 24: /// 入栈操作 25: /// </summary> 26: /// <param name="item"></param> 27: void Push(T item); 28: /// <summary> 29: /// 出栈操作 30: /// </summary> 31: /// <returns></returns> 32: T Pop();
33: /// <summary> 34: /// 取栈元素 35: /// </summary> 36: /// <param name="index"></param> 37: /// <returns></returns> 38: T GetElement(int index); 39:
40: }
2 实现 下面实现的代码没有经过测试，不知道正确与否，有兴趣的朋友试试。 1: public class SeqStack<T> : IStack<T> 2: {
3: private int maxsize; //顺序栈的容量 4: private T[] data; //数组，用于存储顺序栈中的数据元素 5: private int top; //栈顶 6:
7: //索引器 8: public T this[int index] 9: {
10: get
11: {
12: return data[index]; 13: }
14: set
15: {
16: data[index] = value; 17: }
18: }
19: public int MaxSize 20: {
21: get
22: {
23: return maxsize; 24: }
25: set
26: {
27: maxsize = value; 28: }
29: }
30:
31: public int Top 32: {
33: get
34: {
35: return top; 36: }
37: }
38:
39: public SeqStack(int size) 40: {
41: data = new T[size]; 42: maxsize = size;
43: top = -1;
44: }
45:
46: /// <summary> 47: /// 求栈的长度 48: /// </summary> 49: /// <returns></returns> 50: public int GetLength() 51: {
52: return top + 1; 53: }
54: /// <summary> 55: /// 判断栈是否为空 56: /// </summary> 57: /// <returns></returns> 58: public bool IsEmpty() 59: {
60: if (top == -1) 61: {
62: return true; 63: }
64: else 65: {
66: return false; 67: }
68: }
69: /// <summary> 70: /// 判断栈是否已满 71: /// </summary> 72: /// <returns></returns> 73: public bool IsFull() 74: {
75: if (top == maxsize - 1) 76: {
77: return true; 78: }
79: else 80: {
81: return false; 82: }
83: }
84: /// <summary> 85: /// 清空操作 86: /// </summary> 87: public void Clear() 88: {
89: top = -1;
90: }
91: /// <summary> 92: /// 入栈操作 93: /// </summary> 94: /// <param name="item"></param> 95: public void Push(T item) 96: {
97: if (IsFull()) 98: {
99: Console.Write("Stack is full"); 100: return; 101: }
102: data[++top] = item;
103: }
104: /// <summary> 105: /// 出栈操作 106: /// </summary> 107: /// <returns></returns> 108: public T Pop() 109: {
110: if (IsEmpty()) 111: {
112: Console.Write("Stack is empty"); 113: return default(T); 114: }
115: T outEle = data[top];
116: --top;
117: return outEle; 118: }
119: /// <summary> 120: /// 取栈顶元素 121: /// </summary> 122: /// <param name="index"></param> 123: /// <returns></returns> 124: public T GetElement(int index) 125: {
126: if (IsEmpty()) 127: {
128: Console.Write("Stack is empty"); 129: return default(T); 130: }
131: if (index < 0 && index > top + 1) 132: {
133: Console.Write("index is error"); 134: return default(T); 135: }
136: return data[index - 1]; 137: }
138: }
由于链栈的操作与单链表很相似，这里就不说明代码，有兴趣的朋友可以写出来，供大家分享。 C#中的栈： C#2.0以下版本只提供了非泛型的Stack类，该类继承了ICollection、IEnumerable和ICloneable接口。 C#2.0提供了泛型的Stack<T>类，该类继承了IEnumerable<T>、ICollection和IEnumerable接口，关于泛型Stack<T>类的更具体的信息，读者可参考.NET Framework的有关书籍 |
请发表评论