2022-09-22
一、栈概述 Overview
1. 栈的定义
. 限定操作的线性表：只能在线性表的一端操作
. 运行操作的一端是栈顶top，另外一端为栈底bottom/base；[约定]a0为栈底；ai-1为栈顶
. 不包含任何元素的栈是空栈
2. 栈的特点
操作：遵循后进先出的原则：LIFO-last in first out
数据进来：入栈、压栈、进栈
数据出去：退栈、弹栈、出栈
应用：临时保存数据，如函数调用、浏览器访问的前进和后退、文档编辑时的撤销、弹匣、汉诺塔等
3. 栈的抽象数据类型ADT
. 数据对象
D={ ai | ai∈Set, i=0,1,2,...,n-1}
. 数据关系：
R={<ai, ai+1> | ai,ai+1∈Set, i=0,1,2,...,n-2}
. 数据运算
Init(&stack) 初始化
Clear(&stack) 清空
Destroy(&stack) 销毁
isEmpty(&stack) 是否为空
Length(&stack) 栈长度
Push(&stack, data) 入栈
Pop(&stack, &data) 出栈
Top(&stack, &el) 取栈顶
Display(&stack) 遍历
[Section End]
二、顺序栈 Sequence Stack
1. 顺序栈的数据结构
. 使用一组地址连续的存储单元依次存放自栈底到栈顶的元素
. top：指向栈顶元素的上一个位置
. base：指向栈底；如果base为空，则栈不存在
. top和base相同时，栈为空
. size：栈的最大可用容量
//使用动态数组
typedef struct Stack{
    Elemtype *top;
    Elemtype *base;
    int size; 
}Stack;

//使用静态数组的实现，请参考[3. 顺序栈的参考代码]
2. 顺序栈的基本操作
2.1 初始化：栈顶top和栈底base相同
void Init(Stack *s)
{
    s->base = (Elemtype *)malloc(sizeof(Elemtype) * MaxSize);
    if (!s->base)
        exit(0);
    s->top = s->base;
    s->size = MaxSize;
}
2.2 入栈：A入栈
Status Push(Stack *s, Elemtype data)
{
    // Stack Full
    if (s->top - s->base >= s->size)
        exit(0);
    *(s->top) = data;
    s->top++;
    return OK;
}
2.3 出栈：C出栈，栈顶top下移
Status Pop(Stack *s, Elemtype *data)
{
    // Stack Empty
    if (s->top == s->base)
        return ERROR;
    //*e = *--(s->top);
    s->top--;
    *data = *(s->top);
    return OK;
}
2.4 取栈顶：获取B，栈顶top不变
Status Top(Stack *s, Elemtype *data)
{
    if (s->top > s->base)
    {
        *data = *(s->top - 1);
        return OK;
    }
    return ERROR;
}
2.5 栈的长度
Status Length(Stack *s)
{
    return s->top - s->base;
}
2.6 是否为空
Status IsEmpty(Stack *s)
{
    return (s->base == s->top) ? OK : ERROR;
}
2.7 清空栈
void Clear(Stack *s)
{
    s->top = s->base;
}
2.8 销毁栈
void Destroy(Stack *s)
    {
    if (s != NULL)
    {
        free(s->base);
        s->top = s->base = NULL;
        s->size = 0;
    }
}
2.9 遍历栈
当p不等于top时，将p地址处的值输出；p++
[]可以使用top或base遍历栈吗？
void Display(Stack *s)
{
    int i = 0;
    int len=Length(s);
    int *p=s->base;
    if (!len)
        return;
    while (i < len)
    {
        printf("%d->", *p);
        i++;
        p++;
    }
    printf("NULL\n");
}
3. 顺序栈的参考代码
//动态数组
#include <stdio.h>
#include <stdlib.h>
    
#define ERROR 0
#define OK 1

#define MaxSize 10

typedef int Status;
typedef int Elemtype;

typedef struct Stack
{
    Elemtype *top;
    Elemtype *base;
    int size;
} Stack;

void Init(Stack *s)
{
    s->base = (Elemtype *)malloc(sizeof(Elemtype) * MaxSize);
    if (!s->base)
        exit(0);
    s->top = s->base;
    printf("%p\n",s->base);
    s->size = MaxSize;
}

Status Push(Stack *s, Elemtype data)
{
    // Stack Full
    if (s->top - s->base >= s->size)
        exit(0);
    *(s->top) = data;
    s->top++;
    return OK;
}

Status Pop(Stack *s, Elemtype *data)
{
    // Stack Empty
    if (s->top == s->base)
        return ERROR;
    //*e = *--(s->top);
    s->top--;
    *data = *(s->top);
    return OK;
}

Status Top(Stack *s, Elemtype *data)
{
    if (s->top > s->base)
    {
        *data = *(s->top - 1);
        return OK;
    }
    return ERROR;
}

Status Length(Stack *s)
{
    return s->top - s->base;
}

Status IsEmpty(Stack *s)
{
    return (s->base == s->top) ? OK : ERROR;
}

void Clear(Stack *s)
{
    s->top = s->base;
}

void Destroy(Stack *s)
{
    if (s != NULL)
    {
        free(s->base);
        s->top = s->base = NULL;
        s->size = 0;
    }
}

void Display(Stack *s)
{
    int i = 0;
    int len = Length(s);
    int *p = s->base;
    if (!len)
        return;
    while (i < len)
    {
        printf("%d->", *p);
        i++;
        p++;
    }
    printf("NULL\n");
}

void DisplayAdv(Stack s, void (*visit)(Elemtype))
{
    while (IsEmpty(&s))
    {
        visit(*s.base++);
    }
}

void Dec2bin(Stack *s, int num)
{
    int i,temp,res,len;
    while (num > 0)
    {
        temp = num % 2;
        num = (int)num / 2;
        Push(s, temp);
    }
    len=Length(s);
    // WHY NOT???
    // for ( i = 0; i < Length(s); i++)
    for ( i = 0; i < len; i++)
    {
        Pop(s,&res);
        printf("%d",res);
    }    
}

int main()
{
    int i, value, length;
    Elemtype e;
    Stack *s;
    printf("%p\n",s->base);

    Init(s);
    printf("%p\n",s->base);
    for (i = 0; i < 10; i++)
        Push(s, i);
    length = Length(s);
    printf("data in stack:\n");
    Display(s);

    IsEmpty(s);
    length = Length(s);

    Pop(s, &e);
    Top(s, &e);
    printf("Top is %d, length is %d\n", e, Length(s));

    Clear(s);
    length = Length(s);

    // decimal to binary
    printf("decimal to binary---------------\n");
    printf("please input a number->");
    scanf("%d",&value);
    Dec2bin(s, value);
    Destroy(s);

    return 0;
}
//静态数组
#include <stdio.h>
#include <stdlib.h>
        
#define maxSize 10
#define TRUE 1
#define FALSE 0

typedef struct Stack
{
    int data[maxSize];
    int top;
} Stack;

Stack *Init();
int IsEmpty(Stack *s);
int Push(Stack *s, int data);
int Pop(Stack *s, int *data);
int Top(Stack *s, int *data);
void Clear(Stack *s);
void Show(Stack *s);
void Dec2bin(Stack *s, int num);

int main(void)
{
    int res;
    Stack *s = Init();
    printf("please input a number->");
    scanf("%d", &res);
    printf("Decimal number: \t%d\n", res);
    printf("Binary number: \t\t");
    Dec2bin(s, res);
    return 0;
}
Stack *Init()
{
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->top = -1;
    printf("Init done\n");
    return s;
}

int IsEmpty(Stack *s)
{
    return (s->top == -1) ? TRUE : FALSE;
}

int Push(Stack *s, int data)
{
    if (s->top == maxSize - 1)
    {
        printf("Stack Full\n");
        return FALSE;
    }
    s->data[s->top] = data;
    s->top++;
    return TRUE;
}

int Pop(Stack *s, int *data)
{
    if (s->top == -1)
    {
        printf("Stack Empty\n");
        return FALSE;
    }
    s->top--;
    *data = s->data[s->top];
    return TRUE;
}

int Top(Stack *s, int *el)
{
    if (s->top == -1)
    {
        printf("Stack Empty\n");
        return FALSE;
    }
    *el = s->data[s->top - 1];
    printf("Stack top done\n");
    return TRUE;
}

void Clear(Stack *s)
{
    s->top = -1;
}

void Show(Stack *s)
{
    int res;
    while (s->top > -1)
    {
        Pop(s, &res);
        printf("%d", res);
    }
    printf("\n");
}

void Dec2bin(Stack *s, int num)
{
    int rem;
    char *str;
    while (num > 0)
    {
        rem = num % 2;
        num = (int)num / 2;
        Push(s, rem);
    }
    Show(s);
}
[Section End]
三、链栈 Linked Stack
1. 链式栈的特点
. 不需要头结点
. 不存在栈满的情况
. top=NULL表示空栈
2. 链栈的数据结构
//不带头节点的链栈
typedef struct Node
{
    int data;
    struct Node *next;
} Node, Stack;
//带头节点的链栈
typedef struct Node
{
    int data;
    struct Node *next;
} Node;

typedef struct Stack
{
    Node *top;
    int count;
} Stack;
3. 链栈的参考代码
//不带头节点的链栈
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
} Node, Stack;

Stack *Init()
{
    Node *s = NULL;
    printf("%p\n", s);
    return s;
}

Stack *Push(Stack *s, int data)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->next = s;
    node->data = data;
    return node;
}

void pop(Stack *s, int *data)
{
    if (!s)
        return;
    *data = s->data;
    Node *node = s;
    s = s->next;
    free(node);
}

int top(Stack *s)
{
    return s ? s->data : -1;
}

Stack *Clear(Stack *s){
    Node *node=s;
    Node *tmp;
    while (node)
    {
        tmp=node;
        node=node->next;
        free(tmp);
    }
    return node;    
}

void Traverse(Stack *s)
{
    int res;
    Node *p =s;
    while (p)
    {
        res=p->data;
        printf("%d->", res);
        p=p->next;
    }
        printf("NULL\n");
}
// 10 -> 2
void Dec2bin(Stack *s, int num)
{
    int rem;
    while (num > 0)
    {
        rem = num % 2;
        s=Push(s, rem);
        num = (int)num / 2;
    }
    Traverse(s);
}

int main(void)
{
    Stack *s;
    printf("%p\n", s);
    s = Init();
    printf("%p\n", s);
    s=Push(s,1);
    s=Push(s, 11);
    s=Push(s, 2);
    s=Push(s, 3);
    s=Push(s, 10);
    Traverse(s);
    s = Clear(s);
    Dec2bin(s, 5);
    s = Clear(s);
    return 0;
}
//带头节点的链栈
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

typedef struct Stack
{
    Node *top;
    int count;
} Stack;

// 初始化栈就是创建一个结构体变量
Stack *Init()
{
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->top = NULL;
    stack->count = 0;
    printf("Stack Init done\n");
    return stack;
}
// 链表的头插法
void Push(Stack *s, int data)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = s->top;
    s->top = node;
    s->count++;
}

void Pop(Stack *s, int *res)
{
    if (!s->top)
        return;
    Node *node = s->top;
    s->top = node->next;
    s->count--;
    *res = node->data;
    free(node);
}

int Top(Stack *s, int *res)
{
    if (s->top){
        *res = s->top->data;
        return 0;
    }
    return -1;
}

void Traverse(Stack *s)
{
    Node *node = s->top;
    while (node)
    {
        printf("%d->", node->data);
        node = node->next;
    }
    printf("Null\n");
}

int isEmpty(Stack *s)
{
    return s->count ? 1 : 0;
}

void Clear(Stack *s){
    Node *node;
    while (s->top)
    {        
        node=s->top;
        s->top=node->next;
        free(node);
    }    
    s->count=0;
}

void Dec2bin(Stack *s, int num)
{
    int rem;
    while (num > 0)
    {
        rem = num % 2;
        Push(s, rem);
        num = (int)num / 2;
    }
    Traverse(s);
}

int main(void)
{
    int res;
    Stack *s = Init();
    Dec2bin(s, 9);
    Clear(s);
    isEmpty(s);
    Push(s, 1);
    Push(s, 11);
    Push(s, 2);
    Push(s, 3);
    Push(s, 10);
    Traverse(s);
    Pop(s, &res);
    Pop(s, &res);
    Traverse(s);
    Pop(s, &res);
    Traverse(s);
    Top(s, &res);
    Pop(s, &res);
    Top(s, &res);
    Pop(s, &res);
    Top(s, &res);
    return 0;
}
[Section End]
队列 Queue
1. 顺序队列参考代码
    #include <stdio.h>
    #include <stdlib.h>
    
    #define maxSize 10
    #define TRUE 1
    #define FALSE 0
    
    typedef struct
    {
        int data[maxSize];
        int rear;
        int front;
    } Queue;
    
    //地址的地址
    void initBak(Queue **q)
    {
        *q = (Queue *)malloc(sizeof(Queue));
        (*q)->front = 0;
        (*q)->rear = 0;
        printf("init inside\t%p\n", *q);
    }
    
    //返回申请的地址
    Queue *init()
    {
        Queue *q = (Queue *)malloc(sizeof(Queue));
        q->front = 0;
        q->rear = 0;
        printf("inside size of Queue\t%p\n", q);
        printf("inside size of Queue\t%ld\n", sizeof(*q));
        return q;
    }
    
    int isEmpty(Queue *q)
    {
        return q->rear == q->front;
    }
    
    //先加再入
    int enQueue(Queue *q, int data)
    {
        if ((q->rear + 1) % maxSize == q->front)
        {
            printf("Queue full\n");
            return FALSE;
        }
        //先赋值再移动
        q->data[q->rear] = data;
        q->rear = (q->rear + 1) % maxSize;
        printf("data %d enQueue OK\n",data);
        return TRUE;
    }
    
    
    void deQueue(Queue *q,int *res)
    {
        if (q->rear == q->front)
        {
            printf("Queue empty\n");
            return;
        }
        //先获取再移动
        *res=q->data[q->front];
        q->front = (q->front + 1) % maxSize;
        printf("%d deQueue OK\n",*res);
        return;
    }
    
    int length(Queue *q){
        return (q->rear-q->front) % maxSize;
    }
    
    //homework start--------------------------------------------------
    void display(Queue *q){
        int len=length(q);
        int ind=q->front;
        printf("Queue->");
        while(ind!=q->rear)
        {
            printf("%d->",q->data[ind]);
            ind++;
        }
        printf("NULL\n");
    }
    //homework end----------------------------------------------------
    
    void destroy(Queue *q)
    {
        free(q);
    }
    
    void baoshu(Queue *sq, int n)
    {
    
        int i, count = 1, e;
        //init(sq);
        for (i = 1; i <= n; i++)
            enQueue(sq, i);
    
        printf("排列后队列:");
        while (!isEmpty(sq))
        {
            deQueue(sq, &e);
            if (count % 2 == 1)
                printf("%d ", e);
            else
                enQueue(sq, e);
            count++;
        }
        printf("\n");
    }
    
    int main(void)
    {
        int i,res,len;
        Queue *q;
        printf("oustside\t%p\n", q);
        printf("outside size of Queue\t%ld\n", sizeof(*q));
        q=init();
        printf("outside init done\t%p\n", q);
        printf("outside size of Queue\t%ld\n", sizeof(*q));
        display(q);
        enQueue(q,10);
        enQueue(q,20);
        enQueue(q,30);
        printf("length of Queue %d\n",length(q));
        enQueue(q,40);
        enQueue(q,50);
        printf("length of Queue %d\n",length(q));
        enQueue(q,60);
        enQueue(q,70);
        enQueue(q,80);
        enQueue(q,90);
        printf("\n");
        display(q);
        deQueue(q,&res);
        printf("length of Queue %d\n",length(q));
        deQueue(q,&res);
        deQueue(q,&res);
        display(q);
        printf("length of Queue %d\n",length(q));
        deQueue(q,&res);
        deQueue(q,&res);
        deQueue(q,&res);
        display(q);
        deQueue(q,&res);
        deQueue(q,&res);
        deQueue(q,&res);
        deQueue(q,&res);
        display(q);
        free(q);
        printf("free\t\t%p\n", q);
        baoshu(q,5);
        return 0;
    }
2. 链式队列参考代码
    #include <stdio.h>
    #include <stdlib.h>

    #define TRUE 1
    #define FALSE 0
    
    typedef struct Node
    {
        int data;
        struct Node *next;
    } Node;
    
    typedef struct
    {
        Node *front;
        Node *rear;
        int len;
    } Queue;
    
    //地址的地址
    void initBak(Queue **q)
    {
        *q = (Queue *)malloc(sizeof(Queue));
        (*q)->front = NULL;
        (*q)->rear = NULL;
        (*q)->len = 0;
    }
    
    //返回申请的地址
    Queue *init()
    {
        Queue *q = (Queue *)malloc(sizeof(Queue));
        q->front = NULL;
        q->rear = NULL;
        q->len = 0;
        return q;
    }
    
    //没有队满的限制
    void enqueue(Queue *q, int el)
    {
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = el;
        node->next = NULL;
        // 判断是否为空
        if (!q->len)
        {
            q->front = node;
            q->rear = node;
        }
        else
        {
            q->rear->next = node;
            q->rear = node;
        }
        q->len++;
        printf("enqueue OK\n");
    }
    
    //要判断队是否为空；且删除节点时，不要忘记回收节点；
    int dequeue(Queue *q)
    {
        if (!q->len)
        {
            printf("Queue empty\n");
            return FALSE;
        }
        Node *node=q->front;
        int res = q->front->data;
        q->front = q->front->next;
        free(node);
        q->len--;
        printf("dequeue OK\n");
        return res;
    }
    
    void Top(Queue *q,int *res){
        if(!q->len){
            return;
        }
        *res=q->front->data;
    }
    
    void destroy(Queue **q)
    {
        free(*q);
    }
    
    int isEmpty(Queue *q)
    {
        //OK
        //return q->len==0;
        return q->len?0:1;
    }
    
    int len(Queue *q){
        return q->len;
    }
    
    //如果根据表长len来遍历呢
    void display(Queue *q){
        Node *p=q->front;
        printf("Queue->");
        while(p){
            printf("%d->",p->data);
            p=p->next;
        }
        printf("NULL\n");
    }
    
    int main(void)
    {
        Queue *q=init();
        display(q);
        int len = 8, res, i;
        for (i = 1; i <= len; i++)
        {
            enqueue(q, i);
        }
        display(q);
        dequeue(q);
        display(q);
        dequeue(q);
        dequeue(q);
        display(q);
        dequeue(q);
        dequeue(q);
        dequeue(q);
        dequeue(q);
        display(q);
        dequeue(q);
        display(q);
        dequeue(q);
        display(q);
        return 0;
    }
更多内容，请访问 队列
[Section End]
应用 Application
1. 递归
    // n的阶乘
    function fac(n) {
      if (n == 0) {
        return 1
      } else {
        return n * fac(n - 1)
      }
    }

    // a和b的最大公约数
    function gcd(a, b) {
      if (b == 0) {
        return a;
      } else {
        return gcd(b, a % b)
      }
    }

    // n阶台阶的走法：可以一次走1阶；也可以一次走2阶，共多少种走法？
    function steps(n) {
      switch (n) {
        case 1: return 1;
        case 2: return 2;
        default: return steps(n - 1) + steps(n - 2)
      }
    }
2. 进制转换
10进制转换为2进制：10进制除以2，将余数进栈；最后再依次出栈；
void dec2bin(Stack *s, int num)
{
    int rem;
    while (num > 0)
    {
        rem = num % 2;
        push(s, rem);
        num = (int)num / 2;
    }
    show(s);
}
3. 回文
对称串；从左到右和从右到左的次序是一样的；
void symStr(Stack *s, char *str)
{
    while (*str != '\0')
    {
        push(s, *str);
        str++;
    }
    traversal(s);
}
4. 中缀表达式和后缀表达式
5. 击鼓传花
[Section End]
拓展 Reference