本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
栈和队列？什么玩意儿😂，别急，今天俺给您说道说道，保准您听了之后，还是不知道啥是栈和队列🤣，得了得了，不皮了，各位看官，您且听好嘞😄
对数据结构和算法不熟悉😥
要说到栈和队列，那一定先说两个概念，那就是”数据结构“和”算法“，我知道您可能还不是很了解啥是数据结构和算法😅，或者您知道，但是概念比较模糊，今天俺可不打算给您说它俩，只是给你个建议。
如果你觉得你自己对数据结构和算法的概念比较模糊，怎么整😥，有个办法，那就是找一天时间，专门研究啥是数据结构和算法，可以网上各种搜，也可以请教一些人，保准您花这一天时间，受益无穷😎
那俺就继续说今天的主角栈和队列了😁
啥是栈？啥是队列？😌
别急，俺现在就告诉你，我想啊，你在读我这篇文章之前嘞，肯定已经看过不少关于栈和队列的讲解了，或许看的时间比较久了，或许看的不明不白的😂，这都不是事，今天过后，你就不会再忘记啥事栈和队列了😎。
关于它俩你要知道的事😀
首先嘞，你要记住，栈和队列属于数据结构中的线性结构，也就是线性表，线性？啥玩意，没错，就是你想的那一根根的线，毛线，对，别疑惑，你肯定见过，长长的一根线。
在数据结构中，像数组，链表，栈和队列都属于线性结构，在这些数据结构中，或者说线性结构的一个特点吧，就是人家有个前驱后继的概念，就是一个元素的前后都能再找到一个元素，前面的就叫前驱，后面的就叫后继，看吧，很好理解😀
接着，你还需要知道啥是LIFO和FIFO🙄，咋不知道吗，那可不行，其实简单，就是缩写：
记住了，这两个缩写代表了栈和队列这两个数据结构对数据存取的特点
一个生活中的例子看栈😎
啥特点？😫
简单，先说栈这家伙，它是数据结构，就是告诉你，按照它的要求来存取数据的，啥要求，先举个生活中的例子，比如你妈妈让你刷盘子，加入有五个盘子，你肯定事这样干的：
啥意思，就是你最先洗完的那个盘子肯定是放在最低下的，然后其他的挨个往上放，最后洗完的那个盘子肯定是放在最上面的😃
那当我们需要用这些盘子的时候，肯定也是挨个从上面依次拿一个用拿一个用，对吧😁
但是嘞，如果你告诉我，您洗完盘子是这样放的：
我还能说啥，你家地方大呗😂，如果你再告诉我，你是从中间抽着用，我还能说啥？我认输还不行吗🤣
栈的数据存取
其实啊，对于栈，它就和这个刷盘子放盘子差不多，每个盘子其实就相当于一个数据，放好的这些盘子的结构就是栈这种数据结构，当然，对于对于盘子我们有放和取两个基本操作，同样的，对于栈来说，无非也就是数据的存取。
对于存就像放盘子一样，最先存进去的数据一定是在最下面的，最后一个存进去的数据肯定是在最上面的，那对于数据取来说，也是从上至下依次取用，我们用个图来表示的话，就是这些的嘞：
咋样，看的懂不😁，为了防止别人说我美工差，我必须得解释解释😂，这里1和2两个大红快你就可以看作是数据，外面的蓝框就可以看作是栈，现在往里面放数据，先把1放进去，看，一下坐到最底下了🤣，后面再来的都在它上面。
如果要对数据进行取用呢？那肯定也是先把2拿走才能拿1，不然你拿不到1啊，它被2给盖着嘞😅
再进一步来说，你可要记住了，这个栈啊，最底部可是封死的，也就是说，对于数据的存取，只允许你在一段进行操作，看上面那个图，被封死的那个口我们叫它栈底，允许你进行数据操作的那一个口，也就是开着的我们称为栈顶，咋样，这个还是很好理解的😏
所以，你发现没，对于栈这个数据结构来说啊，它对数据的存取是有一定要求的，也就是只让你在一段进行数据操作，也就是你只能操作栈顶的元素，另外，除了栈顶，其他元素你是不可见的，因为都盖住了😅，你看图是不是。
好了，到这里你知道了关于栈的两个术语，也就是栈底和栈顶，咋样，有没有成就感😂
知道了这么两个玩意儿，那就很容易理解啥是出栈啥是入栈了吧，入栈不就是把数据存进来，对了，存进来的这个数据就成了栈顶元素喽，那对于出栈，可不就是把数据拿走吗？
再看个图就是这样的：😃
咋一看，我画的图还不错啊😂
最后啊，为了让你更清楚了理解栈这个结构和它对数据存取的特点，我再给你说个东西，保准你恍然大悟，醍醐灌顶啊，啥嘞，不知道栈是啥样的是吧，打过羽毛球不，那知道装羽毛球的那个盒子吧，你拿羽毛球是不是开个口，然后挨个拿，你能直接拿到中间的吗？必须不啊，如果你说，我可以开俩口，可以拿到最后一个，我说大哥，咱能不抬杠不😂
所以啊，栈嘞，就是先放进去的要最后才能拿，对数据来说，就是后进先出（LIFO）.
一个生活中的例子看队列
现在你知道啥是栈了，那队列嘞😲，其实这俩货也差不多，都是对数据的存取有着比较特殊的要求，比如栈，人家就允许你在一段操作数据，也就是栈顶，你只能在栈顶玩耍，那么队列嘞。
首先，你看到队列俩字想到啥，排队？一群小学生排队？有相似之处，不过还是有差距，人家小学生排队，说不定哪个小男孩看上哪个小女孩就去插队了，就是学生可以自己随意走动，但是相比较队列这个数据结构就有点不同了😮
队列啊，人家对数据的要求也是有严格要求的，啥嘞，就是对于数据的存储，要在一端进另一端出，你想想栈那孩子，是不是只能在一端也就是栈顶玩耍，数据的存取都从栈顶这一个口，但是队列人家两端都开口，不过要求你从这端进必须那端出。
想想生活中汽车过涵洞，假如这个涵洞的宽度只能够一个汽车顺利通行，那汽车们是不是就要排好队，挨个进挨个出了，你说你想插队，那是不可能滴，看上哪个女司机，你也不能插过去啊😂
看图就是这样的：
这个画的确实有点抽象了哈😂，凑合着看吧😅
队列的数据存取
看看这些红红的方块车😂，要想顺利通过这个涵洞，是不是要按照顺序一个个来，最先开进去的也是最先开出来，这其实就是队列对数据存取的特点啊，先进先出（FIFO）😁
下面咱看看队列的示意图吧：
这里的入队，出队，队尾和队头应该都好理解啊，看着图一目了然啊，这就是队列了，这么一看，是不是感觉队列也好简单啊，其实关于队列的概念，只要好好看看，理解理解，还真的没啥难的😀
要记住的就是队列这家伙，要求的是一端进一端出，也就是要满足先进先出的原则。
其实关于队列还有什么循环队列和优先队列之类的，不要着急，路要一步步走，步子跨大了容易😂，以后肯定会讲到。
栈和队列难不难？😂
其实吧，关于数据结构这块啊，如果你仔细去学的话就会发现，关于数据结构的一些基本结构没啥难的，那么难的地方在哪呢？
那肯定是把这些数据结构用代码给实现出来啊😂，咋样，这一步对很多人来说是不是有难度，这个也是我们学习数据结构与算法必须跨过的坎，不过不用着急，我们一步步来，先把最基本的东西搞懂了，后面再去几种搞代码。
不过这次我还是简单说一些，因为其中牵涉的有些知识点还是很有必要现在就知道的。
怎么实现栈和队列
那你想想，像栈和队列这俩货，我们可以怎么实现他们呢？可以用什么来实现呢？😀
记住这句话：
基本上所有的数据结构都可以使用数组和链表来实现😁
所以啊，无论是对栈还是对队列来说，我们都可以使用数组和链表来实现他们，当然，使用数组和链表实现一定是有所不同的，因为本身数组和链表就是两个不同的数据结构。
记住了，用数组实现的栈叫做顺序栈，用链表实现的栈叫做链式栈，那队列嘞，同样的道理，那至于为啥叫顺序栈和链式栈，这个也好理解吧，这都是根据数组和链表各自的特点啊😀
接下来，我们就以数组来实现栈，从而说一些比较重要的知识点😎
数组实现顺序栈(思路分析)
那使用数组该怎么来实现一个栈呢？这次我重点是梳理思路，不会给出一些完整的代码的，因为我觉得只有你把思路理清了，你才知道使用数组实现栈的时候有些步骤为啥要那样做😉
需要些啥😮
那好，现在根据我们上面讲的栈的相关知识，我们来看，对于一个栈来说，它的基本操作无非就是入栈和出栈，我们列出来：
既然实现一个栈，我们用数组，那我们是不是要创建一个数组，用来底层存储栈的数据啊，好还需要一个数组：
好了，大致上我们直观感觉到的就是这么多了吧，接下来我画个图：
先看这么一个图😎，这跟之前画的那个图是一样的，只不过这个躺这了😂，现在我们要用数组实现一个栈，其实也就是按照栈的要求去往数组中存取数据。
数组该咋弄😂
栈啥要求？基本的就是后进先出，比如这里已经进去的四个元素，1是最先进去的，就放入栈底了，4在这里看是最后一个进的就属于栈顶元素了，现在，我们想想，代码需要写啥，首先肯定需要一个数组：
private int[] array;//用数组实现，只能存储整型数据
好，现在我们定义了一个数组，那你想想，这个数组我们该定多长呢？所以这是个问题吧，我们需要给个长度：
private final static int size = 10;
比如默认给个10，这个时候我们已经可以创建一个长度为10的整型数组了，再想，我们现在要实现的是栈，底层也就是往数组存取数据，比如往数组中放一个元素，栈中的元素是不是就多了一个数据，这里的size是表示数组的长度，那怎么表示栈中的元素呢？
想一想，本身栈是空的吧，也就是一开始还没有数据入栈的时候，栈是空的，然后入栈数据就多了一个，出栈数据就减少了一个，想到了吗😁，这里是不是可以搞个计数，比如定一个整型变量来表示栈中的数据，入栈就加一，出栈就减一，那好我们定义一个：
int count;
你又要想了，那空栈怎么表示呢？你说，空栈不就是数据元素是0个嘛，可以，我们可以默认count一开始为0，表示是空栈。
栈顶指针很关键😎
接着我们再看栈的一个特点，就是只能在栈顶玩耍，也就是说啊，我们操作栈实际上操作的就是栈顶的那个元素，那我们是不是可以弄个啥，专门来代表这个栈顶元素呢？
这里一般的实现思路是搞个栈顶指针，实时指向栈顶，一般叫做top，栈顶可不就是top嘛，人家是这样的：
private int top; //栈顶指针
你看到这跟之前那个count是不是一样啊，这里可有点不一样，哪里不一样呢？count代表的是栈的元素多少，这个top可代表一个栈顶指针啊，其实这个指针也并不是真正意义上的指针，count我们把它默认为0代表空栈，那这个top怎么来代表空栈呢？还是0？显然不可能。
那是多少😅，考虑到要实时指向栈顶，向下，比如我们入栈第一个元素，也就是往数组放入第一个元素，那位置肯定是a[0]啊，这个时候a[0]就代表栈顶元素啊， 再入栈一个就放在了a[1]的位置上了，那么这个top怎么指向呢？
继续思考，top要想实时指向，肯定要随着入栈和出栈做移动，怎么表示这个移动呢？最简单的不就是做加一减一的操作吗😀，那默认值是多少嘞，想下，是不是搞成-1比较靠谱。
为啥事-1，此时-1代表空栈，入栈一个元素top加上一变成了0，此时的元素不久恰好放在了a[0]的位置上了嘛，咋样，懂了吧。
这样一来，top的值就和栈顶元素在数组中的位置时一样的，可不就是实时指向嘛，看图，首先时空栈
然后入栈一个元素，top+1
咋样，知道了吧，于是乎我们创建一个栈就可以通过构造函数这样来：
//调用无参构造函数创建一个默认长度为10的数组
public StackArray(){
a = new int[size];
top = -1; //栈空的时候
}
入栈原来是这么回事😊
那我们再想，怎么表示栈顶元素呢？看图，很简单的，是不是就是a[top]，那么入栈的话，是不是top加一，然后通过a[top]指向这个栈顶元素。
这里一定要记住的就是top的值和栈顶元素在数组中存的位置是一样的
所以入栈其实也就是top加一之后拿到这个元素应该在的位置，然后把数据放到数组中，这其实就是栈的入栈操作啊，代码大致时这样：
//入栈，往数组中存放元素
public void push(int element){
//判断栈是否已满
if(top == size-1){
throw new StackOverflowError();
}
else {
a[++top] = element;
}
}
出栈也不过如此😂
那再想想出栈嘞，出栈时怎么一回事嘞，我们再看个图：
比如这里入栈了两个元素，如果我们要出栈，那就是把2给出栈，那么自然1又变成了栈顶元素，所以top应该指向它，做法就是指向2的top减一就行了。
想想是不是😀，也就是变成现在这个样子了
所以出栈啊，就是使用top减一来模拟的。
这里就有个疑问了，这里虽然top减一，代表此时栈顶元素时1，那么这个2是不是还在啊😂
对了，这里实际上2依然还是在数组上的，只不过暴露给外界知道的是此时栈顶元素是1，理想状态2已经被干掉了，然后你再想，如果再次入栈，是不是top又指向2的位置，然后来个新值给他覆盖掉了，明白了吧😊
所以出栈的代码大致如下：
//出栈
public int pop(){
//判断栈是否为空栈
if(top == -1){
throw new EmptyStackException();
}
return a[top--];
}
注意a[top–]是先计算a[top]然后top再自减
精华总结🥰
以上就是关于使用数组创建栈的一些实现思路了，这里有一些注意点：
好了，以上大致就是本文的全部内容了，关于栈的链式实现以及队列的实现，以后我们搞代码的时候单独说。今天就先到这，如果觉得本文不错，可以转发分享或者点赞支持一下哦😘
让我知道你在看
原文始发于微信公众号（编码之外）：轻轻松松学会栈和队列（附有顺序栈的实现思路分析）
