首页 > 其他分享 >第3章-栈、队列和数组

第3章-栈、队列和数组

时间：2023-07-05 10:36:36浏览次数：49  
标签：return 队列 top 运算符 数组 front data rear

3.1栈

顺序栈的基本操作

#define MaxSize 10
typedef struct{	//栈的顺序存储类型
    Elemtype data[MaxSize];		//静态数组存放栈中元素	
    int top;				//栈顶指针
}SqStack;
//Sq:sequence--顺序
//初始化栈
void InitStack(SqStack &S)
{
    S.top=-1;		//初始化栈顶指针
}
//判断栈空
bool StackEmpty(SqStack S)
{
    if(S.top==-1)	//栈空
    	return true;
    else return false;//不空
}
//新元素入栈
bool Push(SqStack &S,ElemType e)
{
    if(S.top==MaxSize-1)	
        return false;	//栈满报错
    S.top=S.top+1;		//这两句语句也相当于S.data[++S.top]=x;先自增再赋值
    S.data[S.top]=x;
    return true;
}
//出栈操作
bool Pop(SqStack &S,ElemType x)
{
    if(S.top==-1)	//栈为空报错
        return false;
    x=S.data[S.top];//这两句也相当于x=S.data[S.top--]
    S.top=S.top-1;
    return true;
}
//读栈顶元素
bool GetTop(SqStack S,ElemType &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top];
	return true;
}
void testStack(){
    SqStack S;		//声明一个顺序栈（分配空间）
    InitStack(S);
    //...后续操作...
}

代码试验

#include<iostream>
#define MaxSize 10
using namespace std;
typedef int ElemType;
typedef struct{
    int data[MaxSize];		//静态数组存放栈中元素	
    int top;				//栈顶指针
}SqStack;
//Sq:sequence--顺序
//初始化栈
void InitStack(SqStack &S)
{
    S.top=-1;		//初始化栈顶指针
}
//判断栈空
bool StackEmpty(SqStack S)
{
    if(S.top==-1)	//栈空
    	return true;
    else return false;//不空
}
//新元素入栈
bool Push(SqStack &S,int x)
{
    if(S.top==MaxSize-1)	
        return false;	//栈满报错
    S.top=S.top+1;		//这两句语句也相当于S.data[++S.top]=x;先自增再赋值
    S.data[S.top]=x;
    return true;
}
//出栈操作
bool Pop(SqStack &S,int &x)
{
    if(S.top==-1)	//栈为空报错
        return false;
    x=S.data[S.top];
    S.top=S.top-1;
    return true;
}
//读栈顶元素
bool GetTop(SqStack S,ElemType &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top];
	return true;
}
void stackprint(SqStack S)
{
	while(S.top!=-1)
	{
		ElemType x;
		Pop(S,x);
		cout<<x<<" ";
	}	
}
int main()
{
	SqStack S;
	InitStack(S);
	for(int i=1;i<=4;i++)
	{
		Push(S,i);
	}
	stackprint(S);//输出4 3 2 1
	return 0;
	
}

若栈顶指针初始化为S.top=0,即指向栈顶元素的下一位置，那么入栈操作就为S.data[S.top++]=x,出栈操作就为x=S.data[--S.top];

栈满栈空条件也会发生变化。

总共的出栈序列，若有n个元素：出栈序列有$C_{2n}^{n}$/ (n+1)种，这个数称之为卡特兰数

共享栈

#define Maxsize 10
typedef struct{
    ElemType data[MaxSize];
    int top0;			//0号栈顶指针
    int top1;			//1号栈顶指针
}ShStack;
//初始化栈
void InitStack(ShStack &S)
{
    S.top0=-1;		//初始化栈顶指针
    S.top1=Maxsize;
}

判断栈满：top0+1=top1;

只有在整个存储空间被占满时才发生上溢

链栈

通常采用单链表实现，并规定所有操作都是在单链表的表头进行

栈的链式存储类型

typedef struct Linknode{
    ElemType data;			//数据域
    struct Linknode *next;	//指针域
}*LisStack;					//栈类型定义

题目总结：

1.栈和队列具有相同的逻辑结构

逻辑结构分为：

  • 线性结构：一对一（栈，队列，线性表）
  • 非线性结构：树形结构（一对多：一般树，二叉树）；图状结构（多对多：有向图，无向图）

2.只有头结点的单循环链表，找表尾结点需要遍历一次链表，时间复杂度为O（n）

3.2 队列

1.队列的基本操作

队列的存储类型

#define Maxsize 10		//定义队列中元素的最大个数
typedef int Elemtype;
typedef struct{
	Elemtype data[Maxsize];//静态数组存放队列元素
	int front,rear;			//队头指针和队尾指针
}SqQueue;

初始化

//初始化队列
void InitQueue(SqQueue &Q)
{
	// 初始时 队头，队尾指针指向0
	Q.rear=Q.front=0;
}

判断队列是否为空

//判断队列是否为空
bool QueueEmpty(SqQueue Q)
{
	if(Q.rear==Q.front) //相等则为空
		return true;
	else return false;
}

入队操作

//入队操作
bool EnQueue(SqQueue &Q,Elemtype x)
{
	if(Q.front==(Q.rear+1)%Maxsize)	//判断队满
		return false;
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%Maxsize;	//队尾指针加一取模
	return true;
}

出队操作


//出队操作
bool DeQueue(SqQueue &Q,Elemtype &x)
{
	if(Q.front==Q.rear)	//判断队空 
		return false;
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%Maxsize;//队头指针加一取模
	return true;
}

队中元素个数:

(rear+Maxsize-front)%Maxsize

若队尾指针指向的是最后一个元素

rear初始=n-1

Q.rear=(Q.rear+1)%Maxsize

判空：(Q.rear+1)%Maxsize==Q.front

2.多种方法判断队满队空

（1）如上所述

（2）定义一个size变量

typedef struct{
	Elemtype data[Maxsize];//静态数组存放队列元素
	int front,rear;			//队头指针和队尾指针
	int size;		//添加size变量来记录队列长度
}SqQueue;

插入成功,size++;

插入失败，size--；

初始化时，front=rear=0,size=0;

队空判断size=0;

队满判断size=Maxsize；

（3）设置tag变量

每次删除操作成功时，令tag=0;

每次插入操作成功时，令tag=1;

typedef struct{
	Elemtype data[Maxsize];//静态数组存放队列元素
	int front,rear;			//队头指针和队尾指针
	int tag;		
}SqQueue;

初始化时，初始化时，front=rear=0,tag=0;

只有删除操作才会导致队列为空；

故队空条件为：front==rear&&tag==1

只有插入操作才会导致队列为满；

故队满条件为：front==rear&&tag==0

3.队列的链式实现

存储类型

typedef struct LinkNode{	//链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{			//链式队列
    LinkNode *front,*rear;//队列的队头和队尾指针
}LinkQueue;

初始化（带头结点）

//初始化队列
void InitQueue(LinkQueue &Q)
{
    //初始化时，front、rear都指向头结点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
        return true;
    else return false;
}

void testLinkQueue()
{
    LinkQueue Q;//声明一个队列
    InitQueue(Q);//初始化一个队列
    ......
}

初始化（不带头结点）

//初始化队列
void InitQueue(LinkQueue &Q)
{
    //初始化时，front、rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{
    if(Q.front=NULL)
        return true;
    else return false;
}

入队(带头结点)

void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));//分配一个新的结点空间
    s->data=e;
    s->next=NULL;
    Q.rear->next=s;	//新结点插入到rear之后
    Q.rear=s;		//修改表尾表尾指针
}

入队(不带头结点)

void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL)//在空队列中插入第一个元素
    {
        Q.front=s;	//修改队头队尾指针
        Q.rear=s;
    }
    else
    {
        Q.rear->next=s;
        Q.rear=s;
    }
}

出队（带头结点）

bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.front==Q.rear)	//空队列
        return false;
    LinkNode *p=Q.front->next;
    x=p->data;	//用变量x返回队头元素
    Q.front->next=p->next;//修改头结点的next指针
    if(Q.rear==p)	//若此结点为最后一个结点
        Q.rear=Q.front;
    free(p);
}

出队（不带头结点）

bool DeQueue(LinkQueue &Q,Elemtype &x)
{
    if(Q.front==NULL)	//空队列
        return false;
    LinkNode *p=Q.front;	//用p指针指向此次需要出队的结点
    x=p->data;
    Q.front=p->next;
    if(Q.front==p)		//要出队的结点是最后一个结点
    {
        Q.front==NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;
}

3.3 栈和队列的应用

1.括号匹配算法

#include<iostream>
#include<string.h>
#define MaxSize 10
using namespace std;
typedef char ElemType;
typedef struct{
    int data[MaxSize];		//静态数组存放栈中元素	
    int top;				//栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S)
{
    S.top=-1;		//初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S)
{
    if(S.top==-1)	//栈空
    	return true;
    else return false;//不空
}

//新元素入栈
bool Push(SqStack &S,int x)
{
    if(S.top==MaxSize-1)	
        return false;	//栈满报错
    S.top=S.top+1;		//这两句语句也相当于S.data[++S.top]=x;先自增再赋值
    S.data[S.top]=x;
    return true;
}
//出栈操作
bool Pop(SqStack &S,ElemType &x)
{
    if(S.top==-1)	//栈为空报错
        return false;
    x=S.data[S.top];
    S.top=S.top-1;
    return true;
}
//读栈顶元素
bool GetTop(SqStack S,ElemType &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top];
	return true;
}

//元素出栈并打印
void stackprint(SqStack S)
{
	while(S.top!=-1)
	{
		ElemType x;
		Pop(S,x);
		
		cout<<x<<" ";
	}	
}

//括号匹配
bool bracketCheck(char str[],int length)//length表示这段字符串的长度
{
	SqStack S;
	InitStack(S);
	for(int i=0;i<length;i++)
	{
		if(str[i]=='{' || str[i]=='[' || str[i]=='(')
			Push(S,str[i]);	//扫描左括号并入栈
		else{	//匹配到右括号时
			if(StackEmpty(S))	//若栈为空，匹配失败
				return false;
			
			char topElem;
			Pop(S,topElem);	//栈顶元素出栈
			if(str[i]==')' && topElem!='(')
				return false;
			if(str[i]==']' && topElem!='[')
				return false;
			if(str[i]=='}' && topElem!='{')
				return false;
		}
	}
	return StackEmpty(S);//检索完所有括号之后，栈空说明匹配成功
}
int main()
{
	char str[MaxSize];	
	cin>>str;
	//cout<<str<<endl;
	int length=strlen(str);
	//cout<<length<<endl;
	cout<<bracketCheck(str,length);
	return 0;
}

2.栈在表达式求值中的应用

中缀、后缀、前缀表达式

中缀表达式 后缀表达式 前缀表达式
运算符在两个操作数中间 运算符在两个操作数后面 运算符在两个操作数前面
a+b ab+ +ab
a+b-c ab+c- -+abc
a+b-c*d ab+cd*- -+ab*cd

中缀转后缀的手算方法

（1）确定中缀表达式中各个运算符的运算顺序（运算顺序可能不唯一，因此对应的后缀表达式可能也不唯一）

（2）选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数

（3）如果还有运算符没被处理，就继续（2）

“左优先”原则：只要左边的运算符能先计算，就优先算左边的(可保证运算顺序唯一)

例1：

中缀表达式：((15÷(7-(1+1)))×3)-(2+(1+1))

后缀表达式：15711+-÷3× 211++ - 也就是：15711+-÷3× 211++ -

例2：

中缀表达式：A+B*(C-D)-E/F

后缀表达式：ABCD-*+EF/-

后缀表达式的计算（手算）

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合为一个新的操作数

注意：两个操作数的左右顺序（运算时是有左右顺序的）

后缀表达式的计算（机算）

用栈实现后缀表达式的计算：

（1）从左往右扫描所有元素

（2）若扫描到操作数则压入栈，并回到（1），否则执行（3）

（3）若扫描到运算符，则弹出两个栈顶元素（先弹出的是右操作数），执行相应运算，运算结果压回栈顶，回到（1）

中缀转前缀的手算方法

（1）确定中缀表达式中各个运算符的运算顺序

（2）选择下一个运算符，按照[运算符 左操作数 右操作数 ]的方式组合成一个新的操作数

（3）如果还有运算符没被处理，就继续（2）

“右优先”原则：只要右边的运算符能先计算，就优先算右边的

前缀表达式的计算（机算）

用栈实现后缀表达式的计算：

（1）从右往左扫描所有元素

（2）若扫描到操作数则压入栈，并回到（1），否则执行（3）

（3）若扫描到运算符，则弹出两个栈顶元素（先弹出的是左操作数），执行相应运算，运算结果压回栈顶，回到（1）

中缀转后缀（机算）

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符

从左到右处理各个元素，直到末尾。可能遇到三种情况：

  1. 遇到操作数。直接加入后缀表达式。
  2. 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符，并加入后缀表达式，直到弹出"（"为止。“（”不加入后缀表达式
  3. 遇到运算符。先依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到"("或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

中缀表达式的计算（用栈实现）

用栈实现中缀表达式的计算：

初始化两个栈：操作数栈和运算符栈

若扫描到操作数栈，压入操作数栈

若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

3.队列的应用

图的广度优先搜索，缓冲区，树的层序遍历，多用户引起的资源竞争问题

3.4数组和特殊矩阵

特殊矩阵的压缩存储

对称矩阵

策略：只存储主对角线+下三角区

按行优先原则将各元素存入一维数组中，数组大小为(1+n)*n/2

i>j时，按行优先原则，ai,j是第几个元素，应该是i*(i-1)/2+j,下标k为i*(i-1)/2+j-1

j>i，利用对称特性，ai,j=aj,i 此时，k=j*(j-1)/2+i-1

三角矩阵的压缩存储

下三角矩阵：除了主对角线和下三角区，其余的元素都相同

压缩存储策略：按行优先原则将下三角区及对角线元素存入一维数组中。并在最后一个位置存储常量C

k=i*(i-1)/2+j-1 ----i≤j（下三角区和主对角线元素）

k=(n-1)*n/2 ----i>j（上三角区元素）

上三角矩阵：除了主对角线和上三角区，其余的元素都相同

数组下标

k=(i-1)*(2n-i+2)/2+(j-i) ----i≤j（上三角区和主对角线元素）

k=(n-1)*n/2 ----i>j（下三角区元素）

三对角矩阵

当|i-j|>1时，有ai,j=0，数据元素的总个数就为3n-2

按行优先原则，ai,j是第几个元素？

前i-1行共有3(i-1)-1个元素

ai,j是第i行的j-i+2个元素

故ai,j是2i+j-2个元素，下标k则为2i+j-3

已知下标为k时，得到坐标i,j

3（i-1）-1<k+1≤3i-1

i≥（k+2）/3 ----向上取整，再由k与i，j之间的关系推出j

稀疏矩阵

定义：非零元素远远少于矩阵元素的个数

压缩存储策略：

顺序存储——三元组<行，列，值>

十字链表法

标签：return,队列,top,运算符,数组,front,data,rear
From： https://www.cnblogs.com/Jinx8823/p/17527830.html

相关文章

  • LeetCode 周赛 352（2023/07/02）一场关于子数组的专题周赛
    本文已收录到AndroidFamily，技术和职场问题，请关注公众号[彭旭锐]和[BaguTreePro]知识星球提问。往期回顾：LeetCode单周赛第350场·滑动窗口与离散化模板题单周赛352概览T1. 最长奇偶子数组（Easy）标签：滑动窗口、枚举T2. 和等于目标值的质数对（Medium）标签：质......
  • LeetCode 108. 将有序数组转换为二叉搜索树
    题目链接：LeetCode108.将有序数组转换为二叉搜索树题意：给你一个整数数组nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过1」的二叉树。解题思路：(递归)O(n)递归建立整......
  • 消息队列三兄弟谁主沉浮
    简介消息队列主要为了异步场景下实现上下游解耦功能：在传统场景中，上游产生一条消息，比如用户下单了一件商品，系统创建了对应的订单，需要通知下游的物流、支付等系统进行后续处理；消息队列可以使得上游系统（订单）和下游系统（支付/物流等）解耦，上游只管向消息队列中投递消息即可，下游订阅消息......
  • Java数组和数据存储
    数组的定义数组是相同类型数据的有序集合。其中，每一个数据称作一个元素，每个元素可以通过一个索引（下标）来访问它们。数组的四个基本特点：1.长度是确定的。数组一旦被创建，它的大小就是不可以改变的。2.其元素的类型必须是相同类型，不允许出现混合类型。3.数组类型可以是任何数据类......
  • 数组元素积的符号
    已知函数 signFunc(x)将会根据x的正负返回特定值：如果x是正数，返回1。如果x是负数，返回-1。如果x是等于0，返回0。给你一个整数数组nums。令product为数组nums中所有元素值的乘积。返回signFunc(product)。示例1：输入：nums=[-1,-2,-3,-4,3,2,1]输......
  • JavaScript 数组的 reduce 方法有哪些应用
    JavaScript数组的reduce方法有哪些应用JavaScript中的reduce()方法可以用于将数组元素汇总为单个值，它接受一个回调函数作为参数，并在每个数组元素上调用该函数，以便将其累加到一个累加器变量中。下面是一些实际应用：数组求和：使用reduce()方法将数组元素相加，从而计算数组的总......
  • 指针遍历二维数组
    #include<stdio.h>intmain(){intarr[3][3]={{1,2,3},{4,5,6},{7,8,9}};int(*p)[3]=arr;inti=0;for(i=0;i<3;i++){intj=0;for(j=0;j<3;j++){printf("%d",*((*(p+i))+j));}printf("\......
  • Java数组
    Java数组数组概述1.数组概述1.相同类型变量的有序集合2.数组的声明和创建1.dataType[]arrayRefVar2.dataType[]arrayRefVar=newdataType[arraySize]内存分析1.声明数组int[]array=null;在栈中声明了array2.创建数组array=newint[10];在......
  • Vue 数组中出现__ob__: Observer无法取值[已解决]
    Vue数组中出现__ob__:Observer无法取值[已解决]代码如下解决办法加一个setTimeoutcreated(){setTimeout(()=>{//这里就写你要执行的语句即可，先让数据库的数据加载进去数组中你在从数组中取值就好了},800)}改完之后就可以了......
  • 单调栈单调队列学习笔记
    目录：单调栈1.1概念1.2实现1.3时间复杂度分析1.4应用单调队列1.1概念1.2实现1.3时间复杂度分析1.4应用习题1.单调栈1.1概念单调栈为满足单调性的栈结构，栈内元素满足单调性。1.2实现为满足单调性，在遍历到一个元素时，若此时加入后栈不满足单调性，则弹出栈......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99