c++的栈和队列怎么实现
这篇文章主要介绍“c++的栈和队列怎么实现”，在日常操作中，相信很多人在c++的栈和队列怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”c++的栈和队列怎么实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
创新互联公司是一家专业从事成都网站设计、网站建设、网页设计的品牌网络公司。如今是成都地区具影响力的网站设计公司,作为专业的成都网站建设公司,创新互联公司依托强大的技术实力、以及多年的网站运营经验,为您提供专业的成都网站建设、营销型网站建设及网站设计开发服务！
第一节：栈（Stack）
栈是限制在表一端进行插入和删除操作的线性表。允许进行插入、删除操作的这一端称为栈顶（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++的栈和队列怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！
当前标题：c++的栈和队列怎么实现
URL地址：http://cdiso.cn/article/pehjhd.html
