数据结构学习笔记9--栈和队列的顺序存储结构

淩亂°似流年 2022-06-07 10:39 260阅读 0赞

**栈和队列的相同点和不同点**：

**相同点**：栈和队列是两种重要的数据结构，也是两种特殊的线性表结构。从数据的逻辑角度看，栈和队列是线性表；从操作的角度来看，栈和队列的基本操作是线性表基本操作的子集，是操作受限制的线性表。

**不同点**：栈是限定仅在表尾进行插入删除的线性表，它的存其特征是后进先出；队列是限定只允许在表的一端进行插入，而在另一端进行删除元素的线性表，它的存取特征是先进先出。

**栈的顺序存储表示与实现**：栈的顺序存储又称顺序栈，它是利用一组地址连续的存储单元一次性存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈的位置。（要设置一个指针是因为栈是在栈顶进行插入删除操作）

#define StackSize<顺序栈的容量> typedef struct snode{ ElemType data[StackSize] int top;}snode;

其中，snode相当于一个栈，data\[i\]存放第i个元素。初始化时，top赋值为-1.

队列的顺序存储表示与实现：与栈一样，队列的顺序存储指的是利用一组地址连续的存储单元存放队列中的元素，并设置两个分别指示队头元素的存储位置和队尾元素的存储位置的变量front,rear,分别称为队头指针和队尾指针。（要设置两个指针是因为要在队尾进行插入操作，而在队头进行删除操作）

**顺序队列的类型变量定义如下**:

#define QueueSize<顺序队列的容量> typedef struct qnode{ ElemType data[QueueSize] int front,rear;}qnode;

初始化时，front和rear均赋值为-1.

假溢出：当rear=QueueSize-1时，队列为满，如果再加入新元素，就会产生溢出。但是这种溢出不是真正的溢出，在数组的前端可能还有空位置（删除操作），所以这是一种假溢出。

为了解决顺序队列中的“假溢出”问题，需要把数组想象成为一个首尾相接的环，称这种数组为“循环数组”，存储在其中的队列称为“循环队列”。

解决队满，队空的判断问题有3种方法：

1.设置一个布尔变量以区别队满还是队空。

2.浪费一个元素的空间，用于区分队满还是队空。

3.是用一个计数器记录队列中的元素个数。（即队列长度）

在使用中，大多采用第2种方法，即队头、队尾指针中有一个指向元素，而另一个指向空元素。

通常约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示在一维数组中的当前位置的前一个位置。

![Center][]

[Center]: /images/20220607/5df6b4ca045a4ce29e4de6dd82089946.png

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构学习：Java中栈和队列的实现

在Java中，我们可以使用`java.util.Stack`和`java.util.Queue`来实现栈和队列。 1. **Stack（堆栈）：**通常只允许在一端进行插入（

电玩女神/ 2024年09月16日 06:03/ 0 赞/ 57 阅读

相关【数据结构】-循环队列2(顺序存储)

顺序存储-循环队列2 1.头文件及类型定义 2.循环队列类型定义 3.函数声明 4.基本操作 4.1 初始化队列 4.2

素颜马尾好姑娘i/ 2023年02月28日 12:56/ 0 赞/ 4 阅读

相关数据结构——栈&队列的python实现

栈&队列的python实现栈的python实现队列的python实现栈的python实现 • 栈（也称下压栈，堆栈）是仅允许在表尾

灰太狼/ 2023年02月14日 02:43/ 0 赞/ 32 阅读

相关队列的顺序存储结构

1.算法原理分析如下图 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZ

迈不过友情╰/ 2022年12月15日 11:23/ 0 赞/ 179 阅读

相关学习笔记栈（一.栈的顺序存储结构）

快考试了来整理。栈中的数据元素用一个预设的足够长度的一维数组来实现 datatype data[MAXSIZE]; 用一个int 类型的数据来作为栈顶的指针

红太狼/ 2022年08月09日 16:42/ 0 赞/ 255 阅读

相关数据结构学习心得——顺序队和链队

队列的定义和栈相反队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允

秒速五厘米/ 2022年06月09日 06:19/ 0 赞/ 299 阅读

相关数据结构学习笔记9--栈和队列的顺序存储结构

栈和队列的相同点和不同点：相同点：栈和队列是两种重要的数据结构，也是两种特殊的线性表结构。从数据的逻辑角度看，栈和队列是线性表；从操作的角度来看，栈和队列的基本操作是线性表

淩亂°似流年/ 2022年06月07日 10:39/ 0 赞/ 261 阅读

相关数据结构之顺序队列的优化

顺序队列的优化我们既然想优化顺序队列，首先得知道目前顺序队列的瓶颈在哪里，那样才能对症下药。顺序队列的瓶颈： 1.线性表的第一个元素作为队头，线性表的最后一个元素作为

￡神魔★判官ぃ/ 2022年05月31日 06:57/ 0 赞/ 239 阅读

相关 Python写数据结构:栈(顺序存储结构)

!/usr/bin/python3.5 __coding:utf-8__ class Stack(): def __init_

偏执的太偏执、/ 2022年05月31日 00:49/ 0 赞/ 213 阅读

相关【数据结构】顺序队列的表示和实现

include<iostream> using namespace std; const int MAXSIZE = 10; typedef s

浅浅的花香味﹌/ 2021年11月26日 15:30/ 0 赞/ 317 阅读