【数据结构】栈和队列
前言
栈和队列是两种重要的线性结构，从数据结构上来看，它们也是线性表。是操作受限的线性表。但从数据类型上来看，则大不相同。
unreal
栈（Stack）
定义
书本定义：
万兆
栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。不含元素的空表称为空栈。
技术学习
《大话数据结构》的定义：
进程间通信
栈的表示和实现
两种存储表示方法：栈的顺序存储表示—-顺序栈 栈的链式表示—–链栈
我们以顺序栈为例子进行栈的表示和实现
社交
栈的顺序存储表示
typedef struct{
char *base;//栈底指针
char *top;//栈顶指针
int stacksize;//当前已分配的存储空间
}SqStack;
栈的初始化
#define SIZE 100;//存储空间初始分配量
int init(SqStack &s){
s.base=(char*)malloc(SIZE*sizeof(char));
if(!s.base)//开辟存储空间失败则停
exit(0);
s.stacksize=100;
s.top=s.base;
return 1;
}
元素进栈
void push(SqStack &s,char e){
//首先判断栈是否满，若满了，则需要申请新的存储空间
if(s.top-s.base>=s.stacksize){
//指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）,返回调整之后的空间的起始位置地址
s.base=(char *)realloc(s.base,(s.stacksize+10)*sizeof(char));
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;//将值赋给s.top指向的位置，s.top++
}
输出出栈序列
void Out(SqStack &s){
if(s.top!=s.base)
printf("%c ",s.top);
s.top++;
}
释放栈
int Clear(SqStack &s){
if(!s.base)
return 0;
free(s.base);//释放内存空间
s.base=NULL;
s.top=NULL;
s.stacksize=0;
return 1;
}
完整代码如下：
社交电子
//栈的基本操作
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define SIZE 100
#define CREAT 10;
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack;
//初始化栈
int initstack(SqStack &s){
s.base=(char *)malloc(SIZE*sizeof(char));
if(!s.base)
exit(0);
s.stacksize=SIZE;
s.top=s.base ;
return 1;
}
//判断栈s是否非空
void isempty(SqStack &s){
if(s.top==s.base)
printf("该栈是空的\n");
else
printf("该栈不是空的\n");
}
//依次进栈元素 a,b,c,d,e
void Push(SqStack &s,char e){
if(s.top-s.base >=s.stacksize ){
s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char));
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;//将值赋给s.top指向的位置，s.top++
}
//输出栈的长度
int StackLength(SqStack s){
return s.top-s.base ;
}
//输出从栈顶到栈底元素
void StackTraverse(SqStack &s){
while(s.base!=s.top)
printf("%c ",*--(s.top));
printf("\n");
}
//输出出栈序列
void OutStack(SqStack &s){
if(s.top!=s.base){
printf("%c ",s.top);
s.top--;
}
// printf("\n");
}
//释放栈
int ClearStack(SqStack &s){
if(!s.base)
return 0;
free(s.base);
s.base=NULL;
s.top =NULL;
s.stacksize =0;
return 1;
}
int main()
{
SqStack h;
initstack(h);
isempty(h);
printf("依次进栈元素 a,b,c,d,e\n");
Push(h,'a');
Push(h,'b');
Push(h,'c');
Push(h,'d');
Push(h,'e');
isempty(h);
printf("该栈的长度为：");
printf("%d\n",StackLength(h));
printf("输出从栈顶到栈底元素：");
StackTraverse(h);
OutStack(h);
isempty(h);
ClearStack(h);
return 0;
}
结果：
MyBatisPlus
栈的应用举例
数制转换
十进制数N和其他d进制数的转化
一个简单算法：
N=(N div d)*d+N mod d
例如十进制的（1248）=八进制的（2504）
题目要求：对于输入的任意一个非负十进制整数，打印输出其等值的八进制数。
遗传算法
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define SIZE 100
#define CREAT 10;
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack;
//初始化栈
int initstack(SqStack &s){
s.base=(int *)malloc(SIZE*sizeof(int));
if(!s.base)
exit(0);
s.stacksize=SIZE;
s.top=s.base ;
return 1;
}
//进栈
void Push(SqStack &s,int e){
if(s.top-s.base >=s.stacksize ){
s.base=(int*)realloc(s.base,(s.stacksize+10)*sizeof(int));
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;//将值赋给s.top指向的位置，s.top++
}
//元素出栈
int Pop(SqStack &s,int &e){
if(s.top==s.base)
return 0;
s.top--;
e=*s.top;
return 1;
}
//判断是否为空
int StackEmpty(SqStack &S){
if(S.top==S.base)
return 1;
else
return 0;
}
//对于输入的任意非负十进制整数，打印与其等值的八进制数
void conversion(){
int N,e;
SqStack S;
initstack(S);
scanf("%d",&N);
while(N){
Push(S,N%8);
N=N/8;
}
while(!StackEmpty(S)){
Pop(S,e);
printf("%d",e);
}
}
int main()
{
conversion();
return 0;
}
结果：
对称加密
括号匹配的检验
行编辑程序
迷宫求解
表达式求值
栈与递归的实现
队列
定义
队列是一种先进先出（FIFO）的线性表。在队列中，允许插入的一端叫做队尾，允许删除的一端叫做队头。
《大话数据结构》的定义：
魔百盒固件
链队列–队列的链式表示和实现
为了操作方便，添加一个头结点，并令头指针指向头结点。
ios拍照旋转
单链队列的表示
typedef struct QNode{
char data ;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
初始化
void init(LinkQueue &Q){
//构造一个空队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit(0);//存储分配失败
Q.front->next=null;
}
销毁
void destory(LinkQueue &Q){
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
}
插入新元素
void queue(LinkQueue &Q,char e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(0);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
删除队头元素
void dequeue(LinkQueue &Q,char &e){
if(Q.front==Q.rear)
printf("队列已空，无法执行删除操作！");
QueuePtr p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
完整代码如下：
虚拟机
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef struct QNode{
char data ;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
void init(LinkQueue &Q){
//构造一个空队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit(0);//存储分配失败
Q.front->next=NULL;
}
void destory(LinkQueue &Q){
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
}
void queue(LinkQueue &Q,char e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(0);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
void dequeue(LinkQueue &Q,char &e){
if(Q.front==Q.rear)
printf("队列已空，无法执行删除操作！");
QueuePtr p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
int size(LinkQueue &Q){
int size=0;
QueuePtr exp=Q.front;
while(exp){
size++;
exp=exp->next;
}
return size;
}
int main(){
LinkQueue Q;
printf("初始化顺序队列\n");
init(Q);
printf("向数列插入元素abcde\n");
queue(Q,'a');
queue(Q,'b');
queue(Q,'c');
queue(Q,'d');
queue(Q,'e');
printf("输出该队列个数\n");
printf("%d\n",size(Q)-1);
printf("销毁该队列\n");
destory(Q);
printf("输出该队列个数\n");
printf("%d\n",size(Q));
return 0;
}
结果：
yolov7
循环队列–队列的顺序表示和实现
把队列的这种头尾相接的顺序存储结构称为循环队列。
big data
《大话数据结构》
由此可见，在C语言中不能使用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度。
bootloader
队列的顺序存储结构（循环队列）
typedef struct{
char *base;//初始化的动态分配存储空间
int front;//头指针
int rear; //尾指针
}SqQueue;
初始化
#define SIZE 100//定义该循环队列存储空间为100
int init(SqQueue &Q){
Q.base=(Elemtype*)malloc(SIZE*sizeof(Elemtype));
if(!Q.base)
exit(0);
Q.front=0;
Q.rear=0;
return 1;
}
队列的长度
int Queuelength(SqQueue &Q){
return (Q.rear-Q.front+SIZE)%SIZE;
}
插入新元素
int push(SqQueue &Q,int e){
if((Q.rear+1)%SIZE==Q.front)
{
printf("该队列已满，不可插入新元素");
return 0;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%SIZE;
return 1;
}
出队一个元素，输出该元素
int Out(SqQueue &Q,Elemtype &e){
if(Q.front==Q.rear)
return 0;
e=Q.base[Q.front];
Q.front=(Q.front+1)%SIZE;
return 1;
}
输出出队序列
void print(SqQueue &Q){
int i=Q.front;
for(;i<Q.rear;i++)
print("%c ",Q.base[i]);
}
释放队列
void clear(SqQueue &Q){
if(Q.base)
free(Q.base);
Q.base=NULL;
Q.front=Q.rear=0;
}
完整代码：
ai
//顺序队列的基本操作
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define SIZE 100
typedef char Elemtype;
typedef int Status;
typedef struct{
Elemtype *base;//初始化的动态分配存储空间
int front;
int rear;
}SqQueue;
// 初始化队列q
Status initQueue(SqQueue &Q){
Q.base=(Elemtype*)malloc(SIZE*sizeof(Elemtype));
if(!Q.base)
exit(0);
Q.front=0;
Q.rear=0;
return 1;
}
//判断队列q是否非空
void isempty(SqQueue &Q)
{
if(Q.rear==Q.front)
printf("该队列为空\n");
else
printf("该队列不为空\n");
}
//依次进队列元素a,b,c
Status Push(SqQueue &Q,Elemtype e){
if((Q.rear+1)%SIZE==Q.front)
{
printf("抱歉，这个队列已经满了，无法插入新的元素");
return 0;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%SIZE;
return 1;
}
//出队一个元素，输出该元素
Status OutQueue(SqQueue &Q,Elemtype &e){
if(Q.front==Q.rear)
return 0;
e=Q.base[Q.front];
Q.front=(Q.front+1)%SIZE;
return 1;
}
//输出队列q的元素个数
Status Queuelength(SqQueue &Q){
return(Q.rear-Q.front+SIZE)%SIZE;
}
//输出出队序列
void Print(SqQueue &Q)
{
int i=Q.front;
for(;i<Q.rear;i++)
printf("%c ",Q.base[i]);
}
//释放队列
Status Clear(SqQueue &Q){
if(Q.base)
free(Q.base);
Q.base=NULL;
Q.front=Q.rear=0;
return 1;
}
int main(){
SqQueue q;
Elemtype e;
printf("初始化队列q\n");
initQueue(q);
printf("判断队列q是否非空\n");
isempty(q);
printf("依次进队列元素a,b,c\n");
Push(q,'a');
Push(q,'b');
Push(q,'c');
OutQueue(q,e);
printf("出队的元素为%c\n",e);
printf("输出队列q的元素个数:");
printf("%d",Queuelength(q));
printf("\n");
printf("依次进队列元素d,e,f\n");
Push(q,'d');
Push(q,'e');
Push(q,'f');
printf("输出队列q的元素个数:");
printf("%d",Queuelength(q));
printf("\n");
printf("输出出队序列：");
Print(q);
printf("\n");
printf("释放队列\n");
Clear(q);
return 0;
}
结果：
苹果ios解锁大师
声明：本站博客内容版权均属于原作者所有，这里所提供资源均只能用于参考学习用，书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
