> 文档中心 > 栈与队列真的很难吗?看完你就会了

栈与队列真的很难吗?看完你就会了


💟作者简介:大家好,我是锡兰Ceylan_,可以叫我CC ❣️    
📝个人主页:锡兰Ceylan_的博客
🏆博主信息:平凡的大一学生,有着不平凡的梦

        专栏

  • 【备战蓝桥,冲击省一】
  • 【开卷数据结构】

⚡希望大家多多支持😘一起进步~❤️
🌈若有帮助,还请关注点赞收藏,不行的话我再努努力💪​

上文详细的讲解了顺序表与链表的实现,相信大家在顺序表与链表的指基础上,很容易就能学会站和队列,废话不多说,我们马上开始!


🌺栈

🍁栈的定义

栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作

假设栈 【s = (a1,a2,……,an) 】,a1为栈底元素,an为栈顶元素。由于栈只能在栈顶进行插入和删除操作,所以进栈次序依次为【a1,a2,……,an】,出栈次序为【an,……,a2,a1】

由此可见:栈的操作特性可以明显地概括为后进先出

栈类似于线性表,它也有两种对应的存储方式分别为顺序栈和链栈


🍁顺序栈

(1)顺序栈的定义

Q:什么是顺序栈?

A:采用顺序存储的栈成为顺序栈。它利用一组地址连续的存储单位存放自栈底到栈顶的数据元素,同时附设一个指针(top)来指示当前栈顶的位置。

栈的顺序存储类型可描述为

#define MaxSize 100//定义栈中元素的最大个数typedef struct{SElemtype *base;//栈底指针SElemtype *top;//栈顶指针 int stacksize//栈可用的最大容量 }SqStack; 

(2)顺序栈的初始化

Q:什么是顺序栈的初始化?

A:顺序栈的初始化操作就是为顺序栈动态分配一个最大容量为 MaxSize 的数组空间。

🔺实现原理

1️⃣为顺序栈动态分配一个最大容量为MAXSIZE的数组

2️⃣栈顶指针top初始为base,表示栈为空

3️⃣stacksize置为栈的最大容量MaxSize

💬 代码演示

Status InitStack(SqStack &S){//构造一个空栈SS. base=new SElemType[MaxSize];//为顺序栈动态分配一个最大容量为MAxsiniif(!S. base) exit(OVERFLOW);//存储分配失败S. top=S. base;//top初始为base,空栈S. stacksize=MaxSize;//stacksize置为栈的最大容量MaxSizereturn OK;}

(3)顺序栈的入栈

Q:什么是顺序栈的入栈?

A:入栈操作是将新元素进入栈

🔺实现原理

1️⃣判断栈是否满了,若满了返回ERROR

2️⃣将新元素压入栈,栈顶指针加1

💬 代码演示

Status Push(SqStack&S,SElemType e){//插入元素e为新的栈顶元素if(S.top-S.base==S:stacksize) return ERROR;//栈满 *S. top++=e;   //元素e压入栈顶,栈顶指针加1return OK;}

(4)顺序栈的出栈

Q:什么是顺序栈的出栈?

A:出栈操作是将栈顶元素删除

🔺实现原理

1️⃣判断栈是否空,若空则返回ERROR

2️⃣栈顶指针减1,栈顶元素出栈

 💬 代码演示

Status Pop(SqStack &S,SElemType &e)(//删除S的栈顶元素,用e返回其值if(S.top==S.base) return ERROR;//栈顶指针减1,将栈顶元素赋给e   //栈顶指针减1,将栈顶元素赋给e e=*--S.top;return OK;)

(5)取顺序栈的栈顶元素

Q:如何取顺序栈的栈顶元素?

A:当栈非空时,此操作返回当前栈顶元素的值,栈顶指针保持不变。

🔺实现原理

1️⃣判断栈是否空

2️⃣返回栈顶元素的值,栈顶指针不变

 💬 代码演示

SElemType GetTop (SqStack S){//返回s的栈顶元素,不修改栈顶指针if(S.top!=S.base)  //栈非空    return*(S.top-1);//返回栈顶元素的值,栈顶指针不变)

🍁链栈

采用链式存储的栈称为链栈。链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现

栈的顺序存储类型可描述为

typedef struct Linknode{ElemType data;//数据域struct Linknode *next;//指针域} *LiStack; 

采用链式存储,便于结点的插入与删除。链栈的操作与链表类似,入栈和出栈的操作都在链表的表头进行。


🌺队列

🍁队列的定义

队列是一种线性表,但限定这种线性表只能在表的一端进行插入,在另一端进行删除。允许删除的一端为队头,又称为队首,允许插入的一端为队尾

队列与生活中的排队一样,最早排队的最先离开,队列的操作特性可以明显地概括为先进先出

队列有两种存储表示,分别为顺序表示与链式表示

🍁队列的顺序表达与实现

(1)队列顺序存储结构

和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次列头到队列尾的元素之外。还需附设两个整型变量【front】和【rear】分别指示队列头元素及队间的位置(后面分别称为头指针和尾指针)。

队列的顺序存储结构表示如下:

#define   MAXSIZE    100//队列容量typedef   struct {   ElemType *base;      //存储空间int front,rear;     //队首,队尾}SqQueue ;

(2)假溢出

图(1)所示为队列的初始状况。此时有【front == rear == 0 成立。该条件可以作为队列判空的条件。

但是【rear == MAXSIZE】不能作为队列满的条件。为什么呢?

图(4)队列中只有一个元素,仍满足该条件。这时入队出现上溢出。但是这种溢出并不是真正的溢出,在队列中依然存在可以存放元素的空位置,所以是一种假溢出

如何解决循环链表的这一缺点呢?

🍁循环队列

Q:什么是循环队列?

A:将顺序队列臆造成一个环状的空间,即把存储队列元素的表从逻辑上视为一个环,称为循环队列

(1)循环队列的初始化

Q:什么是循环队列的初始化?

A:循环队列的初始化就是动态分配一个预定义大小为 MAXSIZE 的数组空间

🔺实现原理

1️⃣为队列动态分配一个最大容量为MAXSIZE的数组空间

2️⃣base指向数组空间的首地址

3️⃣头指针与尾指针置为零,表示队列为空

💬 代码演示

Status InitQueue ( SqQueue  &Q ){Q.base=new  ElemType[MAXSIZE];if(!Q.base)return OVERFLOW;Q.front=Q.rear=0;return OK;} 

🌹循环队列的入队

Q:什么是循环队列的入队?

A:入队操作是指在队尾插入一个新的元素

🔺实现原理

1️⃣判断队列是否满

2️⃣满了返回ERROR

3️⃣将新元素插入队尾

4️⃣队尾指针加一

💬 代码演示 

Status EnQueue(SqQueue &Q,ElemType e){    if((Q.rear+1)%MAXSIZE==Q.front)//判满    return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;}

🌹循环队列的出队

Q:什么是循环队列的出队?

A:出队操作是删除队头元素

🔺实现原理

1️⃣判断队列是否为空

2️⃣为空返回ERROR

3️⃣保留队头元素

4️⃣队头指针加一

💬 代码演示 

Status DeQueue(SqQueue &Q, ElemType &e){    if( Q.rear==Q.front ) return ERROR;//判空e = Q.base[Q.front];Q.front = (Q.front+1)%MAXSIZE;return OK;}

🍁链队列

Q:什么是链队列?

A:队列的链式表示称为链队列。它实际上是一个同时带有队头指针和队尾指针的单链表,头指针指向对头结点,尾指针指向队尾结点。

队列的链式存储如图:

队列的链式存储类型可描述为:

typedef struct Qnode{ElemType data;    struct QNode * next;}Qnode,*QueuePtr;    //结点typedef struct { QueuePtr  front;QueuePtr rear;}LinkQueue;  //链队  

(1)链栈的初始化

Q:什么是链队列的初始化?

A:链栈的初始化操作就是构建一个只有头结点的空队。

🔺实现原理

1️⃣生成新结点作为头结点

2️⃣队头指针和队尾指针指向该结点

3️⃣头指针的指针域置空

💬 代码演示 

Status InitQueue(LinkQueue &Q){Q.front=Q.rear=new QNode;p->next=NULL;return OK;} 

🌹链栈的入队

🔺实现原理

1️⃣为入队元素分配结点空间,用指针p指向

2️⃣将新结点数据域置为e

3️⃣将新结点插入到队尾

4️⃣修改队尾指针为p

💬 代码演示 

Status EnQueue(LinkQueue &Q,ElemType e){p=new QNode;//为入队元素分配结点空间,用指针p指向p->data=e; //将新结点数据域置为ep->next=NULL;Q.rear->next=p;     //将新结点插入到队尾Q.rear=p;//修改队尾指针为preturn OK;}

🌹链栈的出队

🔺实现原理

1️⃣判断是否为空,为空返回ERROR

2️⃣保留头元素空间,以备释放

3️⃣修改头指针的指针域,指向下一结点

4️⃣判断出队元素是否是最后一个元素,若是,将队尾指针重新赋值,指向头结点

5️⃣释放原队头元素的空间

💬 代码演示 

Status DeQueue(LinkQueue &Q,ElemType &e){if(Q.front==Q.rear)//若队列为空,返回ERRORreturn ERROR;QNode *p=Q.front->next;//保留头元素空间,以备释放Q.front->next=p->next;//修改头指针的指针域,指向下一结点    if(Q.rear==p)//判断出队元素是否是最后一个元素,若是,将队尾指针重新赋值,指向头结点Q.rear=Q.front; delete p;//释放原队头元素的空间return OK;}

 本人不才,如有错误,欢迎各位大佬在评论区指正。有帮助的话还请【关注点赞收藏】,不行的话我再努努力💪💪💪