手动实现数据结构-栈结构

1.栈结构

• 是一种受限的线性结构。

• 特点：先进后出

2.使用TS实现

 1 //封装一个栈  使用泛型类
 2 class ArrayStack<T=any>{//给一个默认值为any类型
 3 //定义一个数组，用于存储元素
 4 private data:T[]=[]
 5 //push:将元素压入栈中
 6 push(e:T):void{
 7   this.data.push(e)
 8 }
 9 //pop方法：将栈顶的元素弹出栈(返回出去并从栈顶移除)   
10 pop():T|undefined{
11   return this.data.pop()//pop返回的是删除的元素
12 }
13 //peek方法：看一眼栈顶元素
14 peek():T|undefined{
15   return this.data[this.data.length-1]
16 }
17 //isEmpty
18 isEmpty():boolean{
19   return this.data.length===0
20 }
21 size():number{
22   return this.data.length
23 }
24 }

3.使用JS实现

 1 // 栈类
 2     function Stack() {
 3         // 栈中的属性
 4         var items = []
 5 
 6         // 栈相关的方法
 7         // 压栈操作
 8         this.push = function (element) {
 9             items.push(element)
10         }
11         // 出栈操作
12         this.pop = function () {
13             return items.pop()
14         }
15         // peek操作
16         this.peek = function () {
17             return items[items.length - 1]
18         }
19         // 判断栈中的元素是否为空
20         this.isEmpty = function () {
21             return items.length == 0
22         }
23         // 获取栈中元素的个数
24         this.size = function () {
25             return items.length
26         }
27     }

4.相关题目

4.1 十进制转二进制

 1 function decToBinary(decimal:number):string{
 2   let stack=new ArrayStack<number>()
 3   
 4   //while:不知道循环次数，知道循环终止条件。for：知道循环次数
 5   while(decimal>0){
 6     let result=decimal%2
 7     stack.push(result)
 8     decimal=Math.floor(decimal/2)
 9   }
10   let str=''
11   while(!stack.isEmpty()){
12     str+=stack.pop()
13   }
14   return str
15 }

4.2有效的括号

 1 function isVaild(str:string):boolean{
 2   //创建一个栈结构 用于把存放右括号
 3   let stack=new ArrayStack()
 4   //遍历字符串中每一个字符，当遇到一个左括号就往栈里面添加对应的右括号。当遇到右括号时，就能让它与栈弹出的元素（刚添加进去的）比较，如果不相等，就说明没有成对出现。重要的就是一一对应（相应的左括号对应相应的右括号）。
 5   for(let i=0;i<str.length;i++){
 6     let item=str[i]
 7     switch(item){
 8       case '(':
 9         stack.push(')')
10         break;
11       case '{':
12         stack.push('}')
13         break;
14       case '[':
15         stack.push(']')
16         break;
17       default:
18         if(item!==stack.pop())return false
19         break;
20     }
21   }
22   //只有栈为空的时候，表明括号既一一对应又是双数
23   return stack.isEmpty()
24 
25 }