线性表——栈与队列

标签：线性表 队列 元素 栈顶 front 进栈 rear

• 栈

　　栈（stack）：先进后出，后进先出的数据结构。

　　栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。需要注意，栈是一个线性表，也就是说栈元素具有线性关系，即前驱后继关系，只不过它是一种特殊的线性表，因为它限制了这个线性表的插入和删除操作，栈底是固定的，最先进栈的只能在栈底。

1. 栈的插入操作：叫作进栈，也称压栈、入栈。
2. 栈的删除操作，叫作出栈，有的也叫作弹栈。

　　假设我们规定1、2、3依次进栈，出栈顺序可能有5种：

1.  3，2，1
2.  1，2，3
3.  1，3，2
4.  2，1，3
5.  2，3，1

　　需要注意的是没有3，1，2这种出栈顺序，因为只要3入栈，1、2必已入栈并未出栈，2比1后入栈，应比1先出栈，故如果是3最先出栈的话，顺序必为3，2，1。

——————————————————————————————————

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的元素个数。

————————————————————————————————————

• 栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。

typedef int SElemType;　　/*SElemType类型数据根据实际情况而定，这里假设为int*/
/*顺序栈结构*/
typedef struct
{
　　SElemType data[MAXSIZE];
　　int top;　　/*用于栈顶指针*/
}SqStack;

 

　　栈的顺序存储结构——进栈操作：

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S,SElemType e)
{
　　if(S->top==MAXSIZE-1)　　/*栈满*/
　　{
　　　　return ERROR；
　　}
　　S->top++;　　/*栈顶指针增加一*/
　　S->data[S->top]=e;　　/*将新插入元素赋值给栈顶空间*/
　　return OK;
}

 

　　栈的顺序存储结构——出栈操作：

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR*/
Status Pop(SqStack *S,SElemType *e)
{
　　if(S->top==-1)　　return ERROR;
　　*e=S->data[S->top];　　/*将要删除的栈顶元素赋值给e*/
　　S->top--;　　/*栈顶指针减一*/
　　return OK；
}

 

•  两栈共享空间（使用前提：这只是针对两个具有相同数据类型的栈的一个设计上的技巧）

/*两栈共享空间结构*/
typedef struct
{
　　SElemType data[MAXSIZE];
　　int top1;　　/*栈1栈顶指针*/
　　int top2;　　/*栈2栈顶指针*/
}SqDoubleStack; 

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
　　if(S->top1+1==S->top2)　　/*栈已满，不能再push新元素了*/
　　　　return ERROR;
　　if(stackNumber==1)
　　　　S->data[++S->top1]=e;　　/*若是栈1则先top+1后给数组元素赋值*/
　　else if(stackNumber==2)　　/*栈2有元素进栈*/
　　　　S->data[--S->top2]=e;　　/*若是栈2则先top2-1后给数组元素赋值*/
}

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
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;
}

•  栈的链式存储结构，简称为链栈。

/*链栈结构*/
typedef struct StackNode
{
　　SElemType data;
　　struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct
{
　　LinkStackPtr top;　　/*栈顶指针*/
　　int count;　　/*元素数量*/
}LinkStack;

 

　　栈的链式存储结构——进栈操作：

/*插入元素e为新的元素*/
Status Push(LinkStack *S,SElemType e)
{
　　LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));　　/*开辟一个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;
}

　　链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

　　如果栈的使用过程中元素的变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会好一点。

　　栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦与我们要解决的问题的核心。现在的许多高级语言，比如Java、c#等都有对栈的封装，我们可以不用关注它的实现细节，直接使用Stack的push和pop方法。

• 栈的应用——递归

　　我们先来看一个经典的递归例子：斐波那契数列（Fibonacci）。斐波那契数列就是前面相邻两项之和构成了后一项。

　　我们用数学函数来定义就是：

　　　　  | 0，当n=0

　F(n) =   | 1，当n=1

 　　　　 | F(n-1)+F(n-2)，当n>1

int main()
{
　　int i;
　　int a[40];
　　a[0]=0;
　　a[1]=1;
　　printf("%d",a[0]);
　　printf("%d",a[1]); 
　　for(i=2;i<40;i++)
　　{
　　　　a[i]=a[i-1]+a[i-2];
　　　　printf("%d",a[i]);
　　}
　　return 0
}

/*斐波那契的递归函数*/
int Fbi(int i)
{
    if(i<2)
        return i==0?0:1;
　　return Fbi(i-1)+Fbi(i-2);　　/*这里Fbi就是函数自己，等于在调用自己*/
}
int main()
{
　　int i;
　　printf("递归显示斐波那契数列：\n");
　　for(i=0;i<40;i++)
　　　　printf("%d",Fbi(i));
　　return 0;
}

 

　　递归的定义：我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。。每个递归定义必须至少有一个条件，满足时递归　不在进行，即不再引用自身而是返回值退出。

　　递归的优势：递归能使程序的结构更清晰、更简洁、更容易让人理解从而减少读懂代码的时间。

　　递归的劣势：大量的递归调用会建立函数的副本，会耗费大量的时间和内存。

　　对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统来代劳了。

• 栈的应用——四则运算表达式求值

　　后缀（逆波兰）表示法：一种不需要括号的后缀表达式，我们也把它称为逆波兰（ReversePolish Notation，RPN）表示。

　　四则混合运算的基本思路：（先乘除，后加减，从左算到右，先括号内后括号外。乘除在加减后面却要先运算，而加了括号后，就变得更加复杂，不知道如何处理。）有左括号就一定有右括号，对于多重括号，最终也是完全嵌套匹配的，这用栈结构正好合适，只要碰到左括号，就将此左括号进栈，不管表达式有多重括号，反正遇到左括号就进栈，而后面出现右括号时，就让栈顶的左括号出栈，期间让数字运算，这样，最终有括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最终再因全部匹配成功后成为空栈。

• 中缀表达式（标准四则运算表达式）：即“9+(3-1)x3+10/2”叫做中缀表达式。
• 后缀表达式：9 3 1 - 3 x + 10 2 / +

9 2 3x + 10 2 / +

9 6 +10 2 / +

9 6 + 5 +

15 5 +

20

　　规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

（1）初始化一个空栈。此栈用来对要运算的数字进出使用。

（2）后缀表达式中前三个都是数字，所以9、3、1进栈。

（3）接下来是”-“，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈。

（4）接着是3进栈。

（5）后面是”*“，也就意味着栈中3和2出栈，2与3相乘。得到6，并将6进栈。

（6）下面是“+”，所以栈中6和9出栈，9和6相加，得到15，将15进栈。

（7）接着是10与2两数字进栈。

（8）接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。

（9）最后一个是符号“+”，所以15和5出栈并将相加，得到20，将20进栈。

（10）结果是20出栈，栈变为空。

• 中缀表达式转后缀表达式（9+(3-1)x3+10/2——>9 3 1 - 3 x + 10 2 / +）

　　规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

（1）初始化一空栈，用来对符号进出栈使用。

（2）第一个字符是数字9，输出9，后面是符号“+”，进栈。

（3）第三个字符是”（“，依然是符号，因为其只是左括号，还未配对，故进栈。

（4）第四个字符是数字3，输出，总表达式为9 3，接着是“-”，进栈。

（5）接下来是数字1，输出，总表达式为9 3 1，后面是符号”）“，此时，我们需要去匹配此前的”（“，所以栈顶依次出栈，并输出，直到”（“出栈为止。此时左括号上方只有“-”，因此输出”-“。总的输出表达式为9 3 1 -。

（6）紧接着是符号“x”，因为此时的栈顶符号为“+”优先级低于“x”，因此不输出，“x”进栈。接着是数字3，输出，总的表达式为9 3 1 - 3。

（7）之后是符号“+”，此时当前栈顶元素“x”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”更低的优先级，所以全部出栈），总输出表达式为9 3 1 - 3 x +。然后将当前这个符号“+”进栈。也就是说，前六张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”。而左图中的栈底（也就是栈顶）的“+”是指“9+(3-1)x3+"中的最后一个”+“。

（8）紧接着数字10，输出，后是符号”/“，所以”/“进栈。

（9）最后一个数字2，输出，总的表达式为9 3 1 - 3 x 10 2。

（10）因为已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 - 3 x +10 2 / +。

　总结，计算机具有处理我们通常的标准（中缀）表达式的能力。（1）将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。（2）将后缀表达式进行运算得出结果（栈用来进出运算的数字）整个过程都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

• 栈的兄弟数据结构——队列

　　队列（queue）：先进先出，后进后出的数据结构。

　　队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First in First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为对头。假设队列是q=（a₁，a₂，……，a_n），那么a1就是队头元素，而a_n是队尾元素。这样我们就可以删除时总是从a₁开始，而插入时，列在最后。

——————————————————————————————————

ADT　　栈（Queue）

Data

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

Operation

　　InitQueue（*Q）：初始化操作，建立一个空队列Q。

　　DestroyQueue（*Q）：若队列Q存在，则销毁它。

　　ClearQueue（*Q）：将队列Q清空。

　　QueueEmpty（Q）：若队列Q为空，返回true，否则返回false。

　　GetHead（Q，*e）：若队列存在且非空，用e返回队列Q的队头元素。

　　EnQueue（*Q，e）：若队列Q存在，插入新元素e到队列Q中并成为队尾元素。

　　DeQueue（*Q，*e）：删除队列Q中队头元素，从用e返回其值。

　　QueueLength（Q）：返回队列Q的元素个数。

————————————————————————————————————

　　线性表有顺序存储和链式存储，栈是线性表，具有这两种存储方式，同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。

• 队列的顺序存储，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)。

　　为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

　　假溢出：在下标为0和1的地方还是空闲的。我们把这种现象叫做”假溢出“。为避免这种明目张胆的内存浪费，一种新的数据结构循环队列问世。

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

　　此时问题又来了front等于rear，此时的队列时空还是满呢？

1. 办法一：设置一个标志变量flag，当front=rear，且flag=0时为队列空，当front=rear，且flag=1时为队列满。
2. 办法二：当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。

　　　当rear小于front时，队列满的条件是（rear+1）%QueueSize==front（取模“%”的目的就是为了整合rear与front大小为一个问题）。

　　　因此通用计算队列长度的公式为：（rear-front+QueueSize）%QueueSize。

typedef int QElemType;    /*QElemType类型根据实际情况而定，这里假设为int*/
/*村换队列的顺序存储结构*/
typedef struct
{
　　QElemType data[MAXSIZE];
　　int front;　　/*头指针*/
　　int rear;　　/*尾指针，若队列不空，指向队列尾元素的下一个位置*/
}SqQueue;

/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q)
{
　　Q->front=0;
　　Q->rear=0;
　　return OK;
}

/*返回Q的元素个数，也就是队列的当前长度*/
int QueueLength(SqQueue Q)
{
　　return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;　　/*MAXSIZE相当于坐标轴的零点*/
} 

　　循环队列的入队列操作代码如下：

/*若队列未满，则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q,QElemType e)
{
　　if((Q->rear+1)%MAXSIZE==Q->front)　　/*队列满的判断*/
　　　　return ERROR;
　　Q->data[Q->rear]=e;　　/*将新元素赋值给队尾*/
　　Q->rear=(Q->rear+1)%MAXSIZE；　　/*rear指针向后移一位置*/
　　　　　　　　　　　　　　　　　　　　　/*若到最后则转到数组头部*/
　　return OK；
}

 　　循环队列的出队列操作代码如下：

/*若队列不空，则删除Q中队头元素，用e返回其值*/
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;
}

 　　接下来我们还要研究一下不需要担心队列长度的链式存储结构。

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

　　为了操作方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点。空队列时，front和rear都指向头结点。

　　链队列的结构为:

typedef int QElemType;    /*QElemType根据实际情况而定，这里假设为int*/
typedef struct QNode　　/*结点结构*/
{
　　QElemType data;
　　struct QNode *next;
}QNode,*QueuePtr;
typedef struct　　/*队列的链表结构*/
{
　　QueuePtr front,rear;　　/*队头、队尾指针*/
}LinkQueue;

　　队列的链式存储结构——入队操作：

/*插入元素e为Q的新的队列元素*/
{
　　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;
}

　　队列的链式存储结构——出队操作：

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
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;
}

　　对于循环队列与链队列的比较：它们的基本操作都是常数时间，即O(1)，循环队列是事先申请好空间，试用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素和空间浪费的问题。而链队列则不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上链队列更加灵活。在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列的长度，则用链队列。

• 总结回顾

　　这一张的内容是栈和队列，它们都是特殊的线性表，只不过对插入和删除操作做了限制。

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

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

• 如果它们线性表的顺序存储结构来实现：

（1）对栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。

（2）对队列来说，为了避免插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是O(n)的时间复杂度变成了O(1)。

• 通过顺序存储结构来实现的话原则上与线性表基本相同。

标签：线性表,队列,元素,栈顶,front,进栈,rear
From： https://www.cnblogs.com/cge2ox/p/17553420.html