欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 名人名企 > 3-栈、队列、数组

3-栈、队列、数组

2025/4/2 22:49:00 来源:https://blog.csdn.net/m0_73997331/article/details/146883663  浏览:    关键词:3-栈、队列、数组

一-栈

1-概念

栈是只允许在一端进行插入或删除操作的线性表
在这里插入图片描述
后进先出(LIFO)

2-顺序存储实现

//定义一个栈
#define MaxSize 10
typedef struct{ElemType data[MaxSize];//栈顶指针int top;
}SqStack;//初始化栈,栈顶指针也可以初始化为0
void InitStack(SqStack &S){S.top=-1;
}//进栈
bool Push(SqStack &S, ElemType x){//栈满if(S.top==MaxSize-1)return false;//元素进栈,等价于S.data[++S.top]=x;S.top = S.top + 1;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 false;
}void testStack(){SqStack S;InitStack(S);
}

共享栈:两个栈共享同一片内存空间,两个栈从两边往中间增长

//定义
#define MaxSize 10
typedef struct{ElemType data[MaxSize];//0号栈int top0;//1号栈int top1;
}SqStack;//初始化
void InitStack(ShStack &S){S.top=-1;S.top=MaxSize;
}//栈满条件
top0 + 1 == top1

在这里插入图片描述

3-链式存储实现

类似于单链表,单链表有头插法和尾插法,栈的实现是只有头插法。

二-队列

1-概念

只允许在一端进行插入,在另一端删除的线性表
在这里插入图片描述
先进先出(FIFO)

2-顺序实现(循环队列)

//定义
#define MaxSize 10
typedef struct{ElemType data[MaxSize];//队头指针和队尾指针int front,rear;
}SqQueue;//初始化
void InitQueue(SqQueue &Q){Q.rear=Q.front=0;
}void testQueue(){SqQueue Q;InitQueue(Q);
}//入队
bool EnQueue(SqQueue &Q, ElemType x){//判断队满if((Q.rear+1)%MaxSize==Q.front)return false;Q.data[Q.rear]=x;//保证队尾指针在0~MaxSize-1之间循环Q.rear=(Q.rear+1)%MaxSize;return true;
}//出队
bool DeQueue(SqQueue &Q, ELemType &x){//判断队空if(Q.rear==Q.front)return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;
}//获得队头元素
bool GetHead(SqQueue Q, ElemType &x){if(Q.rear==Q.front)return false;x=Q.data[Q.front];return true;
}//队列元素个数
(rear + MaxSize - front) % MaxSize

判断队满队空的其它方法
①设置变量size记录队列当前长度

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;//记录队列当前长度int size;
}SqQueue;void InitQueue(SqQueue &Q){Q.rear=Q.front=0;Q.size=0;
}void testQueue(){SqQueue Q;InitQueue(Q);
}//入队
bool EnQueue(SqQueue &Q, ElemType x){//判断队满if(Q.size==MaxSize)return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;//插入成功size++Q.size++;return true;
}//出队
bool DeQueue(SqQueue &Q, ElemType &x){//判断队空if(Q.size==0)return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;//删除成功Q.size--;return true;
}

②设置变量tag

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;//记录最近进行的是删除还是插入int tag;
}SqQueue;void InitQueue(SqQueue &Q){Q.rear=Q.front=0;Q.tag=0;
}void testQueue(){SqQueue Q;InitQueue(Q);
}//入队
bool EnQueue(SqQueue &Q, ElemType x){//判断队满if(Q.front==Q.rear && Q.tag==1)return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;//每次插入操作成功时,都令tag=1Q.tag=1;return true;
}//出队
bool DeQueue(SqQueue &Q, ElemType &x){//判断队空if(Q.front==Q.rear && Q.tag==0)return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;//每次删除操作成功时,都令tag=0Q.tag=0;return true;
}

3-链式实现

4-双端队列

三-栈和队列的应用

1-栈在括号匹配中的应用

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

3-栈在递归中的应用

4-队列的应用

四-数组和特殊矩阵

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词