算法系列15天速成 第十天 栈
一： 概念
栈，同样是一种特殊的线性表，是一种last in first out（lifo)的形式，现实中有很多这样的例子，
比如：食堂中的一叠盘子，我们只能从顶端一个一个的取。
二：存储结构
”栈“不像”队列“，需要两个指针来维护，栈只需要一个指针就够了，这得益于栈是一种一端受限的线性表。
这里同样用”顺序结构“来存储这个”栈“，top指针指向栈顶，所有的操作只能在top处。
代码段：
#region 栈的数据结构
/// <summary>
/// 栈的数据结构
/// </summary>
public class seqstack<t>
{
public t[] data;
/// <summary>
/// 栈顶指针
/// </summary>
public int top = -1;
public seqstack(int lenth)
{
data = new t[lenth];
}
}
#endregion
三：常用操作
栈的操作有：①初始化栈，②入栈，③出栈，④获取栈顶。
1: 初始化栈
这个还是比较简单的，初始化栈时，设置默认top指针为-1，这个就不用图来展示了。
代码段：
#region 栈的初始化操作
/// <summary>
/// 栈的初始化操作
/// </summary>
/// <typeparam name="t"></typeparam>
/// <returns></returns>
public seqstack<t> seqstackinit<t>(int length)
{
seqstack<t> seqstack = new seqstack<t>(length);
seqstack.top = -1;
return seqstack;
}
#endregion
2：入栈
这个操作主要就是做两件事情：① 将元素从栈顶压入，② top指针自增。
代码段：
#region 入栈
/// <summary>
/// 入栈
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <param name="data"></param>
public void seqstackpush<t>(seqstack<t> seqstack, t data)
{
if (seqstackisfull(seqstack))
throw new exception("不好意思，栈溢出");
seqstack.data[++seqstack.top] = data;
}
#endregion
3：出栈
同样跟“入栈”类似，需要做两件事情，①干掉top处的元素，②top指针自减。
代码段
#region 出栈
/// <summary>
/// 出栈
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <returns></returns>
public t seqstackpop<t>(seqstack<t> seqstack)
{
if (seqstackisempty(seqstack))
throw new exception("呜呜，栈已空");
seqstack.data[seqstack.top] = default(t);
return seqstack.data[--seqstack.top];
}
#endregion
4：获取栈顶元素
这个很简单，跟“出栈”唯一不同的是不破坏栈顶元素，只是翻出来看看而已。
代码段
#region 获取栈顶
/// <summary>
/// 获取栈顶
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <returns></returns>
public t seqstackpeek<t>(seqstack<t> seqstack)
{
if (seqstackisempty(seqstack))
throw new exception("栈已空");
return seqstack.data[seqstack.top];
}
#endregion
总的运行代码如下
using system;
using system.collections.generic;
using system.linq;
using system.text;
namespace seqstack
{
class program
{
static void main(string[] args)
{
seqstackclass stackmanager = new seqstackclass();
seqstack<student> seqstack = stackmanager.seqstackinit<student>(10);
console.writeline("******************** 压入id=1,id=2,id=3的元素 ***********************\n");
//压入id=1,id=2,id=3的元素
stackmanager.seqstackpush(seqstack, new student() { id = 1, name = "一线码农", age = 23 });
stackmanager.seqstackpush(seqstack, new student() { id = 2, name = "huangxincheng520", age = 23 });
stackmanager.seqstackpush(seqstack, new student() { id = 3, name = "51cto", age = 23 });
console.writeline(".... 压入成功，当前栈中元素有：" + stackmanager.seqstacklen(seqstack) + "个");
console.writeline("\n****************** 查看栈顶元素 ********************");
var result = stackmanager.seqstackpeek(seqstack);
console.writeline("栈顶元素为：id=" + result.id + ",name=" + result.name + ",age=" + result.age);
console.writeline("\n******************** 弹出栈顶元素 ***********************");
stackmanager.seqstackpop(seqstack);
console.writeline("\n****************** 查看栈中的元素 ********************");
for (int i = 0; i < stackmanager.seqstacklen(seqstack); i++)
{
console.writeline("栈顶元素为：id=" + seqstack.data[i].id + ",name=" + seqstack.data[i].name + ",age=" + seqstack.data[i].age);
}
console.read();
}
}
#region 学生数据实体
/// <summary>
/// 学生数据实体
/// </summary>
public class student
{
public int id { get; set; }
public string name { get; set; }
public int age { get; set; }
}
#endregion
#region 栈的数据结构
/// <summary>
/// 栈的数据结构
/// </summary>
public class seqstack<t>
{
public t[] data;
/// <summary>
/// 栈顶指针
/// </summary>
public int top = -1;
public seqstack(int lenth)
{
data = new t[lenth];
}
}
#endregion
public class seqstackclass
{
#region 栈的初始化操作
/// <summary>
/// 栈的初始化操作
/// </summary>
/// <typeparam name="t"></typeparam>
/// <returns></returns>
public seqstack<t> seqstackinit<t>(int length)
{
seqstack<t> seqstack = new seqstack<t>(length);
seqstack.top = -1;
return seqstack;
}
#endregion
#region 判断栈是否为空
/// <summary>
/// 判断栈是否为空
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <returns></returns>
public bool seqstackisempty<t>(seqstack<t> seqstack)
{
return seqstack.top == -1;
}
#endregion
#region 清空栈
/// <summary>
/// 清空栈
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
public void seqstackclear<t>(seqstack<t> seqstack)
{
seqstack.top = -1;
}
#endregion
#region 栈是否已满
/// <summary>
/// 栈是否已满
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
public bool seqstackisfull<t>(seqstack<t> seqstack)
{
return seqstack.top == seqstack.data.length;
}
#endregion
#region 入栈
/// <summary>
/// 入栈
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <param name="data"></param>
public void seqstackpush<t>(seqstack<t> seqstack, t data)
{
if (seqstackisfull(seqstack))
throw new exception("不好意思，栈溢出");
seqstack.data[++seqstack.top] = data;
}
#endregion
#region 出栈
/// <summary>
/// 出栈
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <returns></returns>
public t seqstackpop<t>(seqstack<t> seqstack)
{
if (seqstackisempty(seqstack))
throw new exception("呜呜，栈已空");
seqstack.data[seqstack.top] = default(t);
return seqstack.data[--seqstack.top];
}
#endregion
#region 获取栈顶
/// <summary>
/// 获取栈顶
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <returns></returns>
public t seqstackpeek<t>(seqstack<t> seqstack)
{
if (seqstackisempty(seqstack))
throw new exception("栈已空");
return seqstack.data[seqstack.top];
}
#endregion
#region 获取栈中元素个数
/// <summary>
/// 获取栈中元素个数
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="seqstack"></param>
/// <returns></returns>
public int seqstacklen<t>(seqstack<t> seqstack)
{
return seqstack.top + 1;
}
#endregion
}
}