这篇文章主要介绍“c++的栈和队列怎么实现”,在日常操作中,相信很多人在c++的栈和队列怎么实现问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”c++的栈和队列怎么实现”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
创新互联公司是一家专业从事成都网站设计、网站建设、网页设计的品牌网络公司。如今是成都地区具影响力的网站设计公司,作为专业的成都网站建设公司,创新互联公司依托强大的技术实力、以及多年的网站运营经验,为您提供专业的成都网站建设、营销型网站建设及网站设计开发服务!
栈是限制在表一端进行插入和删除操作的线性表。允许进行插入、删除操作的这一端称为栈顶(Top),另一个固定端称为栈底。
例如栈中有三个元素,进栈的顺序是a1、a2、a3,当需要出栈时顺序为a3,a2,a1, 所以栈又称“后进先出”或“先进后出”的线性表,简称“LIFO表”或“FILO表”。
1.1:栈的基本运算:
(1)栈初始化:
Init_Stack(s)
(2)判栈空:
Empty_Stack(s)
(3)入栈:
Push_Stack(s,x)
(4)出栈:
Pop_Stack(s)
(5)读栈顶元素:
Top_Stack(s)
1.2 栈的存储结构和基本运算
由于栈是运算受限的线性表(各个元素依次存放在一组地址连续的存储单元中),因此线性表的存储结构对栈也是适用的,只是操作不同而已。
(1)顺序栈
利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义,栈中的数据元素用一个预设的足够长度的一维数组来实现:datatype data[MAXSIZE],栈底位置可以设置在数组的任意一个端点,而栈顶随着插入和删除而变化的,用int top来作为栈顶的指针,指明当前栈顶的位置,同样将data和top封装在一个结构中,顺序栈的类型描述如下:
typedef struct{ datatype data[MAXSIZE]; int top; }SeqStack
定义一个指向顺序栈的指针。
SeqStack *s;
通常将0下标端设为栈底,这样空栈时栈顶指标top=-1;入栈时,栈顶指针加1,即s->top++;出栈时,栈顶指针减1,即s->top--。栈顶指针与栈中数据元素如下图所示:
基本操作实现如下:
1)置空栈:首先建立栈空间,然后初始化栈顶指针。
SeqStack *Init_SeqStack() { SeqStack *s; s=malloc(sizeof(SeqStack)); s->top = -1; return s; }
2)判空栈:
int Empty_SeqStack(SeqStack *s){ if(s->top ==-1){ return 1; } else{ return 0; } }
3)入栈:
int Push_SeqStack(SeqStack *s,datatype x){ if(s->top ==MAXSIZE-1){ //防止空间溢出——上溢 return 0; }else{ s->top++; s->data[s->top]=x; return 1; } }
4)出栈:
int Pop_SeqStack(SeqStack *s,datatype *x){ if(Empty_SeqStack)(s)){ return 0; } else{ *x =s ->data[s->top]; s->top--; return 1; } }
5)取栈顶元素:
datatype Top_SeqStack(SeqStack *s){ if(Empty_SeqStack(s)){ return 0; } else{ return (s->data[s->top]); } }
(2)链栈
用链式存储结构实现的栈称为链栈。通过链栈用单链表表示,因此其结点结构与单链表的结点结构相同,在此用LinkStack表示:既有:
typedef struck node{ datatype data; struct node *next; }StackNode * LinkStack;
基本操作如下:
1)置空栈:
LinkStack Init_LinkStack(){ return NULL; }
判栈空:
int Empty_LinkStack(LinkStack top){ if(top==NULL) return 1; else return 0; }
3)入栈:
LinkStack Push_LinkStack(LinkStack top , datatype x){ StackNode *s; s = malloc(sizeof(StackNode)); s->data=x ; s->next=top; top=s; return top; }
出栈:
LinkStack Pop_LinkStack(LinkStack top , datatype *x){ StackNode *p; if(top ==NULL) return NULL; else *x = top->data; p =top; top= top->next; free(p); return top; }
2.1:定义及基本运算
栈是讲一种先进后出的数据结构,而在实际问题中还经常使用一种“先进先出”的数据结构:即插入在表一端进行,而删除在表的另一端进行,这叫数据结构被称为队列(Queue [kju])。允许插入的一端被称为队尾(rear),允许删除的一端成为队头(front)。如一个队列入队顺序依次为:a1;a2;a3;a4;a5,出队时顺序将依然是a1;a2;a3;a4;a5。就像超市排队的人结账。
队列也是一种运算受限的线性表,又叫先进先出表,简称“FIFO表”。
基本操作:
(1)初始化:
Init_Queue(q)
(2)入队操作:
In_Queue(q,x)
(3)出队操作:
Out_Queue(q,x)
(4)读队头元素:
Front_Queue(q,x)
(5)判队空操作:
Empty_Queue(q)
2.2:队列的存储结构和基本运算
(1)顺序队
顺序存储的队列称为顺序队。因为队列的队头和队尾都是活动的,因此,除了队列的数据区外还有队头、队尾两个指针。顺序队定义如下:
define MAXSIZE 100;//容量 typedef stuct{ datatype data[MAXSIZE];//存储空间 int rear,font;//队尾指针 }SeQueue; SeQueue *sq;//指针 sq = malloc(sizeof(SeQueue))); //申请存储空间 sq ->data[0]~ sq->data[MAXSIZE -1];; //存储区 sq->front //队头 sq ->rear //队尾 sq->front =sq->rear = -1 ; //置空 //sq->rear++;//顺序队 sq->rear = (sq->rear+1) % MAXSIZE;//循环队 sq->data[sq->rear] =x; //入队 //sq->front++; sq->front = (sq ->front+1)%MAXSIZE; x=sq->data[sq->front]; //出队 m =(sq->rear) - (q->font);//队长
1)置空队:
c_SeQueue* Init_SeQueue(){ q =malloc(sizeof(c_SeQueue)); q ->font =q ->rear =-1; q->num = 0; return q; }
2)入队:
int In_SeQueue(c_SeQueue *q , datatype x){ if(num == MAXSIZE){ return -1; } else{ q ->rear =(q ->rear+1)%MAXSIZE: q ->data[q ->rear] = x; num++; return 1; } }
3)出队:
int Out_SeQueue(c_SeQueue *q , datatype *x){ if(num ==0){ return -1; } else{ q->fornt =(q->front+1)%MAXSIZE; *x =q ->data[q->front];//读出队头元素 num--; return 1; } }
4)判空:
int Empty_Sequeue(c_SeQueue *q){ if(num==0) return 1; else return 0; }
(2) 链队列
链式存储的队列称为链队列。和链栈类似,链队列可以用单链表来实现,根据队的FIFO原则,为了操作上的方便,可以分别设置一个头指针和一个尾指针。
链队列定义如下:
typedef struct node{ datatype data; struct node next; }QNode; typedef struct{ QNode *front , *rear; }LQueue; LQueue *q; //定义一个指向链队列的指针
1)创建一个带头结点的空队:
LQueue *Init_LQueue(){ LQueue *q,*p; q = malloc(sizeof(LQueue));//申请头尾指针结点 p = malloc(sizeof(QNode)); //申请链队头结点 p->next = NULL; q->front = p; q->rear =p ; return q; }
2)入队:
void In_LQueue(LQueue *q , datatype x){ QNode *p; p = malloc(sizeof (QNode));//申请新结点 p->data =x; p->next =NULL; q->rear ->next =p; q->rear =p; }
3)判队空:
int Empty_LQueue(LQueue *q){ if(q->front ==q->rear) return 0; else return 1; }
4)出队:
int Out_LQueue(LQueue *q , datatype *x){ QNode *p; if(Empty_Lqueue(q)){ return 0; } else{ p=q->front->next; q->front->next=p->next; *x = p->data;//队头元素放x中 free(p); if(q->front->next ==NULL){//只有一个元素时,出队后队空 q->rear = q->front; return 1; } }
到此,关于“c++的栈和队列怎么实现”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!