当前位置:坤哥网-gooditblog-算法系列15天速成——第十天 栈

算法系列15天速成——第十天 栈

2011/12/3 23:01:00 gooditblog阅读(237) 评论(2)

 

今天跟大家聊聊栈,在程序设计中,栈的使用还是非常广泛的,比如有“括号匹配问题“,”html结构匹配问题“。

所以说掌握了”栈“的使用,对我们学习算法还是很有帮助的。

 

一: 概念

         栈,同样是一种特殊的线性表,是一种Last In First Out(LIFO)的形式,现实中有很多这样的例子,

     比如:食堂中的一叠盘子,我们只能从顶端一个一个的取。

 

二:存储结构

        ”栈“不像”队列“,需要两个指针来维护,栈只需要一个指针就够了,这得益于栈是一种一端受限的线性表。

      这里同样用”顺序结构“来存储这个”栈“,top指针指向栈顶,所有的操作只能在top处。

         

代码段:

 1 #region 栈的数据结构
2 /// <summary>
3 /// 栈的数据结构
4 /// </summary>
5 public class SeqStack<T>
6 {
7 public T[] data;
8
9 /// <summary>
10 /// 栈顶指针
11 /// </summary>
12 public int top = -1;
13
14 public SeqStack(int lenth)
15 {
16 data = new T[lenth];
17 }
18 }
19 #endregion

 

 

三:常用操作

        栈的操作有:①初始化栈,②入栈,③出栈,④获取栈顶。

 

1: 初始化栈

        这个还是比较简单的,初始化栈时,设置默认top指针为-1,这个就不用图来展示了。

 

代码段:

 1 #region 栈的初始化操作
2 /// <summary>
3 /// 栈的初始化操作
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <returns></returns>
7 public SeqStack<T> SeqStackInit<T>(int length)
8 {
9 SeqStack<T> seqStack = new SeqStack<T>(length);
10
11 seqStack.top = -1;
12
13 return seqStack;
14 }
15 #endregion


2:入栈

       这个操作主要就是做两件事情:① 将元素从栈顶压入,② top指针自增。

代码段:

 1 #region 入栈
2 /// <summary>
3 /// 入栈
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="seqStack"></param>
7 /// <param name="data"></param>
8 public void SeqStackPush<T>(SeqStack<T> seqStack, T data)
9 {
10 if (SeqStackIsFull(seqStack))
11 throw new Exception("不好意思,栈溢出");
12
13 seqStack.data[++seqStack.top] = data;
14 }
15 #endregion

 

3:出栈

      同样跟“入栈”类似,需要做两件事情,①干掉top处的元素,②top指针自减。

代码段

 1 #region 出栈
2 /// <summary>
3 /// 出栈
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="seqStack"></param>
7 /// <returns></returns>
8 public T SeqStackPop<T>(SeqStack<T> seqStack)
9 {
10 if (SeqStackIsEmpty(seqStack))
11 throw new Exception("呜呜,栈已空");
12
13 seqStack.data[seqStack.top] = default(T);
14
15 return seqStack.data[--seqStack.top];
16 }
17 #endregion

 

4:获取栈顶元素

      这个很简单,跟“出栈”唯一不同的是不破坏栈顶元素,只是翻出来看看而已。

 

代码段

 1 #region 获取栈顶
2 /// <summary>
3 /// 获取栈顶
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="seqStack"></param>
7 /// <returns></returns>
8 public T SeqStackPeek<T>(SeqStack<T> seqStack)
9 {
10 if (SeqStackIsEmpty(seqStack))
11 throw new Exception("栈已空");
12
13 return seqStack.data[seqStack.top];
14 }
15 #endregion

 

总的运行代码如下

View Code
  1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace SeqStack
7 {
8 class Program
9 {
10 static void Main(string[] args)
11 {
12 SeqStackClass stackManager = new SeqStackClass();
13
14 SeqStack<Student> seqStack = stackManager.SeqStackInit<Student>(10);
15
16 Console.WriteLine("******************** 压入ID=1,ID=2,ID=3的元素 ***********************\n");
17 //压入ID=1,ID=2,ID=3的元素
18 stackManager.SeqStackPush(seqStack, new Student() { ID = 1, Name = "一线码农", Age = 23 });
19 stackManager.SeqStackPush(seqStack, new Student() { ID = 2, Name = "huangxincheng520", Age = 23 });
20 stackManager.SeqStackPush(seqStack, new Student() { ID = 3, Name = "51cto", Age = 23 });
21
22 Console.WriteLine(".... 压入成功,当前栈中元素有:" + stackManager.SeqStackLen(seqStack) + "");
23
24 Console.WriteLine("\n****************** 查看栈顶元素 ********************");
25
26 var result = stackManager.SeqStackPeek(seqStack);
27
28 Console.WriteLine("栈顶元素为:ID=" + result.ID + ",Name=" + result.Name + ",Age=" + result.Age);
29
30 Console.WriteLine("\n******************** 弹出栈顶元素 ***********************");
31
32 stackManager.SeqStackPop(seqStack);
33
34 Console.WriteLine("\n****************** 查看栈中的元素 ********************");
35
36 for (int i = 0; i < stackManager.SeqStackLen(seqStack); i++)
37 {
38 Console.WriteLine("栈顶元素为:ID=" + seqStack.data[i].ID + ",Name=" + seqStack.data[i].Name + ",Age=" + seqStack.data[i].Age);
39 }
40
41 Console.Read();
42 }
43 }
44
45 #region 学生数据实体
46 /// <summary>
47 /// 学生数据实体
48 /// </summary>
49 public class Student
50 {
51 public int ID { get; set; }
52
53 public string Name { get; set; }
54
55 public int Age { get; set; }
56 }
57 #endregion
58
59 #region 栈的数据结构
60 /// <summary>
61 /// 栈的数据结构
62 /// </summary>
63 public class SeqStack<T>
64 {
65 public T[] data;
66
67 /// <summary>
68 /// 栈顶指针
69 /// </summary>
70 public int top = -1;
71
72 public SeqStack(int lenth)
73 {
74 data = new T[lenth];
75 }
76 }
77 #endregion
78
79 public class SeqStackClass
80 {
81 #region 栈的初始化操作
82 /// <summary>
83 /// 栈的初始化操作
84 /// </summary>
85 /// <typeparam name="T"></typeparam>
86 /// <returns></returns>
87 public SeqStack<T> SeqStackInit<T>(int length)
88 {
89 SeqStack<T> seqStack = new SeqStack<T>(length);
90
91 seqStack.top = -1;
92
93 return seqStack;
94 }
95 #endregion
96
97 #region 判断栈是否为空
98 /// <summary>
99 /// 判断栈是否为空
100 /// </summary>
101 /// <typeparam name="T"></typeparam>
102 /// <param name="seqStack"></param>
103 /// <returns></returns>
104 public bool SeqStackIsEmpty<T>(SeqStack<T> seqStack)
105 {
106 return seqStack.top == -1;
107 }
108 #endregion
109
110 #region 清空栈
111 /// <summary>
112 /// 清空栈
113 /// </summary>
114 /// <typeparam name="T"></typeparam>
115 /// <param name="seqStack"></param>
116 public void SeqStackClear<T>(SeqStack<T> seqStack)
117 {
118 seqStack.top = -1;
119 }
120 #endregion
121
122 #region 栈是否已满
123 /// <summary>
124 /// 栈是否已满
125 /// </summary>
126 /// <typeparam name="T"></typeparam>
127 /// <param name="seqStack"></param>
128 public bool SeqStackIsFull<T>(SeqStack<T> seqStack)
129 {
130 return seqStack.top == seqStack.data.Length;
131 }
132 #endregion
133
134 #region 入栈
135 /// <summary>
136 /// 入栈
137 /// </summary>
138 /// <typeparam name="T"></typeparam>
139 /// <param name="seqStack"></param>
140 /// <param name="data"></param>
141 public void SeqStackPush<T>(SeqStack<T> seqStack, T data)
142 {
143 if (SeqStackIsFull(seqStack))
144 throw new Exception("不好意思,栈溢出");
145
146 seqStack.data[++seqStack.top] = data;
147 }
148 #endregion
149
150 #region 出栈
151 /// <summary>
152 /// 出栈
153 /// </summary>
154 /// <typeparam name="T"></typeparam>
155 /// <param name="seqStack"></param>
156 /// <returns></returns>
157 public T SeqStackPop<T>(SeqStack<T> seqStack)
158 {
159 if (SeqStackIsEmpty(seqStack))
160 throw new Exception("呜呜,栈已空");
161
162 seqStack.data[seqStack.top] = default(T);
163
164 return seqStack.data[--seqStack.top];
165 }
166 #endregion
167
168 #region 获取栈顶
169 /// <summary>
170 /// 获取栈顶
171 /// </summary>
172 /// <typeparam name="T"></typeparam>
173 /// <param name="seqStack"></param>
174 /// <returns></returns>
175 public T SeqStackPeek<T>(SeqStack<T> seqStack)
176 {
177 if (SeqStackIsEmpty(seqStack))
178 throw new Exception("栈已空");
179
180 return seqStack.data[seqStack.top];
181 }
182 #endregion
183
184 #region 获取栈中元素个数
185 /// <summary>
186 /// 获取栈中元素个数
187 /// </summary>
188 /// <typeparam name="T"></typeparam>
189 /// <param name="seqStack"></param>
190 /// <returns></returns>
191 public int SeqStackLen<T>(SeqStack<T> seqStack)
192 {
193 return seqStack.top + 1;
194 }
195 #endregion
196 }
197 }

 

 

 

 


原文:http://www.cnblogs.com/huangxincheng/p/2275065.html
标签:
分类: 算法

发表评论 没有账号,注册评论