线性结构---栈和队列

线性结构---栈和队列目录 一 栈 stack 栈的概念及运算 1 概念 2 栈的基本运算 栈的顺序存储结构 1 初始化 2 判空栈 3 入栈 4 出栈 5 取栈顶元素 多栈共享邻接空间 1 初始化两栈共享的空栈 2 入栈 3 出栈 栈的链式存储结构 1 入栈 2 出栈 多链栈 1 入栈

大家好,我是讯享网,很高兴认识大家。

目录

一、栈(stack)

❀栈的概念及运算

1.概念

2.栈的基本运算

❀栈的顺序存储结构

1.初始化

2.判空栈

3.入栈

4.出栈

5.取栈顶元素

❀多栈共享邻接空间

1.初始化两栈共享的空栈

2.入栈

3.出栈

❀栈的链式存储结构

1.入栈

2.出栈

❀多链栈

1.入栈

2.出栈

二、队列

❀队列的概念及运算

1.概念

2.基本运算

❀顺序队列

❀循环队列

1.初始化

2.入队

3.出队

4.判队空

❀链队列

1.初始化

2.入队

3.判队空

4.出队


一、栈(stack)

❀栈的概念及运算

1.概念

  栈是一种只允许在一端进行插入和删除操作的线性表,也称为一种受限的线性表。进行插入和删除的一端成为栈的“栈顶”(top),另一端称为栈的栈底(bottom)。栈的插入操作通常称为“入栈”和“进栈”,删除操作通常称为“出栈”和“退栈”。根据栈的定义,栈具有“后进先出”的特点。

栈的模型图:


讯享网

 2.栈的基本运算

  • InitStack(S):初始化一个新的栈
  • Empty(S):判断是否为空栈
  • Push(S,x):在S的顶部插入数据x,将x元素入栈
  • Pop(S):出栈,判断栈是否为空,然后返回栈顶元素,将x出栈
  • GetTop(S):判断栈是否为空,返回栈顶元素
  • SetEmpty(S):置S为空栈

❀栈的顺序存储结构

❀顺序栈

  采用顺序存储方式实现的栈,栈中的元素用一预设的足够长的数组来实现,用int top来作为栈顶的指针,同时将数据域和指针域封装在一个结构中。类型描述如下:

#define MAXSIZE <占最大元素数> tyoedef struct { ElemType elem[MAXSIZE]; int top; }SeqStack;

讯享网

1.初始化

  malloc一块新sizeof(SeqStack)字节的空间,将top指针置为-1。

讯享网SeqStack* InitStack() { SeqStack* s = (SeqStack)malloc(sizeof(SeqStack)); if(!s) { return NULL; } s->top = -1; return s; }

2.判空栈

  检查s->top是否为-1.

int Empty(SeqStack* s) { if(s->top == -1) return 1; //为空 return 0; }

3.入栈

  入栈前先判断栈是否为满,即s->top是否等于MAXSIZE-1,然后再入栈。入栈后改变栈顶指针top的指向。

讯享网int Push(SeqStack* S,ElemType x) { if(s->top == MAXSIZE - 1) return 0; //栈满不能入栈 S->elem[++(S->top)] = x; return 1; }

4.出栈

  出栈前先判断栈是否为空。出栈后改变栈顶指针top的指向。

int Pop(SeqStack* S,ElemType* x) { if(S->top == -1) return 0; *x = S->elem[S->top--]; //将出栈的元素保存在在x return 1; } 

5.取栈顶元素

  先判断顺序栈是否为空。

讯享网ElemType GetTop(SeqStack* S) { if(S->top == -1) return 0; //判断栈是否为空 return (S->elem[S->top]); }

❀多栈共享邻接空间

  在计算机系统软件中,常常一个程序中会用到多个栈,所需栈空间的大小难以准确估计,导致有的栈空间溢出,有的栈空间空闲的情况。计算机软件系统的栈的溢出通常又称为栈的“上溢”。多栈共享邻接空间充分利用了栈的动态特性使其存储空间互补,最常见的是两栈共享,两栈共享拥有两个栈底:lefttop=-1和righttop=MAXSIZE-1,两栈共享的示意图如下:

两栈共享数据结构的定义:

typedef struct { ElemType elem[MAXSIZE]; int leftop; //左侧栈顶指示器 int righttop; //右侧栈顶指示器 }DupsqStack;

为了识别左右栈,必须另设:

讯享网char statues; statues = 'L';//左栈 statues = 'R';//右栈

1.初始化两栈共享的空栈

  malloc出sizeof(DupsqStack)个字节大小的空间,将左栈初始值置为-1,右栈初始值置为MAXSIZE-1。

DupsqStack* InitDStack() { DupsqStack* S = (DupsqStack*)malloc(sizeof(DupsqStack)); if(!S) return NULL; S->lefttop = -1; S->righttop = MAXSIZE-1; return S; }

2.入栈

  根据statues将元素x压入左栈或右栈,在此之前判断两栈共享空间是存满,入栈后将各自的指针重置。

讯享网int PushDupStack(DupsqStack* s,char statues,ElemType x) { if(s->lefttop++ == s->righttop) return 0; //栈满 if(statues == 'L') //左侧进栈 { s->elem[++s->lefttop] = x; } else if(statues == 'R') //右侧进栈 { s->elem[--s->righttop] = x; } else return 0; //参数错误 return 1; //入栈成功 }

3.出栈

  根据statues选择从左侧出栈或者从右侧出栈,在此之前判断栈是否为空。出栈后将各自的指针重置。

int PopDupDtack(DupsqStack* s,char statues) { if(statues == 'L') { if(s->lefttop == -1) return 0;//左栈为空 return (s->elem[s->lefttop--]); } else if(statues == 'R') { if(s->righttop == MAXSIZE) return 0;//右栈为空 return (s->elem[s->righttop--]); } else return 0; //传参错误 }

❀栈的链式存储结构

  要避免栈上溢,最好选用栈的链式存储结构,这种结构的栈通常被称为“链栈”。在一个链栈中,栈底就是链表的最后一个节点,栈顶总是总是链表的第一个节点。一个链栈可由栈顶指针top唯一确定,于是采用带头节点的单链表实现栈,链表的表头指针top就作为栈顶指针,top始终指向当前链栈的头指针,即top->next为链栈的栈顶元素,当top->next==NULL时,说明链栈为空,又称为空栈。链栈的定义如下:

讯享网typedef struct StackNode { DateType date; struct StackNode* next; }slStacktype;

1.入栈操作

   为新存储的节点开辟空间,采用头插法插入节点,保证新插入的节点始终在栈顶。

int PushLStack(slStackType* top,DateType x) { slStackType* p = (slStackType*)malloc(sizeof(slStackType)); if(!p) return 0; p->date = x; //头插法将存储元素的节点插入到链栈中 p->next = top->next; top->next = p; return 1; }

2.出栈

出栈前先判断链栈是否为空,将栈顶指针重置后释放掉出栈元素的空间。

讯享网int PopLStack(slStackType* top,DateType* x) { //出栈前判断链栈是否为空 if(top->next == NULL) return 0; slStackType* p = top->next; *x = p->date; top->next = p->next; free(p); //释放掉出栈节点所占的空间 return 1;//出栈成功 }

❀多链栈

  在程序中同时使用两个以上的栈时,使用顺序栈共用邻接空间很不方便,使用多个单链栈操作比较方便,将多个多链栈的栈顶指针放在一个一维指针数组中,设:

slStackType* top[M];

  其中从top[0] -- top[M-1]存放M个不同的链栈,只需要确定链栈号i就能以top[i]为栈顶指针进行操作。

1.入栈

  为入栈元素申请一个节点,找到存放栈顶指针的数组元素,采用头插法将数据元素插入该链栈中。

讯享网int PushDupls(slStackType* top[M],int i,DateType x) { slStackType* p = (slStackType*)malloc(sizeof(slStackType)); if(!pl) return 0; p->date = x; p->next = top[i]->next; //将数组元素插入到数组下标为i的栈顶指针的链栈之中 top[i]->next = p; return 1; }

2.出栈

  在第i个栈顶指针的数组元素中将元素x出栈,释放掉元素x节点所占的存储空间。出栈之前判断链栈是否为空。

int PopDupls(slStackType* top[M],int i,DateType* x) { if(top[i]->next == NULL) return 0; slStackType* p = top[i]->next; *x = p->date;//将出栈的数据元素存放在x中 top[i]->next = p->next; free(p); return 1; }

二、队列

❀队列的概念及运算

1.概念

  队列是另一种限定性线性表,只允许在表的一端进行插入,另一端进行删除。进行插入的一端叫做“队尾”(rear),进行删除的一端叫做“队头”(front)。队列的插入操作常称为“入队和“进队””,删除操作常称为“出队”和“退队”。根据队列的定义可知,对头元素总是最先进队列,也是最先出队列;队尾元素最后进队列,同时也是最后出队列,因此队列具有“先进先出”的特点。

  队列的示意图:

2.基本运算

  • InitQueue(q):初始化队列,构造一个空队列
  • InQueue(q,x):入队,将数据元素x插入到队尾
  • OutQueue(q,&x):出队,删除队首元素,返回其值
  • FrontQueue(q,&x):读队头元素,返回其值,队列不变。
  • EmptyQueue(q):判断队列是否为空

❀顺序队列

规定:

  由于数组的下标是从0开始的,为了算法设计的方便,初始化队列时,将front和rear指针都赋值为-1,当插入新的元素时,尾指示器rear加一,然后插入数据元素;当队列元素出队时,头指示器front加1,然后删除数据元素。在非空队列中,front总是指向队列中实际队头元素前面的一个位置,队尾总是指向队尾元素(这样设置是为了某些运算的方便)。

顺序队列的类型描述:

 

讯享网#define MAXSIZE <最大元素数> typedef struct { ElemType elem[MAXSIZE]; int front;//头指针 int rear;//尾指针 }SeQueue;
  • 创建一个指向队列的指针变量:SeQueue* sq;
  • 申请顺序队列的存储空间:sq = (SeQueue*)malloc(sizeof(SeQueue));
  • 队中的元素个数:sq->rear - sq->front;
  • 置空队:sq->front = -1;sq->rear = -1;

*缺点:随着入队出队的进行,整个队列会整体向后移动,当队尾指针移动到最后时,再有元素进入就会溢出,而事实上前面已经出队的元素空间仍未被利用,队列并未真正满员,称此中溢出为“假溢出”。

❀循环队列

  ❀解决上述的假溢出问题的方法之一是将队列的数据区elem[0]-elem[MAXSIZE-1]看成是首尾相连的循环结构,称这种循环结构的队列为“循环队列”。头尾指针的关系不变,即头指针指向实际队头元素前面的一个元素的位置,尾指针始终指向尾元素,初始指针为front = rear = MAXSIZE - 1。

  ❀头尾相接的循环表的构造方法可利用数学上的求余运算:

入队时队尾指针加1操作可修改为:

p->rear = (p->rear+1)%MAXSIZE;

  ❀出队时队头指针加1操作可修改为:

讯享网p->front = (p->front+1)%MAXSIZE;

  ❀问题:在对空或者队满或者入队在到出队为空的情况下的条件都是:front == rear。因此无法准确判断队列是否已满。

  解决方法:少用一个元素空间,这种情况下队满的条件是:

(rear+1)%MAXSIZE == front;

  循环队列类型的描述:

讯享网typedef struct { ElemType elem[MAXSIZE]; int front; //头指针 int rear; //尾指针 }CseQueue;

1.初始化

  为循环队列开启空间,将队头指针以及队尾指针置为MAXSIZE-1。

CseQueue* InitSeQueue() { CseQueue* q = (CseQueue*)malloc(sizeof(CseQueue)); if(!q) return 0; q->front = MAXSIZE-1; q->rear = MAXSIZE-1; return q; }

2.入队

  入队前判断队列是否已满,未满将指针++,然后插入元素。

讯享网int InSeQueue(CseQueue* q,ElemType x) { if((q->rear+1)%MAXSIZE == q->front) return 0;//队列已满 q->rear = (q->rear+1)%MAXSIZE; q->elem[q->rear] = x; return 1; }

3.出队

  出队前判断队列是否为空。不为空将指针++,然后移除元素。

int OutSeQueue(CseQueue* q,ElemType* x) { if(q->rear == q->front) return 0;//队列为空 q->font = (q->font+1)%MAXSIZE; *x = q->elem[q->font]; return 1; }

4.判队空

  判断队列中的rear指针和front指针是否为空,二者只有在为空队列的初始状态时才为空。

讯享网int EmptySeQueue(CseQueue* q) { if(q->front == q->rear) return 1;//为空 return 0; }

❀链队列

 链式存储的队列称为“链队列”,可以用带头结点的单链表来实现,链式队列的优点在于不用实现估算空间的占用,而是按需索取。在链队列中,为了操作的方便,也设置队头(front)指针和队尾(rear)指针。头指针始终指向头结点,尾指针指向最后一个元素节点。链队列的示意图如下链队列可以看做是一种特殊的链表:

   链队列的数据类型描述如下:

typedef struct node { DateType date; struct node* next; }Qnode; //链队列节点的类型 typedef struct { Qnode* front; Qnode* rear; }LQueue;//将头尾指针封装在一起的链队列

1.初始化

  创建一个带头节点的空队,将队头指针和队尾指针初始化为头结点。

讯享网LQueue* Init_LQueue() { LQueue* q,QNode* p; q = (LQueue*)malloc(sizeof(LQueue)); //申请头尾指针节点的空间 p = (Qnode*)malloc(sizeof(Qnode)); //创建队列的头结点 if(!q || !p) return NULL; p->next = NULL; q->front = p; q->rear = p; }

2.入队

  为数据元素开辟新的节点,将新节点插入到链表的尾部。

int InLQueue(LQueue* q,DateType x) { QNode* p = (QNode*)malloc(sizeof(QNode));//为新节点开辟空间 if(!q) return 0; p->date = x; q->rear->next = p;//将p节点插入到链队列的最后一个节点后 r->next = NULL;//将最后一个节点的指针域置为空 q->rear = p;//尾指针始终指向尾结点 }

3.判队空

  判断front指针和rear指针是否相等。

讯享网int Empty_LQueue(LQueue* q) { if(q>front == q->rear) return 1; return 0; }

4.出队

  出队前判断队列是否为空,然后将front指针重置,释放队头节点所占的空间。

  *注意:出队完时应判断队列是否为空,如果为空,应当将rear空指针修改为front指针的值,使队列回到初始化状态。

int Out_LQueue(LQueue* q,DateType* x) { if(q->rear == q->front) return 0; //队列为空 Qnode* p = q->front->next; *x = p->date; q->front->next = p->next;//将队头节点置为原队列的第二个节点 free(p); if(q->front->next == NULL) p->rear = p->front;//只有一个元素时,出队列后队列为空,将rear空指针赋值为front指针 }
小讯
上一篇 2025-01-19 15:40
下一篇 2025-02-25 19:44

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/114665.html