栈
栈的定义
1.栈是一种限定性线性表，将线性表的插入和删除限制为仅在表的一端进行，表中允许插入删除操作的一端称为栈顶，因此栈顶的当前位置是动态变化的，由一个位置指示器（栈顶指针）来指示。

2.栈是后进先出的线性表，简称为LIFO表。生活中后进先出的例子：子弹夹中子弹。
栈的表示和实现
1.顺序栈

#define STACKSIZE 50

struct SeqStack

{

int elem[STACKSIZE];

int top;

};

//初始化顺序栈

void InitStack(SeqStack *s)

{

s->top=-1; //top=-1表示空栈

}

//入栈

void Push(SeqStack *s,int x)

{

s->top++;     //修改栈顶指针

s->elem[s->top]=x;//x进栈

}

//出栈

void Pop(SeqStack *s,int *x)

{

*x=s->elem[s->top]; //将栈顶元素赋值给x

s->top–;//修改栈顶指针

}

//判断栈空

int StackEmpty(SeqStack s)

{

if(s.top==-1)

{

return 1;

}

return 0;

}

2.链栈

struct LinkStackNode

{

char data;

LinkStackNode *next;

};

typedef LinkStackNode *LStack;

//初始化顺序栈

void InitStack(Stack *s)

{

*s=new LinkStackNode;

(*s)->next=NULL;

}

//入栈

void Push(LStack s,int e)

{

LinkStackNode *temp;

temp=new LinkStackNode;

temp->data=e;

temp->next=s->next;

s->next=temp;

}

//出栈

void Pop(LStack s,int *ch)

{

*ch=s->next->data;

s->next=s->next->next;

}

//判断栈空

bool StackEmpty(LStack s)

{

if(s->next==NULL)

{

return true;

}

return false;

}

栈的应用举例
1.括号匹配

2.表达式求值
栈与递归的实现
1.递归是指定义自身的同时又出现了对自身的引用。

2.递归问题需要有：

（1）基值的判断，循环终止的条件

（2）递归调用函数

（3）调用后的返回处理

3.一些本身具有固有递归特性的数据结构：广义表，二叉树，树，快速排序法，图的深度优先搜索

4.使用递归算法的前提

（1）原问题可以分解成子问题，且子问题规模更小

（2）规模最小的子问题有直接解

5.设计递归算法的原则

（1）寻找分解算法：原问题转换为子问题 eg：n!=n(n-1)!

（2）设计递归出口：用规模最小的子问题确定循环终止的条件 eg：求n!， n=1时，n!=1

6.递归算法的特性

（1）分而治之，复杂问题简单化

（2）效率低（原因：递归执行时需要系统提供隐式栈来实现）

7.消除递归的方法

（1）简单递归问题：用循环结构的算法代替单向递归和尾递归

单向递归：递归函数虽有一处以上递归调用语句，但各次递归调用语句的参数只和主调函数有关，相互之间参数无关，且这些递归调用语句处于算法最后。

（2）基于栈的方式：将递归中隐含的栈结构转换为用户直接控制的明显的栈

8.有递归特性的问题

（1）斐波那契数列

（2）Ack函数

（3）n的阶乘

（4）汉诺塔问题

本文索引
1、什么是栈
2、栈的特点
3、栈的操作
4、栈的实现
4.1、顺序栈
4.2、链表栈

1、什么是栈
我们用一种最简单的生活常识描述一下，比如我们往柜子里放东西，先放的东西是需要放到柜子最里边，后放的东西在柜子的最外边；如果我们要取东西，先要取柜子最外边的东西，才能取到柜子最里边的东西。这种先进后出，后进先出的结构称为“栈”。


2、栈的特点
“先进后出，后进先出”
3、栈的操作
栈的操作就两种，分别为出栈和入栈。那我们上边的例子，我们往柜子里放东西的过程称为入栈；我们在柜子里拿东西的过程称为出栈。
注意：柜子只有一个出口和入口，而且出口和入口是一样的。如果两端都有开口，就变成了队列
4、栈的实现
栈的实现主要有两种，一种是数组的实现，叫做顺序栈，另外一种是链表的实现，叫做链式栈
4.1、顺序栈

基于数组的顺序栈
public class ArrayStack {
   private String[] items;  // 数组
   private int count;       // 栈中元素个数
   private int n;           // 栈的大小

   // 初始化数组，申请一个大小为 n 的数组空间
   public ArrayStack(int n) {
     this.items = new String[n];
     this.n = n;
     this.count = 0;
   }

   /**
    * 功能:入栈
    * 说明:数组入栈的入口为数组尾部
    * @param item :入栈数据元素
    * @return:是否入栈成功
    */
   public boolean push(String item) {
     // 数组空间不够了，直接返回 false，入栈失败。
     if (count == n) return false;
     // 将 item 放到下标为 count 的位置
     items[count] = item;
     //数组长度+1
     ++count;
     //入栈成功
     return true;
   }

   /**
    * 功能:出栈
    * @return:返回出栈元素
    */
   public String pop() {
     // 栈为空，则直接返回 null
     if (count == 0) return null;
     // 返回下标为 count-1 的数组元素
     String tmp = items[count-1];
     //数组长度-1
     --count;
     //返回出栈数据元素
     return tmp;
   }
 }

4.2、链表栈

/**
 * 功能:基本链表实现栈，入栈、出栈、输出栈
 * @author : 小鹿
 *
 */
 6public class StackBasedLinkedList {
    //定义栈顶指针
    private Node top = null;

    //定义栈结点
    private static class Node {
        //栈结点数据域
        private int data;
        //栈结点指针域
        private Node next;
        //构造函数
        public Node(int data, Node next) {
          this.data = data;
          this.next = next;
        }
        //get 获取数据域方法
        public int getData() {
          return data;
        }
    }

    /**
     * 功能:入栈
     * @param value:要入栈的数据元素
     */
    public void push(int value) {
        //创建一个栈结点 
        Node newNode = new Node(value, null);
        // 判断栈是否为空
        if (top == null) {
          //如果栈为空，就将入栈的值作为栈的第一个元素
          top = newNode;
        } else {
          //否则插入到top栈结点前（所谓的就是单链表的头插法）
          newNode.next = top;
          top = newNode;
        }
    }

    /**
     * 功能 : 出栈
     * @return: -1 为栈中没有数据
     */
    public int pop() {
        // 如果栈的最顶层栈结点为null,栈为空
        if (top == null) return -1;

        //否则执行出栈操作，现将栈顶结点的数据元素赋值给 Value
        int value = top.data;
        //将 top 指针向下移动
        top = top.next;
        //返回出栈的值
        return value;
    }   

    /**
     * 功能:输出栈中所有元素
     */
    public void printAll() {
        //将栈顶指针赋值给p
        Node p = top;
        //循环遍历栈(遍历单链表)
        while (p != null) {
          System.out.print(p.data + " ");
          //指向下一个结点
          p = p.next;
        }
        System.out.println();
    }
}

根据“后进先出”特性，生活中的例子比比皆是。

1数制转换


假设要讲十进制转换为二进制。以 52 为例，如图：


在上述计算过程中，第一次求出的X值为最低位，最后一次求出的X值为最高位。而打印时应从高位到低位进行，恰好与计算过程相反。根据这个特点，我们可以通过入栈出栈来实现，即将计算过程中依次得到的二进制数码按顺序进栈，计算结束后，再顺序出栈，并按出栈顺序打印输出。即可得到给定的二进制数。这是利用栈后进先出特性的最简单例子。

void Conversion(int N){
    /*对于任意的一个非负十进制数N，打印出与其对应的二进制数*/
    Stack S;
    int x;
    InitStack(&S);
    while (N>0) {
        x=N%2;
        Push(&S,x); //将余数压入栈S
        N=N/2;
    }
    while (!IsEmpty(&S)) {
        Pop(&S,&X);
        printf("%d",x);
    }
}


2括号匹配问题


假设表达式有三种括号：圆括号“（）”，花括号“｛｝”，方括号“［］”。它们可互相嵌套，如｛（［］）｝或｛（［］）（）［］｝均为正确格式。而｛）），｛［（）］均为不正确格式。如何检测其正确性？可以应用栈。
我们以“｛［（）］｝”为例，依次读取括号，如图：


注意，上面写的双双出栈其实是，左括号出栈。

void BrackerMatch(char *str){
    Stack S;
    int i;
    char ch;
    InitStack(&S);
    for (i=0;str[i]!='/0';i++)
    {
        switch (str[i]) {
            case '(':
            case '[':
            case '{':
                Push(&S,str[i]);
                break;
            case ']':
            case '}':
            case ')':
                if (IsEmpty(&S)) {
                    printf("\n 右括号多余！");
                    return;
                }else{
                    GetTop(&S,&ch);
                    if(Match(ch,str[i])) //用 Match 判断两个括号是否匹配
                        Pop(&S,&ch);     //已匹配的左括号出栈
                    else{
                        printf("\n对应的左右括号不同类");
                        return;
                    }
                }
            default:
                break;
        }
        if (IsEmpty(&S))
            printf("\n括号匹配！");
        else
            printf("\n左括号多余！");
    }
}


3表达式求值


表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。
1+2*3/(1+5)=2
任何一个表达式都是由数（操作数）和符号（运算符＋－＊／，界限符（））组成。
而符号又有优先级，优先计算得到的值再作为数继续运算，当符号用尽后，值即为所得。


1+2*3/(1+5)   -->   1+6/(1+5)   -->   1+6/6   -->   1+1   -->   2

优先级规则：
（1）先左后右
（2）先乘除，后加减
（3）先括号内，后括号外

此时需要两个栈，一个称作operator，用以存放符号。一个称作operand，用于存放操作数或中间结果。下图，为即将要用到的算符之间的优先关系。


算法的基本过程如下：
初始化两个栈，然后讲表达式起始符“＃”压入operator栈。
输入表达式，以“＃”结尾。
依次读取表达式，读取过程中，若是操作数，直接入栈operand。若是符号，则与operator栈顶运算符进行比较。
（1）若 栈顶符<刚读运算符 ： 刚读运算符 进栈；
（2）若 栈顶符>刚读运算符 ： 进行计算，operator栈顶符退栈，送入x，同时将operand栈退栈两次，得到a，b，对a，b，x进行运算后，将结果作为中间结果推入operand栈；
（3）若 栈顶符=刚读运算符 ： 说明是左右括号相遇，栈顶符退栈即可；
当operator栈的栈顶符和当前符都为“＃”时，说明求值完毕。
以(10+2)*3# 为例，如图：


当栈顶符和当前符都是“＃”，计算结束

int ExpEvaluation(){
    /*operator为符栈，operand为数栈，OPS为运算符集合*/
    InitStack(&operand);
    InitStack(&operator);
    Push(&operator,'#');
    printf("\n输入一个表达式（以＃结束）");
    ch=getchar();
    while(ch!='#'||GetTop(operator)!='#'){ //GetTop 取栈顶
        if (!In(ch,OPS)) {                  //不是操作符，是操作数
            int temp;
            temp=ch-'0';                //数的临时变量，并转换为十进制
            ch=getchar();
            while (!In(ch,OPS)) {        //数可能不只有一位，如100就要读三次
                temp=temp+10+ch-'0';
                ch=getchar();
            }
            Push(&operand,temp);
        }
        else
            switch (Compare(GetTop(operator),ch)) {
                case '<':
                    Push(&operator,ch);
                    ch=getchar();
                    break;
                case '=':
                    Pop(&operator,&x);
                    ch=getchar();
                    break;
                case '>':
                    Pop(&operator,&op);
                    Pop(&operand,&b);
                    Pop(&operand,&a);
                    v=Execute(a,op,b);   //对a和b进行op运算
                    Push(&operand,v);    //注意这里没有 ch=getchar()
                    break;
            }
    }
    v=GetTop(&operand);
    return v;
}



以上均为学习耿国华的《数据结构－c语言》笔记

栈

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈顶。

现实生活中就有很多栈的例子。如下图的书本，这一摞书如果要取肯定是先去最上面的那一本，但它是最后一个放上去的，也就是栈顶的元素都是待添加或是待删除的。这就是后进先出的实际例子。

 



栈的创建：

我们创建一个类来表示栈。先声明：

function Stack() {

  //各种属性和方法的声明

}

然后我们需要一种数据结构来保存栈里的元素：

var items = [];

接下来，我们给栈声明一些方法：

push(element)：添加一个或几个新元素到栈顶
	
pop()：移除栈顶的元素，同时返回被移除的元素
	
peek()：返回栈顶的元素，不对栈做任何修改
	
isEmpty()：判断栈里有无元素
	
clear()：移除栈里的所有元素
	
size()：返回栈里的元素个数。和数组length属性类似。
我们利用这些方法来实现一个栈：

function Stack() {
    var items = [];
    this.push = function(element) {
        items.push(element);
    }
    
    this.pop = function() {
        return items.pop();
    }

    this.peek = function() {
        return items[items.length - 1];
    }

    this.isEmpty = function() {
        return items.length === 0;
    }

    this.size = function() {
        return items.length;
    }

    this.clear = function() {
        items = [];
    }

    this.print = function() {
        console.log(items.toString());
    }
}

我们来测试下：

var stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8 
stack.push(11); 
console.log(stack.size()); // 3 
stack.pop(); 
console.log(stack.size()); // 2 
stack.print(); // 5,8

参考链接： 学习JavaScript数据结构与算法