栈和队列

栈和队列

2022 年 03 月 02 日

1819 次浏览

4668字数

栈

1.栈的表示和实现

1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循后进先出LIFO（Last In First Out）的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。入数据也在栈顶。
栈有两种实现方式：数组、链表
数组：相当于之前顺序表的尾插，尾插用尾去做了栈顶，非常合适。唯一缺陷就是：空间不够需要增容
链表
单链表：使用单链表就优点不合适了，除非将链表的链尾当作栈底、链头当栈顶。栈顶插入就等于链表头插入O(1)
双链表：如果用尾做栈顶，那么就要用双向链表更好。效率O(1)
**但一般栈的实现都会使用数组来实现**（数组的cpu缓存命中要略高一些(**预加载**)）

声名：

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef _TEST_H
#define _TEST_H
//栈的链式存储结构；
typedef struct Node  //创建一种类型的节点；
{
    int data;
    struct Node * pnext;
}NODE, *PNODE;
typedef struct Stack  //创建一个栈类型，里面含有两个指针，一个指向栈顶，一个指向栈底
{
    PNODE ptop;
    PNODE pBottom;
}STACK, *PSTACK;

void init(PSTACK ps);//初始化栈
void push(PSTACK ps, int val);//压栈
void traverse(PSTACK ps);//遍历栈
bool empty(PSTACK ps);//判断栈是否为空
bool pop(PSTACK ps, int * pval);//出栈
void clear(PSTACK ps);//清空栈
#endif  //_TEST_H

具体实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>
#include "test.h"
int main()
{
    //int val;//保存出栈的元素
    STACK S;//定义一个栈变量
    init(&S);//初始化这个栈
    push(&S, 1);//压栈
    push(&S, 2);
    push(&S, 3);
    push(&S, 4);
    push(&S, 5);
    push(&S, 6);
    traverse(&S);//遍历
    /*if (pop(&S, &val))//出栈
    {
        printf("出栈成功!出栈元素为%d \n", val);
        printf("-------------------------------------------------------\n");
    }
    else
    {
        printf("出栈失败！\n");
    }*/
    //traverse(&S);
    clear(&S);//清空
    printf("-------------------------------------------------------\n");
    printf("清空后栈中元素为：");
    printf("栈中元素为：\n");
    traverse(&S);
    //free（S）;//销毁栈
    system("pause");
    return 0;
}
void init(PSTACK ps)
{
    ps->ptop = (PNODE)malloc(sizeof(NODE));//创建一个空栈
    if (NULL == ps->ptop)
    {
        printf("success\n");
        exit(-1);
    }
    else
    {
        ps->pBottom = ps->ptop;//栈底指针跟栈顶指针都指向这个新建的空节点
        ps->ptop->pnext = NULL;
    }
}
void push(PSTACK ps, int val)//压栈
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));//新建一个节点
    pNew->data = val;//新节点数据域等于val
    pNew->pnext = ps->ptop;//新节点指针域指向栈顶指针所指向的节点，就是前面栈底跟栈顶同时指向的空节点，这样就实现压栈了
    ps->ptop = pNew;//然后栈顶元素上移，始终指向就是最后入栈的节点
}
void traverse(PSTACK ps)//遍历
{
    PNODE p = ps->ptop;//遍历是从栈顶依次输出，所以创建一个指针，指向栈顶指针所指向的节点
    while (p!=ps->pBottom)//当p所指向的节点不是栈底指针指向的节点时
    {
        printf("%d\n", p->data);//输出p所指向的节点的数据域的值
        p = p->pnext;//然后指针p重新指向下一个节点
    }
}
//bool pop(PSTACK ps, int * pval)//出栈一个元素
//{
//    if (empty(ps))//先判断栈是否为空
//    {
//        return false;
//    }
//    else//不为空时
//    {
//        PNODE r = ps->ptop;//创建一个新的指针r，指向栈顶指针所指向的节点
//        *pval = r->data;//将该节点的数据域赋值给val
//        ps->ptop = r->pnext;//栈顶指针重新指向r所指向的下一个节点，
//        free(r);//释放r所指向的节点，就是刚才的栈顶节点
//        r = NULL;//清空
//        return true;
//    }
//}
bool empty(PSTACK ps)//判断栈是否为空
{
    if (ps->ptop == ps->pBottom)
        return true;
    else
        return false;
}
void clear(PSTACK ps)//清空栈内元素
{
    if (empty(ps))
    {
        return ;
    }
    else
    {
        PNODE p = ps->ptop;//创建一个指针，指向当前栈顶指针指向的节点
        PNODE q = NULL;//创建一个中间指针
        while (p!=ps->pBottom)//当p所指向的节点不是栈底指针所指向的节点时
        {
            q = p->pnext;//先将p所指向的下一个节点赋给q
            free(p);//然后删除该节点
            p = q;//然后将q指向的节点赋给p,也就是p重新指向了p的下一个节点
        }
        ps->ptop = ps->pBottom;//循环完了之后，栈底指针跟栈底指针指向同一个节点
    }
}

2.队列

2.1队列的概率及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First in First Out）
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.2队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数据的结构，出队列在数组头上出数据，效率会比较低。
记住两个公式：队列中，队列满的条件是：（rear+1）%QueueSize=front；
队列长度公式是：（rear-front+QueueSize）%QueueSize。
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;

typedef struct QueueNode {
    
    struct QueueNode* next;
    QDataType data;
}QNode;

typedef struct Queue { //这样的好处就是消除二级指针
    QNode* tail;
    QNode* head;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
//规定：队尾入
void QueuePush(Queue* pq, QDataType x);
//队头出
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);