数据结构第四章 栈与队列_先进后出的线性表

栈与队列：

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

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

栈

栈的定义

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

我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈是先进后出的线性表，简称LIFO结构。

栈的插入操作，叫做进栈，也称压栈、入栈。栈的删除操作，也叫出栈或者弹栈。

例如，我们有1,2,3三个数字依次进栈，那会有几种出栈次序呢？

• 第一种，1,2,3进，再3,2,1出，这是最简单的一种，出栈次序为321。
• 第二种，1进，1出，2进，2出，3进，3出，出栈次序为123。
• 第三种，1进，2进，2出，1出，3进，3出，出栈次序为213。
• 第四种，1进，2进，2出，3进，3出，1出，出栈次序为231。
• 第五种，1进，1出，2进，3进，3出，2出，出栈次序为132。

栈的抽象数据类型

ADT stack(栈)
Data
	同线性表。元素具有相同类型，相邻元素具有前缀和后继的关系
Operation
	InitStack(*S);  //初始化，建立空栈S
	DestroyStack(*S); //栈存在就销毁
	ClearStack(*S);  //清空栈
	StackEmpty(S);  //判断栈是否为空，若是返回true，反之返回false
	GetTop(S,*e); //若栈存在且非空，返回栈顶元素
	Push(*S,e);  //若栈S存在，插入新元素e到栈S中并成为栈顶元素
	Pop(*S,*e);  //删除栈S中栈顶元素，并用e返回其值
	StackLength(S);  //返回栈S的元素个数
endADT
1
2
3
4
5
6
7
8
9
10
11
12
13

栈的顺序存储结构及其实现

栈的顺序存储结构定义：

typedef int SElemType;
typedef struct
{
	SElemType data[MAXSIZE];
	int top;
}SqStack;
1
2
3
4
5
6

进栈操作push代码：

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S,SElemType e)
{
	if(S->top == MAXSIZE - 1)  //判断栈是否已满
		return ERROR;
	S->top++;   //栈顶指针加1
	S->data[S->top] = e;  //将新插入的元素赋值给栈顶空间
	return OK;
}
1
2
3
4
5
6
7
8
9

出栈操作pop代码：

/*若栈非空，则删除S的栈顶元素，用e返回其值*/
Status Pop(SqStack *S,SElemType e)
{
	if(S->top == - 1)  //判断栈是否为空
		return ERROR;
	*e = S->data[S->top];  //将要删除的栈顶元素赋值给e 
	S->top--;   //栈顶指针减1
	return OK;
}
1
2
3
4
5
6
7
8
9

进栈和出栈的算法时间复杂度均为O(1)

两栈共享空间

栈的顺序存储有一个缺点便是需要事先确定数组存储空间的大小，这十分不方便。我们完全可以用一个数组来存储两个相同类型的栈。做法如下：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

关键思路：栈1为空时，即top1等于-1时；而top2等于n时，即是栈2为空时。若栈2是空栈，栈1的top1等于n-1时，栈1便是栈满状态，同理，若栈1是空栈，top2为0时，栈2就处于栈满状态。最普遍的状态就是top1 +1 ==top2时为栈满。

两栈共享空间的结构的代码如下：

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

对于两栈共享空间的push方法，我们除了需要插入元素参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下：

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
    if(S->top1+1 == S->top2) //栈满
        return ERROR;
    if(stackNumber == 1)  //栈1有元素进栈
        S->data[++S->top1] = e;  //若栈1有元素进栈则top先加1后给数组元素赋值
    else if (stackNumber == 2)  // 栈2有元素进栈
        S->data[--S->top2] = e; //若栈2有元素进栈则top先减1后给数组元素赋值
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11

对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber。代码如下：

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR*/
Status Pop(SqDoubleStack *S,SelemType e,int stackNumber)
{
    if(stackNumber == 1)
    {
        if(S->top == -1) //栈1若是空栈
            return ERROR;
        *e = S->data[S->top1--];  //将栈1的栈顶元素出栈
    }
    else if(stackNumber == 2)
    {
        if(S->top2 == MAXSIZE) //栈2若是空栈
            return ERROR;
        *e = S->data[S->top2++];  //将栈2的栈顶元素出栈
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

栈的链式存储结构及其实现

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

对于链栈来说，基本不存在栈满的情况，除非内存没有可用的空间。对于空栈来说，链表的空其实就是top=NULL的时候。

链栈的结构定义：

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;
1
2
3
4
5
6
7
8
9
10
11

进栈操作：

/*插入元素为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;
}
1
2
3
4
5
6
7
8
9
10

出栈操作：

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR*/
Status Push(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

进栈和出栈的算法时间复杂度均为O(1)

栈的应用----递归

经典的递归例子：

。这个数列有明显的特点，那就是前面相邻两项之和，构成了后一项。

假设我们需要打印出前20位的斐波那契数列数，则其实现代码如下：

int main()
{
    int i;
    int a[20];
    a[0]=0;
    a[1]=1;
    printf("%d",a[0]);
    printf("%d",a[1]);
    for(i=2;i<20;i++)
    {
        a[i]=a[i-1]+a[i-2];
        printf("%d",a[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如果使用递归来实现，会更加简便：

/*斐波那契数列递归函数*/
int Fbi(int i)
{
    if (i<2)
        return i == 0?0:1;
    return Fbi(i-1)+Fbi(i-2);
}
int main()
{
    int i;
    for(int i=0;i<20;i++)
        printf("%d",Fbi(i));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

递归定义：我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。

【注】每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出，这样就不会陷入永不结束的无穷递归中。

队列

队列的定义

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

队列是一种先进先出的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的抽象数据类型

ADT Queue(队列)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
    InitQueue(*Q); //初始化，建立一个空队列Q
	DestroyQueue(*Q); //若队列Q存在，就销毁它
	ClearQueue(*Q); //将队列Q清空
	QueueEmpty(Q); //若队列为空，返回true，否则返回False
	GetHead(Q,*e); //若队列Q存在且非空，则用e返回队列的队头元素
	EnQueue(*Q,e); //若队列Q存在，插入新元素e到队列中
	DeQueue(*Q,e); //删除队列Q中队头元素，并用e返回其值
	QueueLength(Q); //返回队列Q的元素个数
endADT
1
2
3
4
5
6
7
8
9
10
11
12
13

循环队列

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

为了避免“假溢出”（数组末尾元素已经占用，再向后加，就会产生数组越界的错误，而实际上，队列下标0和1处是空闲的，这种现象就是假溢出）错误，我们将队列变成首尾相接的循环。这种顺序存储结构就称为循环队列。

若队列的最大尺寸为QueueSize，那么队列满的条件是
$$(rear+1)\%QueueSize==front$$
通用的计算队列长度的公式为：
$$(rear-front+QueueSize)\%QueueSize$$
循环队列的顺序存储结构代码如下：

typedef int QElemType;
typedef struct
{
	QElemType data[MAXSIZE];
	int front;  //头指针
	int rear;  //尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;
1
2
3
4
5
6
7

循环队列的初始化代码：

Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return OK;
}
1
2
3
4
5
6

循环队列求队列长度代码：

/*返回Q的元素个数，也就是队列的当前长度*/
int QueueLength(Squeue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
1
2
3
4
5

循环队列入队操作代码：

/*若队列未满，则插入元素e为Q新的队尾元素*/
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;
}
1
2
3
4
5
6
7
8
9

循环队列出队操作代码：

/*若队列不空，则删除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;
}
1
2
3
4
5
6
7
8
9

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

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

链队列的结构为：

typedef int QElemType;
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
    QueuePtr front,rear;
}LinkQueue;
1
2
3
4
5
6
7
8
9
10
11

链队列入队操作：

/*插入元素e为Q的新的队尾元素*/
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;
}
1
2
3
4
5
6
7
8
9
10
11
12

链队列出队操作：

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
Status DeQueue(LinkQueue *Q,QElemType e)
{
	QueuePtr p;
	if(Q->rear == Q->front)
		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;//把当前的s设置为队尾结点，rear指向s
    free(p);
    
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

入队和出队的算法时间复杂度均为O(1)

时间空间复杂度分析 – 循环队列和链队列对比

• 时间上：都是O(1)
• 空间上：
  • 循环队列：事先申请好空间，使用期间不释放
  • 链队列：每次申请和释放结点也会存在一些时间开销
  • 循环队列：固定长度，故存在存储元素个数和空间浪费的问题
  • 链队列：需要指针域，产生一些空间上的开销，在空间上更灵活

结语

​ 人生，就像是一个很大的栈演变。出生时你赤条条地来到人世，慢慢地长大，渐渐地变老，最终还得赤条条地离开世间。

​ 人生，又仿佛是一天一天小小的栈重现。童年父母每天抱你不断地进出家门，壮年你每天奔波于家与事业之间，老年你每天独自蹒跚于养老院的门里屋前。

​ 人生，更需要有进栈出栈精神的体现。在哪里跌倒，就应该在哪里爬起来。无论陷入何等困境，只要抬头能仰望蓝天，就有希望，不断进取，你就可以让出头之日重现。困难不会永远存在，强者才能勇往直前。

​ 人生，其实就是一个大大的队列演变。无知童年、快乐少年，稚傲青年，成熟中年，安逸晚年。

​ 人生，又是一个又一个小小的队列重现。春夏秋冬轮回年年，早中晚夜循环天天。变化的是时间，不变的是你对未来执著的信念。

​ 人生，更需要有队列精神的体现。南极到北极，不过是南纬90度到北纬90度的队列，如果你中途犹豫，临时转向，也许你就只能和企鹅相伴永远。可事实上，无论哪个方向，只要你坚持到底，你都可以到达终点。

​ ----摘自《大话数据结构》程杰