1.数据结构定义
在计算机中，存储和组织数据的方式。
注：数据结构与语言无关。
1.1常见的数据结构：
数组（Aarray）栈（Stack）链表（Linked List）图（Graph）散列表（Hash）队列（Queue）树（Tree）堆（Heap）
2.算法（Algorithm）
- ? 一个有限指令集，每条指令的描述不依赖于语言
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定在有限步骤之后终止
注：数据结构的实现，离不开算法。
3.栈结构(Stack)—后进先出（LIFO）
是一种受限的线性表，仅允许在表的一端进行插入和删除运算。
? 在生活中也能发现很多栈的例子。例如，厨房里堆放的盘子，总是叠在上方的先被使用；输入框内容进行删除时，总是最后输入的先删除；弹夹中的子弹，越后装入的，越先发射…
4.实现栈结构
基于数组实现/基于链表实现
5.常见栈操作
首先创建一个类来表示栈
function Stack () { }
我们需要选择一种数据结构来保存栈里的元素，可以选择数组
function Stack(){
var items = [] //用来保存栈里的元素
}
然后给栈添加一些方法：
push(element):添加一个新元素到栈顶位置
Stack.prototype.push = function(element){
? this.items.push(element)
? }
pop():移除栈顶元素，同时返回被移除的元素
Stack.prototype.pop = function(){
? return this.items.pop()
? }
peek():返回栈顶元素，不对栈做任何修改（这个方法不会移除栈顶元素，仅仅返回它）
Stack.prototype.peek = function(){
? return this.items[this.items.length - 1]
? }
isEmpty():如果栈里没有任何元素就返回true，否则返回false
Stack.prototype.isEmpty = function(){
? return this.items.length == 0
? }
size():返回栈里的元素个数，这个方法和数组的length属性很类似
Stack.prototype.size = function(){
? return this.items.length
? }
toString():将栈结构的内容以字符形式返回
Stack.prototype.toString = function(){
? var resultSrting = ''
? for(var i = 0;i <= this.items.length;i++){
? resultSrting += this.items[i]+' '
? }
? return resultSrting
? }
栈的完整代码：
//封装栈类
? function Stack(){
? //栈中的属性
? this.items = []
? //栈的相关操作
? //将元素压入栈
? Stack.prototype.push = function(element){
? this.items.push(element)
? }
? //从栈中取出元素
? Stack.prototype.pop = function(){
? return this.items.pop()
? }
? //查看栈顶元素
? Stack.prototype.peek = function(){
? return this.items[this.items.length - 1]
? }
? //判断栈是否为空
? Stack.prototype.isEmpty = function(){
? return this.items.length == 0
? }
? //获取栈中元素个数
? Stack.prototype.size = function(){
? return this.items.length
? }
? //toString方法
? Stack.prototype.toString = function(){
? var resultSrting = ''
? for(var i = 0;i <= this.items.length;i++){
? resultSrting += this.items[i]+' '
? }
? return resultSrting
? }
}
使用Stack类
进行测试前，要初始化Stack类，然后根据所需进行测试。
//栈的使用
? var s = new Stack()
6.栈的应用
十进制转化成二进制
//函数：将十进制转换成二进制
? function dec2bin(decNumber){
? //定义栈元素
? var stack = new Stack()
? //循环操作
? while(decNumber > 0){
? //获取余数，放入栈中
? stack.push(decNumber % 2)
? //获取整除的结果，作为下一次运行的数字
? decNumber = Math.floor(decNumber / 2)
? }
? //从栈中取出0和1
? var binaryString = ''
? while(!stack.isEmpty()){
//利用pop把栈内元素逐一弹出，将余数拼接成为一个字符串
? binaryString += stack.pop()
? }
? return binaryString
? }
? //进行测试
? alert(dec2bin(100))
? //alert(dec2bin(10))
? //alert(dec2bin(1000))
修改一下算法，实现十进制转换为任意进制
//十进制转换为任意进制
? function baseConverter(decNum, base) {
? var base = (base >= 2 && base <= 16) ? base : 10
? remStack = new Stack()
? rem
? baseStr = ''
? digits = '0123456789ABCDEF'
? while(decNum) {
? rem = Math.floor(decNum % base)
? decNum = Math.floor(decNum / base)
? remStack.push(rem) //余数放到栈中
? }
? while(!remStack.isEmpty()) {
? baseStr += digits[remStack.pop()] //利用pop把栈内元素逐一弹出，将余数拼接成为一个字符串
? }
? return baseStr## 标题
? }