数据结构--第三章--栈和队列--知识点回顾_数据结构栈和队列知识点总结

第三章 栈和队列

一、基本知识点

(1)栈、队列和线性表的异同。

(2)顺序栈的基本运算算法设计。

(3)链栈的基本运算算法设计。

(4)顺序队的基本运算算法设计。

(5)环形队列和非环形队列的特点。

(6)链队的基本运算算法设计。

(7)利用栈/队列求解复杂的应用问题。

二、要点归纳、基本实现

栈的定义和基本运算：

1、栈的定义：后进先出表

2、栈的基本运算

（1）置空栈：s=NULL；

（2）判栈空：empty(s)；

（3) 入栈：push(s,x);

（4) 出栈：pop(s)；

（5) 读栈顶元素：top(s).

3、栈的存储结构

（1）顺序栈：即栈的顺序存储结构，是利用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设top指针指示栈顶元素在顺序栈中的位置。利用栈底位置相对不变的特性，两个顺序栈可以共享一个一维数据空间，以互补余缺。具体实现时可以将两个栈的栈底分别设在空间的两端，让它们的栈顶各自向中间延伸。

（2）链栈：可以克服顺序栈所带来的大量数据元素移动的不足。链栈中头指针就是栈顶指针。

4、栈的应用：表达式求值、括号匹配、递归调用，即将递归过程转变为非递归过程。

顺序栈

#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int top;				//栈指针
} SqStack;					//顺序栈类型

void InitStack(SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top=-1;
} 

void DestroyStack(SqStack *&s)
{
	free(s);
}

bool StackEmpty(SqStack *s)
{
	return(s->top==-1);
}

bool Push(SqStack *&s,ElemType e)
{
	if (s->top==MaxSize-1)    //栈满的情况，即栈上溢出
		return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}

bool Pop(SqStack *&s,ElemType &e)
{
	if (s->top==-1)		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	s->top--;
	return true;
} 

bool GetTop(SqStack *s,ElemType &e)
{
	if (s->top==-1) 		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	return true;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

链栈

#include <iostream>
using namespace std;
typedef char ElemType;
typedef struct linknode
{	
	ElemType data;				//数据域
	struct linknode *next;		//指针域
} LinkStNode;					//链栈类型

void InitStack(LinkStNode *&s)
{
	s=(LinkStNode *)malloc(sizeof(LinkStNode));
	s->next=NULL;
}

void DestroyStack(LinkStNode *&s)
{
	LinkStNode *p=s->next;
	while (p!=NULL)
	{	
		free(s);
		s=p;
		p=p->next;
	}
	free(s);	//s指向尾结点,释放其空间
}

bool StackEmpty(LinkStNode *s)
{
	return(s->next==NULL);
}

void Push(LinkStNode *&s,ElemType e)
{	LinkStNode *p;
	p=(LinkStNode *)malloc(sizeof(LinkStNode));
	p->data=e;				//新建元素e对应的结点p
	p->next=s->next;		 //插入p结点作为开始结点
	s->next=p;
}

bool Pop(LinkStNode *&s,ElemType &e)
{	LinkStNode *p;
	if (s->next==NULL)		//栈空的情况
   {
      return false;
   }
	p=s->next;				//p指向开始结点
	e=p->data;
	s->next=p->next;		//删除p结点
	free(p);				//释放p结点
	return true;
}

bool GetTop(LinkStNode *s,ElemType &e)
{	if (s->next==NULL)		//栈空的情况
   {
		return false;
   }
	e=s->next->data;
	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

队列的定义和基本运算

1、定义：先进先出表

2、队列的存储结构：

（1）顺序队列：设置两个指针：队头指针和队尾指针。

（2）链队列：增加一个头结点，令头指针指向头结点。

3、循环队列：

顺序队列

//非循环队列
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;						//队头和队尾指针
} SqQueue;

void InitQueue(SqQueue *&q)
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=-1;
}

void DestroyQueue(SqQueue *&q)			//销毁队列
{
	free(q);
}

bool QueueEmpty(SqQueue *q)				//判断队列是否为空
{
	return(q->front==q->rear);
}

bool enQueue(SqQueue *&q,ElemType e)	//进队
{	
   if (q->rear==MaxSize-1)				//队满上溢出
	{
   	return false;
	}			
	q->rear++;							//队尾增1
	q->data[q->rear]=e;					//rear位置插入元素e
	return true;						//返回真
}

bool deQueue(SqQueue *&q,ElemType &e)	//出队
{	
   if (q->front==q->rear)				//队空下溢出
	{
   	return false;
	}
	q->front++;
	e=q->data[q->front];
	return true;
}
-----------------------------------------------------------
//循环队列
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;		//队首和队尾指针
} SqQueue;

void InitQueue(SqQueue *&q)
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}

void DestroyQueue(SqQueue *&q)
{
	free(q);
}

bool QueueEmpty(SqQueue *q)
{
	return(q->front==q->rear);
}

bool enQueue(SqQueue *&q,ElemType e)
{	
   if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
	{
   	return false;
	}
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}

bool deQueue(SqQueue *&q,ElemType &e)
{	
   if (q->front==q->rear)		//队空下溢出
	{
   	return false;
	}
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

链队

#include <iostream>
using namespace std;
typedef char ElemType;
typedef struct DataNode
{	
	ElemType data;
	struct DataNode *next;
} DataNode;				//链队数据结点类型
typedef struct
{	
	DataNode *front;
	DataNode *rear;
} LinkQuNode;			//链队类型

void InitQueue(LinkQuNode *&q)
{	
	q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
	q->front=q->rear=NULL;
}

void DestroyQueue(LinkQuNode *&q)
{
	DataNode *p=q->front,*r;//p指向队头数据结点
	if (p!=NULL)			//释放数据结点占用空间
	{	r=p->next;
		while (r!=NULL)
		{	free(p);
			p=r;r=p->next;
		}
	}
	free(p);
	free(q);				//释放链队结点占用空间
}

bool QueueEmpty(LinkQuNode *q)
{
	return(q->rear==NULL);
}

void enQueue(LinkQuNode *&q,ElemType e)
{	
   DataNode *p;
	p=(DataNode *)malloc(sizeof(DataNode));
	p->data=e;
	p->next=NULL;
	if (q->rear==NULL)		//若链队为空,则新结点是队首结点又是队尾结点
		q->front=q->rear=p;
	else
	{	q->rear->next=p;	//将p结点链到队尾,并将rear指向它
		q->rear=p;
	}
}

bool deQueue(LinkQuNode *&q,ElemType &e)
{	
   DataNode *t;
	if (q->rear==NULL)		//队列为空
		return false;
	t=q->front;				//t指向第一个数据结点
	if (q->front==q->rear)  //队列中只有一个结点时
		q->front=q->rear=NULL;
	else					//队列中有多个结点时
		q->front=q->front->next;
	e=t->data;
	free(t);
	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

三、练习题

1．选择题

（1）若让元素 1，2，3，4，5 依次进栈，则出栈次序不可能出现在（ ） 种情况。

A．5，4，3，2，1

B．2，1，5，4，3

C．4，3，1，2，5

D．2， 3，5，4，1

答案：C

解释：栈是后进先出的线性表，不难发现 C 选项中元素 1 比元素 2 先 出栈，违背了栈的后进先出原则，所以不可能出现 C 选项所示的情况。

（2）若已知一个栈的入栈序列是 1，2，3，…，n，其输出序列为 p1， p2，p3，…，pn，若 p1=n，则 pi 为（ ）。

A．i

B．n-i

C．n-i+1

D．不确定

答案：C

解释：栈是后进先出的线性表，一个栈的入栈序列是 1，2，3，…，n， 而输出序列的第一个元素为 n，说明 1，2，3，…，n 一次性全部进栈，再进行输出，所以 p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。

A ． r-f

B ． (n+f-r)%n

C ． n+r-f

D．（n+r-f)%n

答案：D

解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上 MAXSIZE（本题为 n）， 然后与 MAXSIZE（本题为 n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top 指向栈顶. 若想摘除栈顶结点，并将删除结点的值保存到 x 中，则应执行操作（ ）。

A．x=top->data;top=top->link；

B．top=top->link;x=top->link；

C．x=top;top=top->link；

D．x=top->link；

答案：A

解释：x=top->data 将结点的值保存到 x 中，top=top->link 栈顶指针指 向栈顶下一结点，即摘除栈顶结点。

（5）设有一个递归算法如下

int fact(int n) //n 大于等于 0 
{ 
   if(n<=0) return 1; 
   else return n*fact(n-1); 
} 
1
2
3
4
5

则计算 fact(n)需要调用该函数的次数为（ ）。

A． n+1

B． n-1

C． n

D． n+2

答案：A

解释：特殊值法。设 n=0，易知仅调用一次 fact(n)函数，故选 A。

（6）栈在 （ ）中有所应用。

A．递归调用

B．函数调用

C．表达式求值

D．前 三个选项都有

答案：D

解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。

（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。

A．队列

B．栈

C．线性表

D．有序表

答案：A

解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。

（8）设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和 e1，则栈 S 的容量至少应该是（ ）。

A．2

B．3

C．4

D． 6

答案：B

解释：元素出队的序列是 e2、e4、e3、e6、e5 和 e1，可知元素入队的序列是 e2、e4、e3、e6、e5 和 e1，即元素出栈的序列也是 e2、e4、e3、e6、e5 和 e1，而元素 e1、e2、e3、e4、e5 和 e6 依次进入栈，易知栈 S 中最多同时存在 3 个元素，故栈 S 的容量至少为 3。

（9）若一个栈以向量 V[1…n]存储，初始栈顶指针 top 设为 n+1，则元素x 进栈的正确操作是( )。

A．top++; V[top]=x;

B．V[top]=x; top++;

C．top–; V[top]=x;

D．V[top]=x; top–;

答案：C

解释：初始栈顶指针 top 为 n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间 V[1…n]中，所以进栈时 top 指针先下移变为 n，之后将元素 x 存储在 V[n]。

（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。

A．线性表的顺序存储结构

B．队列

C. 线性表的链式存储结构

D. 栈

答案：D

解释：利用栈的后进先出原则。

（11）用链接方式存储的队列，在进行删除运算时（ ）。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

答案：D

解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。

（12）循环队列存储在数组 A[0…m]中，则入队时的操作为（ ）。

A. rear=rear+1

B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m

D. rear=(rear+1)%(m+1)

答案：D

解释：数组 A[0…m]中共含有 m+1 个元素，故在求模运算时应除以 m+1。

（13）最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（）。

A. (rear+1)%n==front

B. rear==front

C. rear+1==front

D. (rear-1)%n==front

答案：B

解释：最大容量为 n 的循环队列，队满条件是(rear+1)%n==front，队空条件是 rear==front。

（14）栈和队列的共同点是（ ）。

A. 都是先进先出

B. 都是先进后出

C. 只允许在端点处插入和删除元素

D. 没有共同点

答案：C

解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。

（15）一个递归算法必须包括（ ）。

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D. 终止条件和迭代部分

答案：B