栈和队列的实现

2022-11-10 15:00:10 浏览数 (1)

一、栈

1.概念

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵循后进先出的原则。 注意从栈顶入，栈顶出

二 、栈的实现(顺序表)

1.函数的定义和结构体的创建——stack.h

代码语言：javascript复制
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int datatype;
typedef struct stack
{
    datatype* a;
    int top;
    int capacity;
}ST;
void stackinit(ST* p);
void stackpush(ST* p, datatype x);
int stacktop(ST* p);
void stackpop(ST* p);
int stacksize(ST* p);
bool stackempty(ST* p);
void stackdestroy(ST* p);

2.函数的调用——test.c

代码语言：javascript复制
#include"stack.h"
int main()
{
    ST st;
    stackinit(&amp;st);
    stackpush(&amp;st, 1);
    stackpush(&amp;st, 2);
    stackpush(&amp;st, 3);
    stackpush(&amp;st, 4);
    while (!stackempty(&amp;st))//判断是否为空
    {
        printf("%d ", stacktop(&amp;st));//出栈
        stackpop(&amp;st);//移除栈顶元素
    }
    stackdestroy(&amp;st);//内存销毁
    return 0;
}

3.栈的接口

1.初始化

代码语言：javascript复制
void stackinit(ST* p)//栈的初始化
{
    assert(p);
    p->a = NULL;
    p->top = 0;
    p->capacity = 0;
}

2.入栈

代码语言：javascript复制
void stackpush(ST* p, datatype x)//入栈
{
    assert(p);
    if (p->top == p->capacity)//扩容
    {
        int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
        datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype) * newcapacity);
        if (tmp != NULL)
        {
            p->a = tmp;
            p->capacity = newcapacity;//扩容成原来的2倍
        }
    }
    p->a[p->top] = x;
    p->top  ;
}

3.移除栈顶元素

代码语言：javascript复制
void stackpop(ST* p)//移除栈顶元素
{
    assert(p);
    assert(p->top > 0);
    p->top--;
}

4.出栈

代码语言：javascript复制
int  stacktop(ST* p)//出栈
{
    assert(p);
    assert(p->top > 0);
    return p->a[p->top - 1];//top从0开始，每次入栈top都向后移，所以top-1是实际储存的元素
}

5.判断为空

代码语言：javascript复制
bool  stackempty(ST* p)//是否为空
{
    return p->top == 0;//当栈中没有数据时，则为空，为真， 否则为假。
}

6.栈中元素个数

代码语言：javascript复制
int stacksize(ST* p)//栈中元素个数
{
    assert(p);
    return p->top;//虽然top是指向下一个，但是top从0开始，top正好是元素个数
}

7.内存销毁

代码语言：javascript复制
void stackdestroy(ST* p)//内存销毁
{
    assert(p);
    free(p->a);//销毁动态开辟数组
    p->a = NULL;
    p->top = 0;
    p->capacity = 0;
}

三、队列

1.概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的原则。 入队列：进行插入操作的一段称为队尾 出队列：进行删除操作的一端称为对头 注意 ：对尾入，对头出

四、队列的实现(链表)

1.函数的定义和结构体的创建——queue.h

代码语言：javascript复制
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int datatype;
typedef struct queuenode
{
    datatype data;
    struct queuenode* next;
}queuenode;
typedef struct queue
{
    queuenode * head;
    queuenode * tail;
}queue;
void queueinit(queue*p);
void queuedestroy(queue* p);
void queuepush(queue* p,datatype x);
void queuepop(queue* p);
datatype queuefront(queue* p);
datatype queueback(queue* p);
int queuesize(queue* p);
bool queueempty(queue* p);

2.函数的调用——test.c

代码语言：javascript复制
#include"queue.h"
int main()
{
    queue p;
    queueinit(&amp;p);
    queuepush(&amp;p, 1);
    queuepush(&amp;p, 2);
    queuepush(&amp;p, 3);
    queuepush(&amp;p, 4);
    while (!queueempty(&amp;p))//判断为空
    {
        datatype front = queuefront(&amp;p);
        printf("%d ", front);
        queuepop(&amp;p);
    }
    queuedestroy(&amp;p);//内存销毁
    return 0;
}

3.取一级指针的原因

正常来说，如果将head与tail放在queuenode内部，应该取二级指针， 但是由于此时定义的是结构体为queue 的变量，改变的是该变量的内部。 所以只取一级指针就可以。

4.队列的接口的实现

1.初始化

代码语言：javascript复制
void queueinit(queue* p)//初始化队列
{
    assert(p);
    p->head = NULL;
    p->tail = NULL;
}

2.入队列

代码语言：javascript复制
void queuepush(queue* p,datatype x)//入队列 (队尾入)
{
    assert(p);
    queuenode* newnode = (queuenode*)malloc(sizeof(queuenode));
    newnode->data = x;
    newnode->next = NULL;
    if (p->tail == NULL)
    {
        p->tail = newnode;
        p->head = newnode;
    }
    else
    {
        p->tail->next = newnode;
        p->tail = newnode;
    }
}

3.删除数据

代码语言：javascript复制
void queuepop(queue* p)//删除数据
{
    assert(p);
    assert(!queueempty(p));//断言队列是否为空
    queuenode* next = p->head->next;
    free(p->head);
    p->head = next;
    if (p->head == NULL)//当删除只剩下最后一个节点时 head与tail都指向，free(head) ,tail就变成了野指针
    {
        p->tail = NULL;
    }
}

4.取对头数据

代码语言：javascript复制
datatype queuefront(queue* p)//取队头数据
{
    assert(p->head);
    assert(!queueempty(p));
    return p->head->data;
}

5.取队尾数据

代码语言：javascript复制
datatype queueback(queue* p)//取队尾数据
{
    assert(p->head);
    assert(!queueempty(p));
    return p->tail->data;
}

6.取队的元素个数

代码语言：javascript复制
int queuesize(queue* p)//队的数量
{
    assert(p);
    int sum = 0;
    queuenode* cur = p->head;
    while (cur != NULL)
    {
        sum  ;
        cur= cur->next;
    }
    return sum;
}

7.判断为空

代码语言：javascript复制
bool queueempty(queue* p)//判断队列是否为空
{
    assert(p);
    return p->head == NULL;
}

8.内存销毁

代码语言：javascript复制
void queuedestroy(queue* p)//内存销毁
{
    assert(p);
    queuenode* cur = p->head;
    while (cur != NULL)
    {
        queuenode* next = cur->next;
        free(cur);
        cur = next;
    }
    p->head = NULL;
    p->tail = NULL;
}
queue stack tail 队列

0 人点赞