数据结构3-栈和队列

news/2025/2/24 9:00:04

 栈和队列的操作特点

栈和队列是限定插入和删除只能在表的“端点”进行的线性表

栈（操作尾部）和队列（操作头部）是线性表的子集（是插入和删除位置受限的线性表）

栈（Stack）

栈是一个遵循 后进先出 (LIFO, Last In First Out) 规则的线性表。栈的插入和删除操作都只能在表的一端进行，即栈顶。常见的栈操作包括：

  1. Push：向栈顶插入一个元素。
  2. Pop：从栈顶删除一个元素。
  3. Top 或 Peek：查看栈顶元素。

队列（Queue）

队列是一个遵循 先进先出 (FIFO, First In First Out) 规则的线性表。队列的插入操作发生在表的一端（队尾），删除操作发生在表的另一端（队头）。常见的队列操作包括：

  1. Enqueue：向队尾插入一个元素。
  2. Dequeue：从队头删除一个元素。
  3. Front：查看队头元素。

栈与队列的比较：

  • 栈：插入和删除只能发生在表的顶部。栈是一种顺序存取的数据结构，操作是单向的。
  • 队列：插入操作发生在队尾，删除操作发生在队头，符合先进先出的原则。

在顺序存储结构和链式存储结构上实现栈(顺序栈、链栈)和队列(循环队列、链队列)的各种基本操作

1. 栈（Stack）基本操作

顺序栈（Array-based Stack）

顺序栈使用数组作为底层存储结构。基本操作包括 Push（入栈）、Pop（出栈）、Peek（获取栈顶元素）。

#define MAX_SIZE 100

typedef int ElemType;  // 假设栈的元素类型为整型
typedef struct {
    ElemType elem[MAX_SIZE];
    int top;  // 栈顶指针
} SqStack;

// InitStack: 初始化栈，构建一个空的顺序栈
void InitStack(SqStack &S) {
    S.top = -1;  // 初始化栈为空栈
}

// StackEmpty: 判断栈是否为空，栈空返回1，否则返回0
int StackEmpty(SqStack S) {
    return S.top == -1;  // 栈空返回1，否则返回0
}

// StackLength: 返回栈的元素个数（栈的长度）
int StackLength(SqStack S) {
    return S.top + 1;  // 栈长度为栈顶指针+1
}

// Push: 向栈顶插入元素e，如果栈满则报错
void Push(SqStack &S, ElemType e) {
    if (S.top == MAX_SIZE - 1) {
        printf("栈满\n");
        return;
    }
    S.elem[++S.top] = e;  // 入栈
}

// Pop: 从栈顶删除元素，并将删除的元素存储在e中
void Pop(SqStack &S, ElemType &e) {
    if (S.top == -1) {
        printf("栈空\n");
        return;
    }
    e = S.elem[S.top--];  // 出栈
}

// GetTop: 获取栈顶元素，但不删除该元素
void GetTop(SqStack S, ElemType &e) {
    if (S.top == -1) {
        printf("栈空\n");
        return;
    }
    e = S.elem[S.top];  // 获取栈顶元素
}
链栈（Linked List-based Stack）

链栈使用链表作为底层存储结构。基本操作与顺序栈类似。

typedef int ElemType;
typedef struct Node {
    ElemType data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;  // 栈顶指针
} LinkStack;

// InitStack: 初始化栈，构建一个空的链栈
void InitStack(LinkStack &S) {
    S.top = NULL;  // 初始化栈为空栈
}

// StackEmpty: 判断链栈是否为空，空栈返回1，否则返回0
int StackEmpty(LinkStack S) {
    return S.top == NULL;  // 栈空返回1，否则返回0
}

// Push: 向链栈的栈顶插入元素e
void Push(LinkStack &S, ElemType e) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = e;
    newNode->next = S.top;
    S.top = newNode;  // 入栈
}

// Pop: 从链栈的栈顶删除元素，并将删除的元素存储在e中
void Pop(LinkStack &S, ElemType &e) {
    if (S.top == NULL) {
        printf("栈空\n");
        return;
    }
    Node* temp = S.top;
    e = S.top->data;  // 出栈
    S.top = S.top->next;
    free(temp);
}

// GetTop: 获取链栈的栈顶元素，但不删除该元素
void GetTop(LinkStack S, ElemType &e) {
    if (S.top == NULL) {
        printf("栈空\n");
        return;
    }
    e = S.top->data;  // 获取栈顶元素
}
链队列（Linked List-based Queue）

链队列使用链表作为底层存储结构，队列的头指针指向队头，尾指针指向队尾。

typedef int ElemType;
typedef struct Node {
    ElemType data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
} LinkQueue;

// InitStack: 初始化栈，构建一个空的链栈
void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = NULL;  // 初始化队列为空队列
}

// StackEmpty: 判断链栈是否为空，空栈返回1，否则返回0
int QueueEmpty(LinkQueue Q) {
    return Q.front == NULL;  // 判断队列是否为空
}

// Enqueue: 向队列的队尾插入元素e
void Enqueue(LinkQueue &Q, ElemType e) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = e;
    newNode->next = NULL;
    if (Q.rear == NULL) {
        Q.front = Q.rear = newNode;  // 队列为空时，队头和队尾都指向新节点
    } else {
        Q.rear->next = newNode;  // 队尾插入新节点
        Q.rear = newNode;
    }
}

// Dequeue: 从队列的队头删除元素，并将删除的元素存储在e中
void Dequeue(LinkQueue &Q, ElemType &e) {
    if (Q.front == NULL) {
        printf("队列空\n");
        return;
    }
    Node* temp = Q.front;
    e = Q.front->data;  // 出队
    Q.front = Q.front->next;
    if (Q.front == NULL) {
        Q.rear = NULL;  // 如果队列为空，更新队尾指针
    }
    free(temp);
}

// GetFront: 获取队列的队头元素，但不删除该元素
void GetFront(LinkQueue Q, ElemType &e) {
    if (Q.front == NULL) {
        printf("队列空\n");
        return;
    }
    e = Q.front->data;  // 获取队头元素
}

栈和队列的简单应用

假设有一个洗碗机，它需要根据不同的顺序来处理碗碟。这个问题涉及到两个部分：清洗和排队。当碗碟进洗碗机时，它们是按先进先出（FIFO）的顺序进入的。然而，清洗时，洗碗机只能后进先出（LIFO）的顺序进行处理。也就是说，洗碗机必须清洗最后进入的碗碟，然后才清洗前面的碗碟。

使用一个队列来模拟碗碟的进入顺序，而使用一个栈来模拟洗碗机清洗的顺序。

  • 碗碟进入洗碗机：用户将碗碟依次放入洗碗机，这部分用一个队列来模拟。每个碗碟被按顺序加入队列。

  • 清洗顺序：由于洗碗机必须按照“后进先出”的顺序清洗碗碟，可以将队列中的碗碟转移到栈中，然后按栈的顺序进行清洗。

  • 清洗过程：从栈中弹出碗碟并清洗，直到栈为空。

from collections import deque

class Dishwasher:
    def __init__(self):
        self.queue = deque()  # 用队列存储碗碟进入顺序
        self.stack = []  # 用栈模拟清洗顺序

    def add_dish(self, dish):
        # 把碗碟按顺序放入队列
        self.queue.append(dish)
        print(f"添加碗碟：{dish}")

    def start_washing(self):
        # 把队列中的碗碟转移到栈中（洗碗机需要后进先出的顺序）
        while self.queue:
            dish = self.queue.popleft()
            self.stack.append(dish)
        
        print("开始清洗碗碟：")
        # 按栈的顺序清洗碗碟（后进先出）
        while self.stack:
            dish = self.stack.pop()
            print(f"正在清洗：{dish}")

# 使用示例：
dishwasher = Dishwasher()
dishwasher.add_dish("碗1")
dishwasher.add_dish("碟1")
dishwasher.add_dish("杯子1")

# 开始清洗
dishwasher.start_washing()

碗碟进入顺序：碗1, 碟1, 杯子1，它们依次进入队列。

清洗顺序：由于洗碗机必须后进先出（LIFO），我们把队列中的碗碟依次转移到栈中，然后按栈的顺序清洗：先清洗最后放入的“杯子1”，然后是“碟1”，最后是“碗1”。

递归程序设计的基本方法(分治法、减治法)

递归程序设计的基本方法，包括分治法和减治法。其中，分治法递归的结构为“基本项+归纳项”。具体而言：

基本项：递归的终止条件，当问题足够简单时，直接返回结果。

归纳项：通过将问题分解为更小的子问题来解决，并递归地调用同样的方法来处理这些子问题，直到满足基本项条件。

分治法递归：基本项+归纳项。

阶乘计算：

long Fact(long n) {
    if (n == 0) return 1;  // 基本项
    else return n * Fact(n - 1);  // 归纳项
}

基本项：当 n == 0 时，返回 1。

归纳项：当 n > 0 时，返回 n * Fact(n - 1)，通过递归调用计算阶乘。

这种结构很适合解决分治法问题，即通过递归将大问题分解成小问题，再逐步解决。


http://www.niftyadmin.cn/n/5864138.html

相关文章

机器人部分专业课

机器人部分专业课

华东理工 人工智能与机器人导论 Introduction of Artificial Intelligence and Robots 必修 考查 0.5 8 8 0 1 16477012 程序设计基础 The Fundamentals of Programming 必修 考试 3 64 32 32 1 47450012 算法与数据结构 Algorithm and Data Structure 必修 考试 3 56 40 …
阅读更多...
debian 12安装 postgresql 17

debian 12安装 postgresql 17

按照官方文档安装，即可安装成功 https://www.postgresql.org/download/linux/debian/ 添加存储库 #添加存储库 sudo apt install -y postgresql-common#执行 存储库内 命令，自动处理某些东西 sudo /usr/share/postgresql-common/pgdg/apt.postgresql.o…
阅读更多...
演示基于FPGA的视频图像去雾处理效果

演示基于FPGA的视频图像去雾处理效果

我近期用FPGA开发板做了一个视频图像去雾算法模块，用于验证其能否在不进行帧缓冲的情况下实现去雾功能。 去雾算法来自一篇技术资料（私信提供篇名），其基础是近似的大气光模型。 1 算法原理概要 借助RGB直角坐标空间中的光矢量分…
阅读更多...
【电机控制器】ESP32-C3语言模型——通义千问

【电机控制器】ESP32-C3语言模型——通义千问

【电机控制器】ESP32-C3语言模型——通义千问 文章目录 [TOC](文章目录) 前言一、简介二、代码三、实验结果四、参考资料总结 前言 使用工具&#xff1a; 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、简介 二、代码 #include <WiFi.h> …
阅读更多...
达梦数据库学习笔记@1

达梦数据库学习笔记@1

目录 达梦数据库学习笔记一、表空间管理&#xff08;一&#xff09;默认表空间&#xff08;二&#xff09;相关数据字典&#xff08;三&#xff09;表空间操作&#xff08;四&#xff09;临时表空间管理 二、重做日志管理&#xff08;一&#xff09;系统视图&#xff08;二&…
阅读更多...
管道-过滤器、隐式调用、解释器架构风格对比

管道-过滤器、隐式调用、解释器架构风格对比

管道-过滤器、隐式调用与解释器架构风格对比 1. 管道过滤器风格&#xff08;Pipe-Filter&#xff09; 核心思想&#xff1a;系统由一系列独立的过滤器&#xff08;处理单元&#xff09;组成&#xff0c;通过管道&#xff08;数据通道&#xff09;连接&#xff0c;数据按顺序流…
阅读更多...
【分布式数据一致性算法】Gossip协议详解

【分布式数据一致性算法】Gossip协议详解

在分布式系统中&#xff0c;多个节点同时提供服务时&#xff0c;数据一致性是核心挑战。在多个节点中&#xff0c;若其中一个节点的数据发生了修改&#xff0c;其他节点的数据都要进行同步。 一种比较简单粗暴的方法就是 集中式发散消息&#xff0c;简单来说就是一个主节点同时…
阅读更多...
windows下安装CUDA-本地微调大模型

windows下安装CUDA-本地微调大模型

1、查看NVIDIA的控制面板的版本号 2 下载CUDA Toolkit https://developer.nvidia.com/cuda-toolkit-archive 这里要下载和自己电脑NVIDIA适配CUDA的大版本要保持一致 选择对应的版本进行下载 文件比较大&#xff0c;直接右键复制链接&#xff0c;放到迅雷中两分钟就下好了 3 …
阅读更多...
最新文章

Copyright @ 2022~2023