数据结构学习之栈
开篇：上次我们学习了基本的数组结构。
今天，我们来学习另一个线性的数据结构，栈。
栈这种数据结构，无时无刻不在我们的身边。是种极其重要的数据结构。
所以，什么是栈呢？(不要废话了，快说)
先来看我们生活中，比如我们经常操作的word文档。
我们比如写入四个字， (天气真好)。
我们不想要了这句话，ctrl+z 回撤掉我们所打的。你会很自然发现，消失的顺序会是，好->真->气->天。
别急。 我们再来个例子。
比如那我们的函数调用，
计算机需要有个系统栈来记录我们的函数调用。
public void a()
{
b();
}
public void b()
{
c();
}
public void c()
{
//....
}
a为我们的主函数，当a调用b的时候，进入b函数时，会在a函数中断的位置把函数地址信息压入到系统栈里。
此时b函数又在用掉c函数，此时又会在b函数中断的位置把函数地址信息压入到系统栈里。
此时c执行完后，该怎么办呢。此时系统栈里会取出栈顶元素为返回的地址，为b，程序便正确的回到b处。
同样的。b执行完,系统栈又会取出栈顶元素为返回的地址，为a，程序便正确的回到a处。
此时我们正完成了我们的函数调用。
如我们的图所示:
所以。栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。
插入和删除都在栈顶这一端操作。
包括我们的经常使用编程的ide，会自动检查括号的匹配等等。都是基于栈的结构。
现在，我们基于我们上次的线性数组。来实现我们的自定义栈结构。
我们让我们的结构实现我们的泛型istack接口来实现。
分别有pop出栈，push入栈。判断是否为空和清空操作等。
/// <summary>
/// 栈
/// </summary>
/// <typeparam name="t"></typeparam>
public interface istack<t>
{
void push(t value);
t pop();
t peek();
bool isempty();
void clear();
}
public class stack<t> : istack<t>
{
private array<t> data;
public stack(int capacity=20)
{
this.data = new array<t>(capacity);
}
public void clear()
{
this.data.setempty();
}
public bool isempty()
{
return this.data.getsize() == 0;
}
public t peek()
{
return this.data.search(this.data.getsize());
}
public t pop()
{
return this.data.delete(this.data.getsize());
}
public void push(t value)
{
this.data.add(value);
}
}
由此可见。这是一个重要的数据结构。
届时，我们来看看leetcode上的一道典型的链表题目。20题
题目是这样的。
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
先给出代码(c#)。
public class solution {
public bool isvalid(string str) {
var stack = new stack();
for (int i = 0; i < str.length; i++)
{
if (str[i] == '[' || str[i] == '{' || str[i] == '(')
stack.push(str[i]);
else if(str[i] == ']' || str[i] == '}' || str[i] == ')')
{
if (stack.count == 0)
return false;
var top = (char)stack.pop();
if (str[i] == ')' && top != '(')
return false;
if (str[i] == ']' && top != '[')
return false;
if (str[i] == '}' && top != '{')
return false;
}
}
return stack.count==0;
}
}
使用的stack类为我们的c#本身为我们提供的栈结构。
本题目是 [，(,,{ 三种括号的匹配。
我们判断。如果是这三种，我们就相应的入栈。当遇到他们所匹配的结尾括号时，],),}时候。
便相应的出栈。如果不是他们对应的标签。便是不符合要求的。当一一遍历出栈后。
如果栈为空时。便说明便是符合要求的。
今天我们的栈就到这里啦，下一次，我们来实现另一种线性结构,队列。