栈和队列

栈

定义：

一种可以实现“先进后出”的存储结构
列如：往垃圾桶里面倒垃圾，再倒出

分类：

静态栈：
动态栈：

算法：

出栈
压栈

应用：

1.函数调用
2.中断
3.表达式求值
4.内存分配
5.缓冲处理
6.迷宫

队列

定义：

一种可以实现“先进先出”的存储结构

分类：

链式队列 -- 用链表实现
静态队列-- 用数组实现
静态队列必须是循环队列

循环队列讲解：

1.静态队列为什么必须是循环队列：
如果不是循环队列，到数组末尾是会指针越界，

2.循环队列需要几个参数来确认
需要2个参数来确定
front 和rear
3.循环队列各个参数的含义
这两个参数不同场合有不同的含义
3.1队列初始化:front 和rear的值都是零
3.2队列非空：front代表的是队列的第一个元素，rear代表的是队列的最后一个有效元素的下一个元素
3.3队列空：front和rear的值相等，但不一定为零

4.循环队列入队伪算法的讲解
4.1将值存入rear所代表的位置
4.2 r = (r+1) % 数组长度。

5.循环队列出队伪算法的讲解
f = （f+1）% 数组长度
6.如何判断循环队列是否为空
如果front与rear的值相等，则队列为空
7.如何判断循环队列是否已满
7.1多增加一个标识位
7.2少用一个标识位
if((r+1)%数组长度 == f){
已满
}else{
未满
}

队列算法：
入队
出队

队列的具体应用：
所有和时间有关的操作都有队列的影子

栈代码：

# include<stdio.h>
# include<stdlib.h>
# include<malloc.h>
// 数据
typedef struct Node{
    int data;
    struct Node *pNext;
}NODE,* PNODE; 
//栈，用来标记栈
typedef struct Stack{
    PNODE pTop;
    PNODE pBottom;
}STACK,* PSTACK;

void init(PSTACK);
void push(PSTACK,int);
void traverse(PSTACK);
bool pop(PSTACK,int *);
bool empty(PSTACK pS);
void clear(PSTACK);
int main(void){
    int val;//标记
    STACK s;
    init(&s);
    push(&s,1);
    push(&s,2);
    push(&s,3);
    push(&s,4);
    traverse(&s);
    if(pop(&s,&val)){
        printf("出栈成功，数据为 %d\n",val);
    }else{
        printf("该栈为空!");
    }
    traverse(&s);
    clear(&s);
    traverse(&s);
    return 0;
}

void init(PSTACK pS){
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if(NULL == pS->pTop){
        printf("初始化失败!");
        exit(-1);
    }else{
        pS->pBottom = pS->pTop;
        pS->pBottom->pNext = NULL;
    }

    return;
}
//压栈
void push(PSTACK pS,int val){
    
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;
    
    pNew->pNext = pS->pTop;
    pS->pTop = pNew;
    return;
}

bool empty(PSTACK pS){
    if(pS->pBottom == pS->pTop){
        return true;
    }else{
        return false;
    }
}
//遍历栈
void traverse(PSTACK pS){
    if(empty(pS)){
        printf("该栈为空!");
    }else{
        //通过q来遍历，q相当于游标
        PNODE q = pS->pTop;

        while(pS->pBottom != q){
            printf("%d\n",q->data);
            q = q->pNext;
        }
    }

    return;

}

bool pop(PSTACK pS,int *val){
    
    if(empty(pS)){
        return false;
    }else{

        PNODE r = pS->pTop;
        *val = r->data;
        pS->pTop = r->pNext;
        free(r);
        r = NULL;
        return true;
    }

}

void clear(PSTACK pS){
    if(empty(pS)){
        printf("为空");
    }else{
        /**
         自己写的
        
        PNODE p = pS->pTop;
        PNODE q = p->pNext;
        while(NULL != q){
            free(p);
            p = q;
            q = p->pNext;
        }

        */

        /**
            老师写的
             
               老师的可以省一个循环，判断地址就行
        */
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while(p != pS->pBottom){
            q = p->pNext;
            free(p);
            p = q;
        }




        pS->pTop = pS->pBottom;

        printf("清空完成\n");
    }
}

运行结果： 运行结果

队列代码：

# include<stdio.h>
# include<malloc.h>

typedef struct QUEUE{
    int *pBase;
    int front;
    int rear;
}*PQUEUE;
void init(PQUEUE pq);
bool en_queue(PQUEUE,int);
bool full_queue(PQUEUE);
bool out_queue(PQUEUE,int *);
bool empty_queue(PQUEUE);
void traversion(PQUEUE);

int main(void){
    int val;
    struct QUEUE q;
    init(&q);
    en_queue(&q,1);
    en_queue(&q,2);
    en_queue(&q,3);
    en_queue(&q,4);
    en_queue(&q,5);
    en_queue(&q,6);
    en_queue(&q,7);
    en_queue(&q,8);
    
    traversion(&q);
    
    if(out_queue(&q,&val)){
        printf("出栈成功，元素为%d\n",val);
    }else{
        printf("出栈失败，该栈为空\n");
    }

    traversion(&q);

    return 0;
}

void init(PQUEUE pq){
    pq->pBase = (int *)malloc(sizeof(int) * 6);
    pq->front = pq->rear = 0;

}
bool full_queue(PQUEUE pq){
    if(pq->front == (pq->rear + 1) % 6){
        return true;
    }else{
        return false;
    }
}
bool en_queue(PQUEUE pq,int val){
    if(full_queue(pq)){
        return false;
    }else{
        pq->pBase[pq->rear] = val;
        pq->rear = (pq->rear + 1) % 6;
        
        return true;
    }
}
bool empty_queue(PQUEUE pq){
    if(pq->front == pq->rear){
        return true;
    }else{
        return false;
    }
}

void traversion(PQUEUE pq){
    if(empty_queue(pq)){
        printf("这个队列为空\n");
    }else{
        int i = pq->front;
        while(i != pq->rear){
            printf("%d\n",pq->pBase[i]);
            i = (i + 1) % 6;
        }
    }

    return;
}

bool out_queue(PQUEUE pq,int *val){
    if(empty_queue(pq)){
        return false;
    }else{
        *val = pq->pBase[pq->front];
        pq->front = (pq->front + 1) % 6;
        return true;
    }
}

运行结果： 搜狗截图20200210204215.png