首页 > 其他分享 >栈和队列概念及相关实现

栈和队列概念及相关实现

时间：2024-08-01 18:55:11浏览次数：9  
标签：return 队列 queue 概念 mydata 相关 NULL data

栈

在线性逻辑结构中，可以是顺序存储和链式存储两种方式，其操作可以在线性表中的任意位置实现，可能不符合实际应用需求。优化的线性表，其中包含栈和队列
（注意：一下代码均以C语言实现）

1 栈的概述

所谓的栈，也称为堆栈，是一个特殊的线性逻辑关系。只能在固定端实现栈的读写访问，其固定端称为栈顶，与之对应的另外一端称为栈底(不参与数据运算)。

栈操作特点：先进后出、后进先出；

栈的存储结构：

顺序存储结构：是一个特殊的顺序表，在连续存储空间中顺序存储，通过数据元素存储位置序号表示数据元素之间的逻辑结构关系。

链式存储结构；是一个特殊的链表，在非连续存储空间中存储数据元素，通过指针表示数据元素逻辑结构关系。

2 顺序栈

2.1 顺序栈的操作

2.1.1 顺序栈数据类型的定义
/* 栈数据元素数据类型的定义 */
typedef int data_t;

/* 动态栈数据类型的定义 */
typedef struct sqstack {
    data_t *data;        /* 连续存储空间起始地址 */
    int nmemb;            /* 顺序栈可存储数据元素个数 */
    int top;            /* 栈顶元素存储位置序号 */
} sqstack_t ;
2.1.2 创建顺序栈
sqstack_t *CreateSqStack(int mynmemb)
{
    sqstack_t *stack;
    
    /* 动态创建栈信息存储结构体空间 */
    stack = malloc(sizeof(sqstack_t));
    if (stack == NULL)
        return NULL;
    
    memset(stack, 0, sizeof(sqstack_t));
    /* 动态创建顺序栈数据元素存储空间 */
    stack->data = calloc(mynmemb, sizeof(data_t));
    if (stack->data == NULL) {
        free(stack);
        return NULL;
    }
    stack->nmemb = mynmemb;
    stack->top = -1;        
    
    return NULL;
}
2.1.3 入栈

所谓的栈，也就是栈顶插入数据。

int PushSqStack(sqstack_t *stack, data_t mydata)
{
    if (stack == NULL)
        return -1;
    /* 判断栈空间是否为满，满则入栈失败*/
    if (stack->top == stack->nmemb-1)
        return -1;
    /* 入栈 */
    stack->data[++stack->top] = mydata;
    
    return 0;
}
2.1.4 出栈
/* 出栈 */
int PopSqStack(sqstack_t *stack)
{
    if (stack == NULL)
        return -1;
        
    /* 判断栈空间是否为空 */
    if (stack->top == -1)
        return -1;
    stack->top--;    /* 出栈操作 */
    return 0;
}
2.1.5 查看栈顶元素
/* 查看栈顶元素数据 */
int GetSqStack(sqstack_t *stack, data_t *mydata)
{
    if (stack == NULL)
        return -1;
        
    /* 判断栈空间是否为空 */
    if (stack->top == -1)
        return -1;
    *mydata = stack->data[stack->top];
    
    return 0;
}
2.1.6 其它操作
/* 清空栈 */
void ClearSqStack(sqstack_t *stack)
{
    if (stack == NULL)
        return;
    stack->top = -1;
}
/* 释放栈空间 */
void DestorySqStack(sqstack_t **stack)
{
    free((*stack)->data);
    free(*stack);
    *stack = NULL;
}

2.2 顺序栈分类

顺序栈数据元素存储空间，为连续存储空间，在连续存储空间中，

  1. 可以根据栈的地址生长空间分为递增栈和递减栈

    所谓的递增栈，指的是堆栈的地址是由低地址向高地址方向生长；

    所谓的递减栈，指的是堆栈的地址是由高地址向低地址方向生长。

  2. 可以根据栈顶指针(栈顶序号位置)数据是否有效分为满栈和空栈

    所谓的满栈，指的是栈顶序号位置的数据值为有效数据值；

    入栈，先修改栈顶位置，在写入值；出栈，先读取数据值，在修改栈顶位置；

    所谓的空栈，指的是栈顶序号位置的数据值为无效数据值；

    入栈，先写入数据值，在修改栈顶位置；出栈，先向栈顶位置，在读取数据值；

3 链式栈

所谓的链式栈，是一个特殊的链表，只能在链表的一端进行操作。将**链表的头结点**作为栈顶指针。

队列

1 队列的概述

1.1 队列的概念

所谓的队列，是特殊的线性表；不能在线性表中间位置进行操作，只能在线性表的两端实现操作，此时的两端分别为队头和队尾：

  1. 队尾(rear)：只能实现数据元素的写访问（插入数据元素）；

  2. 对头(front)：只能实现数据元素的读访问（查看队头数据元素、取队头数据元素）；

    队列的特点：先进先出、后进后出。

1.2 队列的存储结构

​ 顺序存储和链式存储两种方式

2 顺序队列

所谓顺序队列，指的是队列的顺序存储结构，此时队列中的数据元素在练习内存空间中存储。

2.1 顺序队列的理解

  1. 普通的顺序队列

在这里插入图片描述

  1. 顺序循环队列

在这里插入图片描述

2.2 顺序队列的操作

2.2.1 顺序循环队列数据类型的定义
/* 数据元素数据类型的定义 */
typedef int data_t;

/* 顺序循环队列 */
typedef struct sqqueue
    data_t *data;
    int nmemb;
    int front;            /* 队头游标：存储队头元素序号 */
    int rear;            /* 队尾游标：存储队尾元素序号 */
} sqqueue_t;
2.2.2 顺序循环队列的创建
sqqueue_t *CreateSqQueue(int mynmemb)
{
    sqqueue_t *queue;
    
    /* 动态创建顺序循环队列信息存储结构体空间 */
    queue = malloc(sizeof(sqqueue_t));
    if (queue == NULL)
        return NULL;
    
    /* 动态开辟顺序循环队列数据元素存储空间 */
    queue->data = calloc(mynmemb, sizeof(data_t));
    if (queue->data == NULL) {
        free(queue);
        return NULL;
    }
    queue->nmemeb = mynmemb;
    queue->front = 0;
    queue->rear = 0;
    
    return queue;
}
2.2.3 顺序队列操作实现
/* 入队 */
int EnSqQueue(sqqueue_t *queue, data_t mydata)
{
    if (queue == NULL)
        return -1;
    /* 判断队列是否为满队列 */    
    if ((queue->rear - queue->front) % queue->nmemb == queue->nmemb -1)
        return -1;
    
    queue->data[queue->rear] = mydata;
    queue->rear = (queue->rear+1) % queue->nmemb;
    
    return 0;
}
/* 出队 */
int DeSqQueue(sqqueue_t *queue)
{
    if (queue == NULL)
        return -1;
    /* 判断队列是否为空队列 */
    if (queue->rear == queue->front)
        return -1;
    /* 出队运算 */
    queue->front = (queue->front+1) % queue->nmemb;
    return 0;
}
/* 查看队头数据元素 */
int GetSqQueue(sqqueue_t *queue, data_t *mydata)
{
    if (queue == NULL)
        return -1;
    /* 判断队列是否为空队列 */
    if (queue->rear == queue->front)
        return -1;
    
    *mydata = queue->data[queue->front];
    
    return 0;
}
/* 判断队列是否为空 */
int isEmptySqQueue(sqqueue_t *queue)
{
    return (queue->rear == queue->front);
}
/* 判断队列是否为空 */
int isFillSqQueue(sqqueue_t *queue)
{
     return ((queue->rear - queue->front) % queue->nmemb == queue->nmemb -1);
}
/* 清空队列 */
void ClearSqQueue(sqqueue_t *queue)
{
    queue->front = queue->rear = 0;
}
/* 销毁队列 */
void DestorySqQueue(sqqueue_t **queue)
{
    free((*queue)->data);
    free(*queue);
    *queue = NULL;
}

3 链式队列

所谓的链式队列，表示为队列的链式存储结构，是特殊的链表。只能在链表的两端进行访问，其中一端(链表头部)进行数据的读操作(读取队头数据元素的数据、出队操作)，另外一端(链表尾部)进行数据的写操作(入队操作)。

3.1 链式队列数据类型的定义

/* 链式队列中结点数据域的数据类型定义 */
typedef int data_t;

/* 链式队列中结点是数据类型定义 */
typedef struct node {
    data_t data;        /* 数据域 */
    struct node *next;    /* 指针域 */
} node_t;

/* 链式队列数据类型 */
typedef struct linkqueue {
    node_t * front;        /* 队头指针 */
    node_t * rear;        /* 队尾指针 */
} linkqueue_t;

3.2 链式队列的创建(初始化)

linkqueue_t *CreateLinkQueue(void)
{
    linkqueue_t *queue;
    
    /* 动态创建链式队列队头指针和队尾指针存储空间 */
    queue = malloc(sizeof(linkqueue_t));
    if (queue == NULL)
        return NULL;
        
    /* 创建无效数据结点，作为队头指针结点 */
    queue->front = malloc(sizeof(node_t));
    if (queue->front == NULL) {
        free(queue);
        return NULL;
    }
    queue->front->next = NULL;
    queue->rear = queue->front;    /* 空队列 */
    
    return queue;
}

3.3 链式队列的操作

/* 入队操作 */
int EnLinkQueue(linkqueue_t *queue, data_t mydata)
{
    node_t *q;
    
    /* 判断链式队列是否存在 */
    if(queue == NULL)
        return -1;
    /* 判断链式队列尾部结点是否存在 */
    if(queue->rear == NULL)
        return -1;
    /* 创建插入数据结点 */    
    q = malloc(sizeof(node_t));
    if (q == NULL) 
        return -1;
    memset(q, 0, sizeof(node_t));
    q->data = mydata;    /* 结点数据初始化 */
    q->next = NULL;
    queue->rear->next = q;    /* 插入结点：链表尾部结点后插入结点 */
    queue->rear = q;        /* 修改队尾指针 */
    
    return 0;
}

/* 读取队头结点数据 */
int GetLinkQueue(linkqueue_t *queue, data_t *mydata)
{    
    /* 判断链式队列是否存在 */
    if(queue == NULL)
        return -1;
    /* 判断链式队列头部结点是否存在 */
    if(queue->front == NULL)
        return -1;
    /* 判断链式队列是否为空队列 */    
    if (queue->front->next == NULL)
        return -1;
    
    *mydata = queue->front->next->data;
    
    return 0;
}

int DeLinkQueue(linkqueue_t *queue)
{
    node_t *q;
    
    /* 判断链式队列是否存在 */
    if(queue == NULL)
        return -1;
    /* 判断链式队列头部结点是否存在 */
    if(queue->front == NULL)
        return -1;
    /* 判断链式队列是否为空队列 */    
    if (queue->front->next == NULL)
        return -1;
    
    /* 出队操作 */
    q = queue->front->next;
    queue->front->next = q->next;
    free(q);
    
    if(queue->front->next == NULL)
        queue->rear = queue->front;
        
    return 0;
}

4 练习

  1. 如何使用两个队列实现一个栈

在这里插入图片描述

void push(linkqueue_t *queue_a, linkqueue_t *queue_b, data_t mydata)
{
   if (isEmptyLinkQueue(queue_a)) {
       EnLinkQueue(queue_b, mydata);
   } else {
       EnLinkQueue(queue_a, mydata);
   }
}

int pop(linkqueue_t *queue_a, linkqueue_t *queue_b, data_t *mydata)
{
   if (isEmptyLinkQueue(queue_a)) {
       if (isEmptyLinkQueue(queue_b)) {
           return -1;    /* 没有数据可以出栈 */
       }
       while(1) {
           if (GetLinkQueue(queue_b, mydata) == -1) 
               return -1;
           DeLinkQueue(queue_b);
           if (isEmptyLinkQueue(queue_b)) {
               return 0;
           }
           EnLinkQueue(queue_a, *mydata);
       }
   } else {
       while(1) {
           if (GetLinkQueue(queue_a, mydata) == -1) 
               return -1;
           DeLinkQueue(queue_a);
           if (isEmptyLinkQueue(queue_a)) {
               return 0;
           }
           EnLinkQueue(queue_b, *mydata);
       }
   }
}


int main()
{
   data_t mydata;
   linkqueue_t *queue_a;
   linkqueue_t *queue_b;
   
   queue_a = CreateLinkQueue();
   if (queue_a == NULL)
       return -1;
   
   queue_b = CreateLinkQueue();
   if (queue_b == NULL)
       return -1;    
   
   mydata = 5;
   while(mydata) {
       printf("push data : %d\n", mydata);
       push(queue_a, queue_b, mydata);        /* 数据元素的入栈先后顺序为：5 4 3 2 1 */
       mydata--;
   }
   printf("-----------%d------------\n", __LINE__);
   
   while(1) {
       if (pop(queue_a, queue_b, &mydata) == -1)    /* 数据元素的出栈先后顺序：1  2 3 4 5 */
           break;
       printf("pop data : %d\n", mydata);    
   }
}
  1. 如何使用两个栈实现一个队列

在这里插入图片描述

int DeQueue(node_t * top_a, node_t * top_b, data_t *mydata)
{
    if (top_b->next == NULL) {
        while(1) {
            if (GetLinkStack(top_a, mydata) == -1)
                break;
            PopLinkStack(top_a);
            PushLinkStack(top_b, *mydata);
        }
    } 
    
    if (top_b->next == NULL)
        return -1;
    GetLinkStack(top_b, mydata);
    PopLinkStack(top_b);
    
    return 0;
}

int EnQueue(node_t * top_a, node_t * top_b, data_t mydata)
{
    PushLinkStack(top_a, mydata);
}

int main()
{
    node_t * top_a;
    node_t * top_b;
    data_t mydata;
    
    top_a = CreateLinkStack();
    if (top_b == NULL)
        return -1;
    top_b = CreateLinkStack();
    if (top_b == NULL)
        return -1;
        
    mydata = 5;    
    while(mydata) {
        printf("%d push is %d\n", mydata--, EnQueue(top_a, top_b, mydata));
    }
    
    while(1) {
        if (-1 == DeQueue(top_a, top_b, &mydata)) 
            break;
        printf("mydata = %d\n", mydata);
    }
}

标签：return,队列,queue,概念,mydata,相关,NULL,data
From： https://blog.csdn.net/weixin_65477256/article/details/140798280

相关文章

  • 生命队列交换机方法
    在之前我们都是基于RabbitMQ控制台来创建队列、交换机。但是在实际开发时，队列和交换机是程序员定义的，将来项目上线，又要交给运维去创建。那么程序员就需要把程序中运行的所有队列和交换机都写下来，交给运维。在这个过程中是很容易出现错误的。因此推荐的做法是由程序启动时检查队列......
  • Day16 二叉树Part4 常规递归和遍历法的综合应用（二叉树相关）
    目录任务112.路径总和思路113.路径总和II思路106.从中序与后序遍历序列构造二叉树思路105.从前序与中序遍历序列构造二叉树思路心得体会任务112.路径总和给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路......
  • 抖音开放平台API接口如何开发||抖音相关接口数据采集数据分析 【附实例】
    抖音开放平台提供了多种接口，包括授权登录、用户信息、视频管理、评论互动、消息通知、数据分析等。以下是开发抖音接口的一些步骤：1.注册开发者账号：在抖音开放平台上注册开发者账号，获取开发者身份认证。2.创建应用：登录开放平台后，创建自己的应用，获取应用的AppID和App......
  • 类和对象的概念
    什么是类类（class）：定义：类是现实世界中某些具有共同属性和行为的事物的抽象。它定义了一组特定的属性（数据）和方法（操作这些数据的函数）。蓝图：类可以看作是创建对象的蓝图或模板。它规定了对象的结构和行为。封装：类通过将数据和操作这些数据的方法组合在一起，提供了封......
  • 类与对象的概念
    类与对象的概念一.类（class）类（Class）是面向对象编程（OOP,Object-OrientedProgramming）中的一个核心概念。它是一种将数据（称为属性或字段）和操作这些数据的方法（称为函数或方法）封装在一起的逻辑单元。类是创建对象的蓝图或模板，它定义了对象可以拥有的属性和方法。在面向对象编程中，类......
  • 1、消息队列框架：ActiveMQ - 开源项目研究文章
    ActiveMQ是Apache软件基金会下的一个开源消息队列服务，遵循JMS1.1规范（JavaMessageService），是一种面向消息中间件（MOM）的实现。它提供高可用性、出色的性能、可扩展性、稳定性和安全性的消息传递服务。ActiveMQ的架构ActiveMQ的架构包括生产者（Producer）、消费者......
  • 如何将优先级任务添加到celery队列而不禁用获取
    我有一个celery工作线程，并发度设置为1，它从RabbitMQ获取任务。我想创建一个在单个并发设置中只有一个队列的系统，因此，所有任务都将添加到主队列中。关于任务-它只是一个循环，我们用更新状态。|||并行地我有两个服务。task.update_state()Celery-beat......
  • Linux系统中 “管理基本存储” 中的部分相关重要知识点
    将持续更新发布，留下个关注吧！1.对Linux磁盘进行分区时有哪两种方案？MBR方案：支持最多四个主分区，可以使用扩展分区和逻辑分区创建最多15个分区，对于32位分区大小，使用此分区的磁盘最多可达2TiBGPT方案：最多提供128个分区，64位存储分区大小。最大磁盘分区大小可以达到8ZiB2.创......
  • 使用LinkedList实现队列和栈
    LinkedList底层是由双向链表实现的，因此可以支持Queue和Stack。本文讨论的实现基于JDK8源码。实现QueueLinkedList本身实现了Queue接口。入队方法签名接口说明(JDK手册)代码实现概括(JDK8)boolean add(Ee)将指定的元素插入此队列（如果立即可行且不会违反容量限制），在......
  • 【会计基础知识】销售相关业务会计分录
    1.普通销售1.1销售发货单在存货核算模块的会计分录：借：主营业务成本贷：库存商品1.2销售发票在应收账款模块的会计分录：借：应收账款贷：主营业务收入、应交税金--应交增值税--销项税额2.分期收款2.1在存货核算模块的会计分录：分期收款发货单：借：发出商品贷：库存商品分期收款......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99