1. AI技术聚合首页
  2. IT

数据结构——栈和队列

社会演员多 • • IT • 阅读 53

了解并实现栈和队列—–C语言版

  • 目录：
  • 一、栈
    • 1.1栈的定义
    • 1.2栈的实现
      • 1.2.1 栈的相关接口
      • 1.2.2栈结构的定义声明和栈的初始化
      • 1.2.3栈数据的处理
      • 1.2.4 栈判空和获取栈中元素个数以及栈销毁
      • 1.2.5 栈的代码实现
  • 二、队列
    • 2.1队列的定义
    • 2.2队列的实现
      • 2.2.1 队列的相关接口
      • 2.2.2 队列结构的定义声明和队列初始化
      • 2.2.3队列数据的处理
      • 2.2.4队列判空和获取队列中元素的个数以及队列的销毁
      • 2.2.5队列代码的实现。

目录：

数据结构好难啊，要多学几遍，博客才能下得去笔。加油！

一、栈

栈:一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

1.1栈的定义

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last In FirstOut)的原则。

压栈：栈的插入操作叫做压栈/入栈/进栈。入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2栈的实现

栈一般都是用数组和链表的方法去实现得，用数组去实现栈的方法更优一点，因为数组的尾删尾插更方便一点。

1.2.1 栈的相关接口

// 初始化栈
void StackInit(Stack* ps);
//扩容
void Stackcapa(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

1.2.2栈结构的定义声明和栈的初始化

栈结构的声明：

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

栈的实现是和顺序表有点像，因为顺序表一般也是用数组来实现的。我们这里采用动态顺序表的实现方式，实现动态栈。当栈中空间不够时，可申请动态内存空间进行增容。

栈的初始化:

void StackInit(Stack* ps)
{ 
    ps->a = NULL;
    ps-> top =0 ;		// 栈顶
    ps->capacity=0;  // 容量 
}

1.2.3栈数据的处理

1.入栈

void  StackPush(Stack* ps, STDataType data)
{
    assert(ps);
 if (ps->top == ps->capacity)//相等就扩容
{
Stackcapa(ps);//扩容
}
    ps->a[ps->top] = data;//先赋值，在加加
    ps->top++;
}

扩容的函数

void Stackcapa(Stack* ps)//扩容
{
        int n = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* top = (STDataType*)realloc(ps->a, sizeof(STDataType) * n);
        if (top == NULL)//判断是否为空
        {
            perror("realloc fail");
            exit(-1);
        }
        ps->a = top;
        ps->capacity = n; 
}

入栈就是尾插数据，也就是按顺序插入数据。因为刚才说了top是指向栈顶元素下一个位置，初始化top为0表示的是空栈，但是数组索引从0开始，因此先插入数据，然后top自增，这样做的另一个好处就是top就是栈中元素个数。

2.出栈

获取栈顶元素

STDataType StackTop(Stack* ps)
{
    assert(ps);//判断栈是否为空
    assert(!StackEmpty(ps));
    return ps->a[ps->top-1];
}

因为top是指向栈顶元素下一个位置的，所以栈顶元素应该是top-1。还有一点，当栈为空时，就不能获取元素，所以要断言一下。

出栈

void StackPop(Stack* ps)
{
    assert(ps);//判断栈是否为空
    assert(ps->top>0);
    --ps->top;//栈减一个就是出栈
}

出栈就相当于尾删，然后top(栈顶）往下降一个单位。但是，出栈肯定是要得到某个数据，就是将栈中的数据弹出来，然后栈顶往下降。因此还需要个函数来获取栈顶的元素。

1.2.4 栈判空和获取栈中元素个数以及栈销毁

1.栈判空

int StackEmpty(Stack* ps)
{
    assert(ps);//判断栈是否为空
    return ps->top == 0;
}

栈判空非常简单，top为0就是空栈。如果top大于0就不是空栈。

2.获取栈中元素个数

int StackSize(Stack* ps)
{
    assert(ps);//判断栈是否为空
    return ps->top;
}

数组是从0开始的，而top又是指向栈顶元素下一个位置的，刚好top就是栈元素个数，top的值就是栈中元素个数。

3.栈销毁

void StackDestroy(Stack* ps)
{
    assert(ps);//判断栈是否为空
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

销毁栈还是和销毁动态顺序表一样，用free释放掉申请的动态内存空间即可，释放掉空间后，该置空的置空，该置0的置0。

1.2.5 栈的代码实现

用C语言实现一个支持动态增长的栈
.h头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps);
//扩容
void Stackcapa(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

.c源文件

#pragma once
#include "stack.h"

// 初始化栈 
void StackInit(Stack* ps)
{ 
    ps->a = NULL;
    ps-> top =0 ;		// 栈顶
    ps->capacity=0;  // 容量 
}
void Stackcapa(Stack* ps)//扩容
{
        int n = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* top = (STDataType*)realloc(ps->a, sizeof(STDataType) * n);
        if (top == NULL)//判断是否为空
        {
            perror("realloc fail");
            exit(-1);
        }
        ps->a = top;
        ps->capacity = n; 
}
//入栈
void  StackPush(Stack* ps, STDataType data)
{
    assert(ps);
 if (ps->top == ps->capacity)//相等就扩容
{
Stackcapa(ps);//扩容
}
    ps->a[ps->top] = data;//先赋值，在加加
    ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
    assert(ps);//判断栈是否为空
    assert(ps->top>0);
    --ps->top;//栈减一个就是出栈
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
    assert(ps);//判断栈是否为空
assert(!StackEmpty(ps));
    return ps->a[ps->top-1];
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
    assert(ps);//判断栈是否为空
    return ps->top == 0;
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
    assert(ps);//判断栈是否为空
    return ps->top;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
    assert(ps);//判断栈是否为空
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

.c源文件

#pragma once
#include "stack.h"
void test_1()
{
    Stack ps;//定义一个栈
    // 初始化栈 
    StackInit( &ps);
    // 入栈 
    StackPush( &ps, 4);
    // 入栈 
    StackPush(&ps, 5);
    // 入栈 
    StackPush(&ps, 6);
    printf("栈中有效元素个数：%d\n", StackSize(&ps));
    // 获取栈顶元素 
    while (!StackEmpty(&ps))
    {
        printf("%d ", StackTop(&ps));
        // 出栈 
        StackPop(&ps);
    }
    printf("\n");
    StackDestroy(&ps);
 
}
int main()
{
    test_1();
    return 0;
}

二、队列

队列:只允许在一端进行插入数据操作，另一端进行刪除数据操作的特殊线性表。

2.1队列的定义

进行数据插入操作的一端叫做入队，进行数据删除操作的一端叫做出队，队列中的数据遵循先进先出FIFO（First In First Out）的原则。

入队列:进行数据插入操作的一端称为队尾。
出从列:进行数据刪除操作的一端称为队头。

2.2队列的实现

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些， 因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.2.1 队列的相关接口

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

2.2.2 队列结构的定义声明和队列初始化

队列结构的声明：

typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;//用来存入队的数据
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;//队头
	QNode* rear;//队尾
	QDataType size;//用来记录元素个数
}Queue;

这里用到了两个结构体，因为我们不仅要有链式的结构，还要标识队列的头和尾，这样方便我们进行头删和尾插，至于size则是用来记录队列中的元素个数的。

队列初始化：

void QueueInit( Queue* q)
{
    assert(q);
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

首先判断是否为空，然后把size置为0，头和尾都置成空。

2.2.3队列数据的处理

1.入队

// 队尾入队列 
void QueuePush(Queue* q, QDataType x)
{
    assert(q);
    QNode* NewNode = (QNode*)malloc(sizeof(QNode));//新建一个节点
    if (NewNode == NULL)
    {
        perror("NewNode");
        exit(-1);
    }
    NewNode->data = x;
    NewNode->next = NULL;
    if (q->rear == NULL)//如果是空队列
    {
        q->front = q->rear = NewNode;
    }
    else//不是空队列
    {
        q->rear->next = NewNode;//尾插
        q->rear = NewNode;
    }
    q->size++;
}

首先肯定是要申请节点，然后进行插入 ，但是插入也分两种情况。
第一种情况：一个数据都没有，front和rear同时指向空；第二种情况：已经有数据了直接在rear后面链接就行了。

获取队列尾部元素

QDataType Queueback(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->rear->data;
}

先判空，队列不能为空，返回队尾数据。

2.出队

// 队头出队列 
void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    if(q->front->next==NULL)
    {
        free(q->front);
        q->front = q->rear = NULL;
    }
    else
    {
        QNode* pwd = q->front->next;//把头指针指向的位置先存起来
           free(q->front);
        q->front = pwd;
    }
    q->size--;
}

这里的删除也是要判断是只有一个结点还是有多个结点的情况
只有一个结点或者删到只有一个结点，就要把头free掉并且头指针和尾都要置成空；有多个节点，创建一个指针，存放pwd的下一个结点，接着free掉头指针，然后更新一下头指针。

获取队列头部元素

QDataType QueueFront(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->front->data;

}

先判空，队列不能为空，返回队头数据。

2.2.4队列判空和获取队列中元素的个数以及队列的销毁

1.队列判空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
    assert(q);
    return q->front == NULL;
}

如果队列头指针为空就是空队列，头指针不为空，就不是空队列。

2.获取队列中元素的个数

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);
    return q->size;
}

结构体Queue中成员size记录的是元素个数

3.队列的销毁

// 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* pwd = q->front;//指向头指针 
    while (pwd)//不是空指针就循环
    {
        QNode* next = pwd->next;
        free(pwd);
        pwd = next;
    }

    q->front = q->rear = NULL;
    q->size = 0;
}

有多少个malloc函数开辟空间就要有多少个free函数释放空间，释放掉空间后，该置空的置空，该置0的置0。

2.2.5队列代码的实现。

用c语言实现一个由链表结构实现的队列

.h头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	QDataType size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

.c源文件

#include "queue.h" 
// 初始化队列 
void QueueInit( Queue* q)
{
    assert(q);
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType x)
{
    assert(q);
    QNode* NewNode = (QNode*)malloc(sizeof(QNode));//新建一个节点
    if (NewNode == NULL)
    {
        perror("NewNode");
        exit(-1);
    }
    NewNode->data = x;
    NewNode->next = NULL;
    if (q->rear == NULL)//如果是空队列
    {
        q->front = q->rear = NewNode;
    }
    else//不是空队列
    {
        q->rear->next = NewNode;//尾插
        q->rear = NewNode;
    }
    q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    if(q->front->next==NULL)
    {
        free(q->front);
        q->front = q->rear = NULL;
    }
    else
    {
        QNode* pwd = q->front->next;//把头指针指向的位置先存起来
           free(q->front);
        q->front = pwd;
    }
    q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->front->data;

}
// 获取队列尾部元素 
QDataType Queueback(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->rear->data;

}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
    assert(q);
    return q->front == NULL;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);
    return q->size;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* pwd = q->front;//指向头指针 
    while (pwd)//不是空指针就循环
    {
        QNode* next = pwd->next;
        free(pwd);
        pwd = next;
    }

    q->front = q->rear = NULL;
    q->size = 0;
}

.c源文件

#include "queue.h" 
void test_1()
{
//定义一个指向队列的指针
    Queue q;
    // 初始化队列 
    QueueInit(&q);
    // 队尾入队列 
    QueuePush(&q, 2);
    // 队尾入队列 
    QueuePush(&q, 3);
    // 队尾入队列 
    QueuePush(&q, 4);
    // 队尾入队列 
    QueuePush(&q, 5);
    // 队尾入队列 
    QueuePush(&q, 6);
    // 获取队列中有效元素个数 
    printf("有效元素个数：%d\n", QueueSize(&q)) ;

    while (!QueueEmpty(&q))
    {
        // 获取队列头部元素 
        printf("%d ", QueueFront(&q));
        // 队头出队列 
        QueuePop(&q);
    }
   //  销毁队列 
   QueueDestroy(&q);
}
int main()
{
    test_1();
    return 0;
}

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
社会演员多的头像社会演员多普通用户
0
上一篇 2023年12月14日
下一篇 2023年12月14日

相关推荐