栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

遵循先进后出原则

栈.png

顺序存储栈

物理结构是顺序存储，先开辟一块内存空间，每push一个新元素，栈顶标记top+1，直到开辟的空间被存满。每Pop一个栈顶元素，top-1，下一个元素变成栈顶元素。

1. 结构定义

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

/* 顺序栈结构 */
typedef struct
{
    ElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}Stack;

2. 代码实现

初始化一个空栈

Status InitStack(Stack *S)
{
    S->top = -1;
    return OK;
}

清空栈（置空）

Status ClearStack(Stack *S)
{
    S->top = -1;
    return OK;
}

判断栈是否为空

Status StackIsEmpty(Stack S) {
    if (S.top == -1) return TRUE;
    else return FALSE;
}

栈的长度

int StackLength(Stack S) {
    return S.top + 1;
}

获取栈顶元素

Status GetStackTop(Stack S, ElemType *e) {
    if (S.top == -1) return ERROR;
    else *e = S.data[S.top];
    return OK;
}

进栈

Status Push(Stack *S, ElemType e) {
    if (!S || S->top == MAXSIZE -1) return ERROR;
    S->data[++S->top] = e;
    return OK;
}

出栈

Status Pop(Stack *S, ElemType *e) {
    if (!S || S->top == -1) return ERROR;
    *e = S->data[S->top--];
    return OK;
}

遍历栈

Status StackTraverse(Stack S){
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

链式存储栈

以链表的形式，新入栈的结点，next 指向原来的栈顶结点，插在链表的最前端，成为新的栈顶。用 top 标记栈顶结点，而不是上面顺序存储的位置，每一次入栈新结点，top 指向新栈顶结点，count 也随之 +1。出栈时，top 指向栈顶结点的 next 结点，count - 1。

1. 结构定义

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

/* 链栈的每一个结点 */
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
}StackNode;

typedef struct StackNode * StackNodePtr;

/* 栈结构 */
typedef struct {
    StackNodePtr top;
    int count;
}LinkStack;

2. 代码实现

初始化一个空栈

Status InitStack(LinkStack *S) {
    S->top = NULL;
    S->count = 0;
    return OK;
}

把链栈置为空栈

Status ClearStack(LinkStack *S) {
    if (S->top == NULL) return ERROR;
    
    StackNodePtr p;
    while (S->count != 0) {
        p = S->top;
        S->top = S->top->next;
        free(p);
        S->count--;
    }
     return OK;
}

获取栈顶元素

Status GetTop(LinkStack S, ElemType *e) {
    if (S.top == NULL) return ERROR;
    *e = S.top->data;
    return OK;
}

获取栈的长度

int StackLength(LinkStack S) {
    return S.count;
}

入栈

Status PushStack(LinkStack *S, ElemType e) {
    StackNodePtr p = (StackNodePtr)malloc(sizeof(StackNode));
    if (p == NULL) return ERROR;
    
    p->data = e;
    p->next = S->top;
    S->top = p;
    S->count++;
    
    return OK;
}

出栈

Status PopStack(LinkStack *S, ElemType *e) {
    if (S->top == NULL) return ERROR;

    StackNodePtr temp = S->top;
    S->top = S->top->next;
    
    *e = temp->data;
     free(temp);
    S->count--;
    
    return OK;
}

判断一个链栈是否为空栈

Status StackIsEmpty(LinkStack S){
    if (S.count == 0) return TRUE;
    else return FALSE;
}

遍历链栈

Status StackTraverse(LinkStack S) {
    StackNodePtr p;
    p = S.top;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

递归

递归，就是运行的过程中直接或者间接的调用自己。递归的基本思想，是把规模较大的一个问题，分解成规模较小的多个子问题去解决，而每一个子问题又可以继续拆分成多个更小的子问题。

构成递归的条件

1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

下列情况下，我们一般会用递归来解决

• 定义是递归的；
• 数据结构是递归的；
• 问题的解法是递归的。

递归的缺点

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

汉诺塔问题

有 3 个分别命名为 A，B，C 的塔座，在塔座 A 上插有 n 个直径⼤小各不相同的，从⼩到大编号为 1,2,3...n 的圆盘。现在要求将塔座 A 上的 n 个圆盘移动到塔座 C 上。并仍然按照同样的顺序叠排。

圆盘移动时必须按照以下的规则：

1. 每次只能移动一个圆盘；
2. 圆盘可以插在 A，B，C 的任一塔座 上；
3. 任何时刻都不能将一个较大的圆盘压在小的圆盘之上。

解决思路

• n = 1 时，直接把盘子从 A 移动到 C 就行了。
• n > 1 时：
  • 先把 n-1 个盘子从 A 移到 B；
  • 将最大的盘子从 A 移到 C；
  • 再将 B 上 n - 1 个盘子移动到 C。

汉诺塔.png

代码实现

int m = 0;
void moves(char X, int n, char Y) {
    m++;
    printf("%d: from %c ——> %c \n", n, X, Y);
}

//n为当前盘子编号. ABC为塔盘
void Hanoi(int n, char A, char B, char C) {
    
    //目标: 将塔盘A上的圆盘按规则移动到塔盘C上,B作为辅助塔盘;
    
    //将编号为1的圆盘从A移动到C上
    if (n==1) moves(A, 1, C);
    else {
        //将塔盘A上的编号为1至n-1的圆盘移动到塔盘B上,C作为辅助塔;
        Hanoi(n - 1, A, C, B);
        //将编号为n的圆盘从A移动到C上;
        moves(A, n, C);
        //将塔盘B上的编号为1至n-1的圆盘移动到塔盘C上,A作为辅助塔;
        Hanoi(n - 1, B, A, C);
    }
}

运行结果

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hanoi 塔问题\n");
    
    
    Hanoi(3, 'A', 'B', 'C');
    printf("盘子数量为3:一共实现搬到次数:%d\n",m);
    
  
    Hanoi(4, 'A', 'B', 'C');
    printf("盘子数量为3:一共实现搬到次数:%d\n",m);
    return 0;
}

结果.png