线性表之栈与队列

简介:

一。栈是限定仅在表尾进行插入和删除操作的线性表

    队列是只允许在一端进行插入操作,而在另另一端进行删除操作的线性表。

    允许插入和删除的一端称为栈顶,另一端称为栈底,不包含任何数据元素的栈称为空栈,栈称为后进先出  LIFO结构

栈的抽象数据类型

ADT 栈 (stack)

Data

同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系

Operation

InitStack(*S):初始化操作,建立一个空栈S

DestroyStack(*S):若栈存在,则销毁它

ClearStack(*S):将栈清空

stackEmpty(S):若栈为空,返回true,否则返回false

GetTop(S,*e):若栈存在且非空,用e返回S的栈顶元素

Push(*S,e):若栈S存在,插入新元素e到栈S中并成为栈顶元素

Pop(*S,*e):删除栈S中栈顶元素,并用e返回其值

StackLength(S):返回栈S的元素个数

endADT

二。栈的顺序存储结构

定义一个top变量来指示栈顶元素在数组中的位置,当栈存在一个元素时,top等于0

因此把空栈的判定条件定义为top 等于-1

         栈的结构定义

typedef int SElemType;  SElemType类型根据实际情况而定这里假设为int

typedef struct

{

SElemType data[MAXSIZE];

int top; 用于栈顶指针

} sqStack;


进栈操作push   插入元素e为新的栈顶元素

Status Push(SqStack *S,SElemType e)

if(S->top == MAXSIZE -1)  栈满

{

return ERROR;

S->top++; 栈顶指针增加一

S->data[S->top]=e; 将新插入元素赋值给栈顶空间

return OK;

}

出栈操作pop  若栈不空 则删除S的栈顶元素,用e返回其值,并返回OK 否则返回错误

Status Pop(SqStack *S,SElemType *e)

if(S->top==-1)

return ERROR;

*e=S->data[S->top];   将要赋值的栈顶元素赋值给e

S->top--;       栈顶指针减一

return OK;


两栈共享空间   top1+1=top2

栈1为空时,就是top1等于-1时;而当top2等于n时,即是栈2为空时

若栈2是空栈,栈1的top1等于n-1时,就是栈1满了。反之,当栈1为空栈时,top2等于0时,为栈2满。


两栈共享空间结构

typedef struct

{

SElemType data[MAXSIZE];

int top1; 栈1栈顶指针

int top2; 栈2栈顶指针

}SqDoubleStack;

进栈操作

Status Push(sqDoubleStack *S,SElemType e,int stackNumber)

if(S->top1+1==S->top2) 栈已满 不能在push新元素了

return ERROR;

if(stackNumber==1)         栈1有元素进栈

S->data[++S->top1]=e;若栈1则先top1+1后给数组元素赋值

else if (stackNumber==2)   栈2有元素进栈

S->data[--S->top2]=e;若栈2则先top2-1后给数组元素赋值

return OK;

两栈共享空间的pop方法

Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)

if(stackNumber==1)

if(S->top1==-1)

return ERROR;  说明栈1已经是空栈 溢出

*e=S->data[S->top1--];  将栈1的栈顶元素出栈

else if(stackNumber==2)

if(S->top2==MAXSIZE)

return ERROR; 说明栈2已经是空栈溢出

*e=S->data[S->top2++];将栈2的栈顶元素出栈

return OK;


栈的链式存储结构即链栈   栈顶  an    栈底  a1

链栈结构

typedef struct StackNode

SElemType data;

struct StackNode *next;

}StackNode,*LinkStackPtr;


typedef struct LinkStack

LinkStackPtr top;

int count;

}LinkStack;


栈的链式存储结构---进栈操作

假设元素值为e的新结点为s,top为栈的栈顶指针

插入元素e为新的栈顶元素

Status Push(LinkStack *S,SElemType e)

LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));

s->data=e;

s->next=S->top; 把当前的栈顶元素赋值给新结点的直接后继

S->top=s; 将新结点s赋值给栈顶指针

S->count++;

return OK;

栈的链式存储结构--出栈操作

若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR

Status Pop(LinkStack *S,SElemType *e)

LinkStackPtr p;

if(StackEmpty(*S))

return ERROR;

*e=S->top->data;

p=S->top; 将栈顶结点赋值给p

S->top=S->top->next;使得栈顶指针下移一位,指向后一结点

free(p); 释放结点p

S->count--;

return OK;


栈的应用---递归

把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数:称作递归函数

9+(3-1)* 3+10/2

仔细观察后发现,括号都是成对出现的,有左括号就一定有右括号,对于多重括号,最终也是完全嵌套匹配的,这用栈架构正好合适,只有碰到左括号,就将此左括号进栈,不管表达式有多少重括号,反正遇到左括号就进栈,而后面出现右括号时,就让栈顶的左括号出栈,期间让数字运算,这样,最终有括号的表达式从左到右巡查一遍,栈应该是由空到有元素,最终再因全部匹配成功后成为空栈的结果。

转化成 9 3 1 - 3 * + 10 2 / +   后缀表达式 叫后缀的原因 所有符号都是在要运算数字的后面出现

我们平时所用的标准四则运算表达式9+(3-1)* 3+10/2  叫做中缀表达式 转变成后缀表达式。规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。





队列的定义:是只允许在一端进行插入操作,而在另一端进行删除操作的线性表

先进先出 允许插入的一端称为队尾,允许删除的一端称为队头


队列的抽象数据类型

ADT 队列(Queue)

Data

同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系

Operation

InitQueue(*Q):初始化操作,建立一个空队列Q

DestroyQueue(*Q):若队列Q存在,则销毁它

ClearQueue(*Q):将队列Q清空

QueueEmpty(Q):若队列Q为空,返回true,否则返回false

GetHead(Q,*e):若队列Q存在且非空,用e返回队列Q的队头元素

EnQueue(*Q,e):若队列Q存在,插入新元素e到队列Q中并成为队尾元素

DeQueue(*Q,*e):删除队列Q中队头元素,并用e返回其值

QueueLength(Q):返回队列Q的元素个数

endADT

循环队列

队列顺序存储的不足:假设一个队列有n个元素,则顺序存储的队列需要建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头,所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度是O(1)。与栈不同的是,队列元素的出列是在队头,即下标是0的位置,那也就意味着,队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时时间复杂度O(n)。

现实当中,你上了公交车,发现前排有2个空座位,而后排所有座位都已经坐满,你会怎么做?立马下车,并对自己说,后面没坐了,我等下一辆?没有这么笨的人,前面有座位,当然也是可以坐的除非坐满了,才会考虑下一辆。 这种前排有座 而后排没人坐的情况 叫做 假溢出

我们把队列的头尾相接的顺序存储结构称为循环队列。

循环队列的顺序存储结构

typedef int QElemType;  QElemType 类型根据实际情况而定,这里假设为int

typedef struct

QElemType data[MAXSIZE];

int front;     头指针

int rear; 尾指针若队列不空,指向队列尾元素的下一个位置

}SqQueue;


循环队列的初始化

Status InitQueue (SqQueue *Q)

Q->front=0;

Q->rear=0;

return OK;

循环队列求队列长度

int QueueLength(SqQueue Q)

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;

循环队列的入队操作

Status EnQueue(SqQueue *Q,QElemType e)

if ((Q->rear+1)%MAXSIZE == Q->front) 队列满的判断

return ERROR;

Q->data[Q->rear]=e; 将元素e赋值给队尾

Q->rear=(Q->rear+1)%MAXSIZE; rear指针向后移一位置,若到最后则转到数组头部

return OK;

循环队列的出队列操作

Status DeQueue(SqQueue *Q,QElemType *e)

if (Q->front == Q->rear)队列空的判断

return ERROR;

*e=Q->data[Q->front]; 将队头元素赋值给e

Q->front=(Q->front+1)%MAXSIZE; front指针向后移一位置 若到最后则转到数组头部

return OK;


队列的链式存储结构及实现


队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列

链队列的结构为

typedef int QElemType;

typedef struct QNode   结点结构

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;


typedef struct      队列的链表结构

QueuePtr front,rear;  队头队尾指针

}LinkQueue;


入队操作

Status EnQueue(LinkQueue *Q,QElemType e)

QueuePtr s=(QueuePtr)malloc(sizeof(QNode));

if (!s)       存储分配失败

exit(OVERFLOW);

s->data=e;

s->next=NULL;

Q->rear->next=s;   把拥有元素e新结点s赋值给原队尾结点的后继

Q->rear=s;         把当前的s设置为队尾结点,rear指向s

return OK;


出队操作

Status DeQueue(LinkQueue *Q,QElemType *e)

QueuePtr p;

if(Q->front==Q->rear)

return ERROR;

p=Q->front->next;      将欲删除的队头结点暂存给p

*e=p->data;            将欲删除的队头结点的值赋值给e

Q->front->next=p->next;   将原队头结点后继p->next赋值给头结点后继

if(Q->rear==p)          若队头是队尾,则删除后将rear指向头结点

Q->rear=Q->front;

free(p);

return OK;



      本文转自潘阔 51CTO博客,原文链接:http://blog.51cto.com/pankuo/1631334,如需转载请自行联系原作者





相关文章
|
23天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
10天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
29 5
|
26天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
29天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
49 4
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
131 9
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
38 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
数据结构(栈与列队)
数据结构(栈与列队)
22 1