数据结构队列知识点

实验课题一：回文（palindrome）是指一个字符串从前面读和从后面读都一样，仅使用若干栈和队列、栈和队列的ADT函数以及若干个int类型和char类型的变量，设计一个算法来判断一个字符串是否为回文。假设字符串从标准输入设备一次读入一个字符，算法的输出结果为true或者false。

可以用一些字符串测试输出结果，如：

"abcdeabcde"， "madamimadam" 等

#include

#include

#define m 100

typedef struct

{

char stack[m];

int top;

}stackstru;

typedef struct

{

char queue[m];

int front;

int rear;

}queuestru;

void main()

{

int stinit(stackstru *s); //初始化顺序栈

int stempty(stackstru *s); //判断栈是否为空

int stpush(stackstru *s,char x); //入栈

char stpop(stackstru *s); //出栈

int quinit(queuestru *q); //初始化循环队列

int quempty(queuestru *q); //判断队列是否为空

int enqueue(queuestru *q,char e); //入队

char dequeue(queuestru *q); //出队

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 数据结构实验

链队列和循环队列

班 级：

学 号：

姓 名：

评语：

成绩： 指导教师：

批阅时间： 年 月 日 《 数据结构 》实验报告

- 1 -

线性数据结构算法实现与应用报告要求

1目的与要求:

1）掌握栈与队列的数据类型描述及特点；

2）掌握栈的顺序和链式存储存表示与基本算法的实现；

3）掌握队列的链式存储表示与基本操作算法实现;

4) 掌握栈与队列在实际问题中的应用和基本编程技巧;

5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性；

7）认真书写实验报告，并按时提交。

2 实验内容或题目

以下题目学生根据自己的兴趣和能力可选作一道作为实验题目：

1） 根据栈数据结构，分别建立一个顺序栈和链式栈并实现其上基本操作（出栈和入栈等）；

2） 根据队列数据结构，分别建立链队列和循环队列，并完成其上的基本操作（出入队列等）；

3） 参考书上表达式求值例题，应用栈的基本操作实现带括号表达式求值运算及其进出栈模拟过程（给出程序执行过程中栈的变化过程）；

4） 阅读P83栈与递归的实现一节内容和3阶汉诺塔问题。使用栈数据结构解决3阶汉诺塔问题，编写程序并模拟栈及其汉诺塔的搬运过程（给出程序执行过程栈的变化过程与圆盘的搬动状态）。

数据结构--栈和队列基础知识

⼀ 概述

栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂

章，做重点讲解。既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这

些内容都会在本章做详细讲解。

使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队

列。

⼆ 栈

2.1 栈的基本概念

同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。

从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：

1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；

2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。拿图 1 的栈来说，从图中数据的存储状态可

判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能

成功取出元素 1。

因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。通常，栈的开⼝端被称为栈顶；相应

地，封⼝端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元

素，下 中的栈底元素为元素 1。

2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：

向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；

从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

2.3 栈的具体实现

栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：

1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。使⽤顺序表模拟栈存储结构常⽤的实现思路，即在顺序表中设

(完整版)《队列》知识点总结

什么是队列？

队列是一种具有特殊操作限制的线性数据结构。它遵循先进先出（FIFO）的原则，即先放入的元素先被取出。

队列的基本操作

1. 入队（enqueue）：将元素插入到队列的尾部。

2. 出队（dequeue）：从队列的头部删除并返回元素。

3. 队列是否为空（isEmpty）：检查队列是否为空。

4. 获取队首元素（getFront）：获取队列头部的元素。

队列的实现方式

队列可以使用数组或链表实现。

数组实现

使用数组实现队列时，可以使用一个数组和两个指针front和rear来表示队列。front指向队列头部，rear指向队列尾部。

入队时，将元素插入到rear指向的位置，并将rear指针后移一位。

出队时，将front指向的元素删除，并将front指针后移一位。

注意：当rear指针和front指针重合时，表示队列为空；当rear指针指向数组的最后一个位置时，表示队列已满。

链表实现

使用链表实现队列时，可以使用一个链表和两个指针head和tail来表示队列。head指向队列头部，tail指向队列尾部。

入队时，将元素添加到tail指向的位置，并将tail指针后移一位。

出队时，将head指向的元素删除，并将head指针后移一位。

注意：当head指针和tail指针重合时，表示队列为空。

队列的应用场景

队列广泛应用于各种场景，例如：

- 消息队列：用于解耦发送者和接收者之间的通信，实现异步处理。 - 高性能缓存：通过队列进行请求的排队和处理，提高缓存的访问效率。

- 进程调度：操作系统使用队列来调度进程的执行顺序。

- 广度优先搜索：队列常用于图的广度优先搜索算法中。

队列的性能分析

使用数组实现队列时，入队和出队操作的时间复杂度均为O(1)。但数组的大小是固定的，当队列满时，无法再插入新元素。

使用链表实现队列时，入队和出队操作的时间复杂度均为O(1)。链表的大小可以动态扩展，不受限制。