135-1821-9792
栈在我们日常编码中遇到的非常多，很多人对栈的接触可能仅仅局限在 递归使用的是栈 和 StackOverflowException，栈是一种后进先出的数据结构(可以想象生化金字塔的牢房和生化角斗场的狗洞)。栈，简单而又不简单，是因为直接学习栈比较容易，但使用栈解决问题很多时候需要巧妙的方法。
创新互联公司从2013年开始，是专业互联网技术服务公司，拥有项目做网站、成都做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元襄城做网站,已为上家服务,为襄城各地企业和个人服务,联系电话:18982081108
本文着重讲解栈数据结构的设计与实现，然后在文末补充两道栈非常非常经典的问题!一定要会!
勾起一波回忆
栈是这么定义的：
栈(stack)又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
稍微介绍一下关键名词：
运算受限：也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端进行插入和删除。同样，队列也是运算受限，只能在两头操作。
线性表：栈也是一种线性表，前面详细介绍过线性表，它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分数组和链表实现，他们的物理存储结构不同。但是逻辑结构(实现的目的)相同。
栈顶栈底： 这个描述是偏向于逻辑上的内容，因为大家知道数组在末尾插入删除更容易，而单链表通常在头插入删除更容易。所以数组可以用末尾做栈顶，而链表可以头做栈顶。
栈的应用： 栈的应用广泛，比如你的程序执行查看调用堆栈、计算机四则加减运算、算法的非递归形式、括号匹配问题等等。所以栈也是必须掌握的一门数据结构。最简单大家都经历过，你拿一本书上下叠在一起，就是一个后进先出的过程，你可以把它看成一个栈。下面我们介绍数组实现的栈和链表实现的栈。
数组实现的栈用的比较多，我们经常刷题也会用数组去实现一个简单的栈去解决简单的问题。
结构设计
对于数组来说，我们模拟栈的过程很简单，因为栈是后进先出，我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。所以对于一个栈所需要的基础元素是 一个data[]数组和一个top(int)表示栈顶位置。
那么初始化函数代码为：
- private T data[];
- private int top;
- public seqStack() {
- data=(T[]) new Object[10];
- top=-1;
- }
- public seqStack(int maxsize)
- {
- data=(T[]) new Object[maxsize];
- top=-1;
- }
push插入
栈的核心操作之一push()：入栈操作。
pop弹出并返回首位
如果top>=0,栈不为空，可以弹出。return data[top--];
如下图，本来栈为1,2,3,4,5,6(栈顶),执行pop操作,top变为3的位置并且返回4;
其他操作
例如peek操作时返回栈顶不弹出.所以只需满足要求时候return data[top]即可。
数组实现：
- package 队栈;
- public class seqStack
{ - private T data[];
- private int top;
- public seqStack() {
- data=(T[]) new Object[10];
- top=-1;
- }
- public seqStack(int maxsize)
- {
- data=(T[]) new Object[maxsize];
- top=-1;
- }
- boolean isEmpty()
- {
- return top==-1;
- }
- int length()
- {
- return top+1;
- }
- boolean push(T value) throws Exception//压入栈
- {
- if(top+1>data.length-1)
- {
- throw new Exception("栈已满");
- }
- else {
- data[++top]=value;
- return true;
- }
- }
- T peek() throws Exception//返回栈顶元素不移除
- {
- if(!isEmpty())
- {
- return data[top];
- }
- else {
- throw new Exception("栈为空");
- }
- }
- T pop() throws Exception
- {
- if(isEmpty())
- {
- throw new Exception("栈为空");
- }
- else {
- return data[top--];
- }
- }
- public String toString()
- {
- if(top==-1)
- {
- return "";
- }
- else {
- String va="";
- for(int i=top;i>=0;i--)
- {
- va+=data[i]+" ";
- }
- return va;
- }
- }
- }
有数组实现，链表当然也能实现。对于栈的设计，大致可以分为两种思路：
结构设计
设计上和链表很相似，长话短说，短话不说，直接上代码就懂。
链表的节点：
- static class node
- {
- T data;
- node next;
- public node() {
- }
- public node(T value)
- {
- this.data=value;
- }
- }
基本结构：
- public class lisStack
{ - int length;
- node
head;//头节点 - public lisStack() {
- head=new node<>();
- length=0;
- }
- //其他方法
- }
push插入
与单链表头插入一致，如果不太了解可以看看前面写的线性表有具体讲解过程。
和数组形成的栈有个区别，链式实现的栈理论上栈没有大小限制(不突破内存系统限制)，不需要考虑是否越界，而数组则需要考虑容量问题。
如果一个节点team入栈：
pop弹出
与单链表头删除一致，如果不太了解请先看笔者对线性表介绍的。
和数组同样需要判断栈是否为空，如果节点team出栈：head指向team后驱节点。
其他操作
其他例如peek操作时返回栈顶不弹出.所以只需判空满足题意时候return head.next.data即可。而length你可以遍历链表返回长度，也可以动态设置(本文采取)跟随栈长变化。
链表实现：
- package 队栈;
- public class lisStack
{ - static class node
- {
- T data;
- node next;
- public node() {
- }
- public node(T value)
- {
- this.data=value;
- }
- }
- int length;
- node
head;//头节点 - public lisStack() {
- head=new node<>();
- length=0;
- }
- boolean isEmpty()
- {
- return head.next==null;
- }
- int length()
- {
- return length;
- }
- public void push(T value) {//近栈
- node
team=new node (value); - if(length==0)
- {
- head.next=team;
- }
- else {
- team.next=head.next;
- head.next=team;}
- length++;
- }
- public T peek() throws Exception {
- if(length==0) {throw new Exception("链表为空");}
- else {//删除
- return (T) head.next.data;
- }
- }
- public T pop() throws Exception {//出栈
- if(length==0) {throw new Exception("链表为空");}
- else {//删除
- T value=(T) head.next.data;
- head.next=head.next.next;//va.next
- length--;
- return value;
- }
- }
- public String toString(){
- if(length==0) {return "";}
- else {
- String va="";
- node team=head.next;
- while(team!=null)
- {
- va+=team.data+" ";
- team=team.next;
- }
- return va;
- }
- }
- }
既然上面详细讲解设计栈，这里来两道栈非常经典非常经典的例题(非常高频，很容易忘，又很重要，普通问题就不放的)
力扣20有效的括号：
题意：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 :
输入: "()[]{}"
输出: true
示例 :
输入: "([)]"
输出: false
分析：
括号类的问题是经典栈类问题，肯定要想到用栈处理。判断一个字符串满不满足一个有效的字符串，就要看它是不是都能组成对。
从单个括号对来说，((,))都是不满足的，只有()才可满足，即一左一右。
从多个括号对来说 {[(字符串还可接受任意无限(，[,{的括号。但是如果向左的括号只能先接收)括号(变成{[)。
从上面可以看作一种相消除的思想。例如(({[()()]}))字符串遍历时候可以这样处理：
每次操作的时候都判断剩余有效括号最顶部那个括号是否能够和遍历的相消除，这个过程利用栈判断当前是加入栈还是消除顶部，到最后如果栈为空说明满足，否则不满足，当然具体括号要对应，具体实现代码为：
在线咨询
在线咨询
