栈和队列

是什么

栈和队列是2种重要的线性结构。

• 从数据结构看，栈和队列也是线性表，其特殊性在于它们的操作受限，可以当成操作受限的线性表。
• 从数据类型看，它们是和线性表大不相同的2类重要的抽象数据类型。在面向对象的程序设计中，它们是多型数据类型。

栈的定义和常用方法的实现

• 栈（Stack）是限定仅在表尾进行插入或者删除操作的线性表。通常，表尾端称为栈顶（top）,表头称为栈底（bottom）;不包含元素的空表称为空栈。
• 栈的修改是按“后进先出”的原则进行的
• 栈的存储结构
  • 顺序存储结构
  • 链式存储结构

顺序栈（顺序存储结构）

• 是利用一组连续的存储单元一次存放自栈底到栈顶的数据元素，同时设定指针top指示栈顶的数据元素，同时设定指针top指示栈顶元素的位置。空栈的栈顶指定值为NULL，

实现顺序栈的常见操作

• Inistack(stack),初始化话一个线性堆栈，即可返回一个Javascript数组声明。

function Inistack(stack) {
  stack = new Array();
  return stack;
}

• Empty(stack),判断线性堆栈是否为空。

function Empty(stack) {
  var returnValue = false;
  if (stack.length == 0) returnValue = true;
  return returnValue;
}

• Push(stack, x),压入栈操作,将x元素追加放到存储线性堆栈的数组的最后。

function Push(stack,x){
  var returnValue = 0;
  var stackLength = stack.length;
  stack[stackLength] = x;
  return stackLength;
}

• Pop(stack),弹出栈操作。即将存储线性堆栈的数组的最后一个元素值返回，并将数组长度减1.

// 弹出线性堆栈操作
function Pop() {
  var returnValue = null;
  var stackLength = stack.length;
  if(stackLength >= 1) {
    returnValue = stack[stackLength-1];
    stack.length = stackLength - 1;  // 减少元素个数
  }
  return returnValue;
}

• Gettop(stack),获取栈顶元素的值，即将存储线性堆栈的数组的最后一个元素值返回即可

function Gettop() {
  var returnValue = null;
  var stackLength = stack.length;
  returnValue = stack[stackLength-1];
  return returnValue;
}

• Clear(stack),清空线性堆栈操作。即将存储线性堆栈的数组的长度设置为0即可

// 清空线性堆栈
function Clear(stack) {
  stack.length = 0;
  return true;
}

• Current_size(stack),获得线性堆栈的当前大小。即将存储线性堆栈的数组的长度返回即可

function Current_size(stack) {
  return stack.length;
}

范例

假设要做一个文本录入程序，为了使程序简单，我们规定程序只能输入26个字母，还能使用回退键删除一个字母。例如，在键盘上输入如下字符序列： "chii<nai<",其中<表示回退键，最后输出的应该是"china"。为此需要设置一个线性栈来保存从键盘上录入的信息。每当从键盘上录入一个非回退键时，就将该字符串压入堆栈，如果从键盘上输入一个回车键，则从堆栈中弹出一个字符。最后在线性堆栈中的就是所需要录入的正确信息。

var input_stack = new Array();
function key_input(event, stack) {
  if(((event.keyCode>=65)&&(event.keyCode<=90))  || (event.keyCode==8)) {
    if(event.keyCode == 8) {
      Pop(stack);
    } else {
      Push(stack, keyCode2Char(event.keyCode));
    }
}
  printStack(stack);
}

// 打印一个线性堆栈的值
function printStack(stack) {
  var printMsg = "";
  for(var i = 0; i < stack.length; i++) {
    printMsg = printMsg + "' " + stack[i] + " , ";
  }
  alert(printMsg);
}

// 将keyCode转换为字符的函数
function keyCode2Char(keycode) {
  var charArray = "a, b , c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z".split(", ");
  return charArray[keyCode-65];
}