JavaScript实现栈结构（Stack）

神月如一 發表於 2020-3-5 21:46:00

<h2 id="javascript实现栈结构stack">JavaScript实现栈结构（Stack）</h2>
<h3 id="一前言">一、前言</h3>
<h4 id="11什么是数据结构">1.1.什么是数据结构？</h4>
数据结构就是在计算机中，存储和组织数据的方式。
例如：图书管理，怎样摆放图书才能既能放很多书，也方便取？
主要需要考虑两个问题：
<ul>
<li>操作一：新书怎么插入？</li>
<li>操作二：怎么找到某本指定的书？</li>
</ul>
常见的数据结构：
<ul>
<li>数组（Aarray）</li>
<li>栈（Stack）</li>
<li>链表（Linked List）</li>
<li>图（Graph）</li>
<li>散列表（Hash）</li>
<li>队列（Queue）</li>
<li>树（Tree）</li>
<li>堆（Heap）</li>
</ul>
注意：数据结构与算法与语言无关，常见的编程语言都有直接或间接的使用上述常见的数据结构。
<h4 id="12什么是算法">1.2.什么是算法？</h4>
算法（Algorithm）的定义
<ul>
<li>一个有限指令集，每条指令的描述不依赖于语言；</li>
<li>接收一些输入（有些情况下不需要输入）；</li>
<li>产生输入；</li>
<li>一定在有限步骤之后终止；</li>
</ul>
算法通俗理解：解决问题的办法/步骤逻辑。数据结构的实现，离不开算法。
<h3 id="二栈结构stack">二、栈结构（Stack）</h3>
<h4 id="21简介">2.1.简介</h4>
数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。而栈和队列就是比较常见的受限的线性结构。如下图所示：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%88/1.png" alt="image-20200226131817102" loading="lazy">
栈的特点为先进后出，后进先出（LIFO：last in first out）。
程序中的栈结构：
<ul>
<li>
函数调用栈：A（B（C（D（））））：即A函数中调用B，B调用C，C调用D；在A执行的过程中会将A压入栈，随后B执行时B也被压入栈，函数C和D执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D（栈顶）；函数D执行完之后，会弹出栈被释放，弹出栈的顺序为D->C->B->A;
</li>
<li>
递归：为什么没有停止条件的递归会造成栈溢出？比如函数A为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数A压入栈，最后造成栈溢出（Stack Overfloat）
</li>
</ul>
3.练习：题目：有6个元素6，5，4，3，2，1按顺序进栈，问下列哪一个不是合法的出栈顺序？
<ul>
<li>A：5 4 3 6 1 2 （√）</li>
<li>B：4 5 3 2 1 6 （√）</li>
<li>C：3 4 6 5 2 1 （×）</li>
<li>D：2 3 4 1 5 6 （√）</li>
</ul>
题目所说的按顺序进栈指的不是一次性全部进栈，而是有进有出，进栈顺序为6 -> 5 -> 4 -> 3 -> 2 -> 1。
解析：
<ul>
<li>A答案：65进栈，5出栈，4进栈出栈，3进栈出栈，6出栈，21进栈，1出栈，2出栈（整体入栈顺序符合654321）;</li>
<li>B答案：654进栈，4出栈，5出栈，3进栈出栈，2进栈出栈，1进栈出栈，6出栈（整体的入栈顺序符合654321）;</li>
<li>C答案：6543进栈，3出栈，4出栈，之后应该5出栈而不是6，所以错误；</li>
<li>D答案：65432进栈，2出栈，3出栈，4出栈，1进栈出栈，5出栈，6出栈。符合入栈顺序；</li>
</ul>
栈常见的操作：
<ul>
<li>push（element）：添加一个新元素到栈顶位置；</li>
<li>pop（）：移除栈顶的元素，同时返回被移除的元素；</li>
<li>peek（）：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）；</li>
<li>isEmpty（）：如果栈里没有任何元素就返回true，否则返回false；</li>
<li>size（）：返回栈里的元素个数。这个方法和数组的length属性类似；</li>
<li>toString（）：将栈结构的内容以字符串的形式返回。</li>
</ul>
<h4 id="22封装栈类">2.2.封装栈类</h4>
代码实现：
<pre><code> // 封装栈类
function Stack(){
 // 栈中的属性
 this.items =[]

 // 栈的相关操作
 // 1.push():将元素压入栈
 //方式一(不推荐)：给对象添加方法，其他对象不能复用
 // this.push = () => {
 // }

 //方式二(推荐)：给Stack类添加方法，能够多对象复用
 Stack.prototype.push = function(element) {
 // 利用数组item的push方法实现Stack类的pop方法
 this.items.push(element)
 }

 // 2.pop():从栈中取出元素
 Stack.prototype.pop = () => {
 // 利用数组item的pop方法实现Stack类的pop方法
 return this.items.pop()
 }

 // 3.peek():查看一下栈顶元素
 Stack.prototype.peek = () => {
 return this.items
 }

 // 4.isEmpty():判断栈是否为空
 Stack.prototype.isEmpty = () => {
 // 两个小时的教训啊不是this.length(不是Stack对象的length，Stack类没有length属性啊)，而是 Stack类中定义的数组items才有length属性呀
 return this.items.length == 0
 }

 // 5.size():获取栈中元素的个数
 Stack.prototype.size = () => {
 return this.items.length
 }

 // 6.toString():以字符串形式输出栈内数据
 Stack.prototype.toString = () => {
 //希望输出的形式：20 10 12 8 7
 let resultString = ''
 for (let i of this.items){
 resultString += i + ' '
 }
 return resultString
 }
}
</code></pre>
测试代码：
<pre><code> // 栈的使用
lets = new Stack()
s.push(20)
s.push(10)
s.push(100)
s.push(77)
console.log(s) //65

console.log(s.pop()); //68
console.log(s.pop()); //69

console.log(s.peek()); //71
console.log(s.isEmpty()); //72

console.log(s.size()); //74
console.log(s.toString()); //75
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%88/2.png" alt="image-20200305205050816" loading="lazy">
栈结构的简单应用：
利用栈结构的特点封装十进至转换为二进至的函数：
<pre><code> //简单应用：
//封装函数：将十进制转成二进制(十转二的运算最后倒叙取余的特点符合栈'先进后出')
let dec2bin = decNumber => {
 //1.定义一个栈对象，保存余数
 varstack = new Stack()

 // 2.循环操作
 while(decNumber > 0){
 // 2.1.获取余数并放入栈中
 stack.push(decNumber % 2)
 // 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
 decNumber = Math.floor(decNumber / 2)
 }

 // 3.从栈中取出0和1
 letbinaryString = '';
 let a = stack.items.length
while(stack.items.length != 0){
 binaryString += stack.pop();
 }
 return binaryString;
}

//测试代码
console.log(dec2bin(10)); //103
console.log(dec2bin(100)); //104
console.log(dec2bin(1000)); //105
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%88/3.png" alt="image-20200305205547226" loading="lazy">
<blockquote>
参考资料:JavaScript数据结构与算法
</blockquote>

</div>
<div id="MySignature" role="contentinfo">
多抽出1分钟来学习，让你的生命更加精彩！ 
来源：https://www.cnblogs.com/AhuntSun-blog/p/12422941.html

頁: [1]

琼殿技术论坛's Archiver

JavaScript实现栈结构（Stack）