数据结构第三章：栈

Posted on | In , | |

Abstract：栈和队列。

3.1 栈—栈的定义及基本运算

栈和队列：逻辑结构与线性表相同，特点在于受限制的运算

  • 栈：后进先出（秤砣）
  • 队列：先进先出（管道）

栈：限制在表的一端进行插删操作的线性表；后进先出的线性表，简称LIFO 表

  • 栈顶：允许插删的一端
  • 栈底：固定端
  • 空栈：表中无元素时

栈

基本操作：

⑴ 栈初始化：Init_Stack(s)
初始条件：栈s 不存在
操作结果：构造空栈。

⑵ 判栈空：Empty_Stack(s)
初始条件：栈s 已存在
操作结果：若s 为空栈返回为1，否则返回为0。

⑶ 入栈： Push_Stack(s，x)
初始条件：栈s 已存在
操作结果：在栈s 的顶部插入一个新元素x， x 成为新的栈顶元素。栈发生变化。

⑷ 出栈：Pop_Stack(s)
初始条件：栈s 存在且非空
操作结果：栈s 的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。

⑸ 读栈顶元素：Top_Stack(s)
初始条件：栈s 存在且非空
操作结果：栈顶元素作为结果返回，栈不变化。

3.1 栈—栈的存储实现和运算实现

1.顺序栈

顺序栈：利用顺序存储方式实现的栈；类似于顺序表的定义,栈中的数据元素用一个预设的足够长度的一维数组来实现：datatype data[MAXSIZE]，栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，用一个int top 来作为栈顶的指针，指明当前栈顶的位置，同样将data 和top 封装在一个结构中，顺序栈的类型描述如下：

1
2
3
4
5
#define MAXSIZE 1024
typedef struct{
    datatype data[MAXSIZE];
    int top;
}SeqStack

定义一个指向顺序栈的指针：SeqStack *s;

通常0 下标端设为栈底，这样空栈时栈顶指针top=-1; 入栈时，栈顶指针加１，即s->top++; 出栈时，栈顶指针减１，即s->top—。栈操作的示意图如图所示

栈顶指针top与栈中数据元素的关系

图(a)是空栈，图(c)是A、B、C、D、E 5 个元素依次入栈之后，图(d)是在图(c)之后E、D 相继出栈，此时栈中还有3 个元素，或许最近出栈的元素D、E 仍然在原先的单元存储着，但top 指针已经指向了新的栈顶，则元素D、E 已不在栈中了

栈顶元素：s->data[s->top]

基本操作：

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
⑴ 置空栈：首先建立栈空间，然后初始化栈顶指针。
SeqStack *Init_SeqStack()
{ SeqStack *s;
s=malloc(sizeof(SeqStack));
s->top= -1; return s;
}

⑵ 判空栈
int Empty_SeqStack(SeqStack *s)
{ if (s->top= = -1) return 1;
else return 0;
}

⑶ 入栈
int Push_SeqStack (SeqStack *s, datatype x)
{if (s->top= =MAXSIZE-1) return 0; /*空栈可入，但栈满不能入栈*/
else { s->top++;
s->data[s->top]=x;
return 1;
}
}

⑷ 出栈
int Pop_SeqStack(SeqStack *s, datatype *x)
{ if (Empty_SeqStack ( s ) ) return 0; /*栈空不能出栈*/
else { *x=s->data[s->top];
s->top--; return 1; } /*栈顶元素存入*x，返回*/
}

⑸ 取栈顶元素
datatype Top_SeqStack(SeqStack *s)
{ if ( Empty_SeqStack ( s ) ) return 0; /*栈空*/
else return (s->data[s->top] );
}

1. 对于顺序栈，入栈时，首先判栈是否满了，栈满的条件为：s->top= =MAXSIZE-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。
2. 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。

2.链栈

链栈：链式存储结构实现的栈，通常用单链表表示；

1
2
3
4
5
typedef struct node
{
	datatype data;
	struct node *next;
}StackNode, *LinkList;

说明top 为栈顶指针： LinkStack top ;因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。

链栈

基本操作：

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
⑴ 置空栈
LinkStack Init_LinkStack（）
{ return NULL;
}

⑵ 判栈空
int Empty_LinkStack（LinkStack top ）

{ if（top==-1） return 1;
else return 0;
}

⑶ 入栈
LinkStack Push_LinkStack（LinkStack top, datatype x）
{ StackNode *s;
s=malloc（sizeof（StackNode））;
s->data=x;
s->next=top;
top=s;
return top;
}

⑷ 出栈
LinkStack Pop_LinkStack (LinkStack top, datatype *x)
{ StackNode *p;
if （top= =NULL） return NULL;
else { *x = top->data;
p = top;
top = top->next;
free (p);
return top;
}
}

3.2 栈的应用举例

1.简单应用：数制转换问题

将十进制数N 转换为r 进制的数，其转换方法利用辗转相除法：以N=3456，r=8 为例。

算法思想如下：当N>0 时重复1，2

1． 若N≠0，则将N % r 压入栈s 中，执行2;若N=0，将栈s 的内容依次出栈，算法结束。
2． 用N / r 代替N

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define L 10
void conversation(int N, int r)
{
	int s[L], top
	int x;
	top = -1;
	while(N)
	{
		s[++top]=N%r;
		N = N/r;
	}
	while (top!=-1)
	{
		x=s[top--];
		printf("%d", x);
	}
}

2.利用栈实现迷宫的求解——回溯法

迷宫

试探方向：在上述表示迷宫的情况下，每个点有8 个方向去试探，如当前点的坐标(x,y)，与其相邻的8 个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），
因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这8 个方向的坐标增量放在一个结构数组move [ 8 ]中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。

与(x,y)相邻的8个点及坐标

入栈

迷宫求解算法思想如下：
1． 栈初始化;
2． 将入口点坐标及到达该点的方向（设为－１）入栈
3． while (栈不空)
{ 栈顶元素＝＞（x , y , d）
出栈;
求出下一个要试探的方向d++ ;
while （还有剩余试探方向时）
{ if （d 方向可走）
则{ （x , y , d）入栈;
求新点坐标(i, j ) ;
将新点（i , j）切换为当前点（x , y） ;
if ( (x ,ｙ)= =(ｍ,n) ) 结束;
else 重置d=0 ;
}
else d++ ;
}
}

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
int path( maze move )
int maze[m][n];


item move[8];
{ SeqStack	s;
  datetype	temp;
  int		x, y, d, i, j;
  temp.x = 1; temp.y = 1; temp.d = -1;
  Push - _SeqStack( s temp );
  while ( !Empty_SeqStack( s ) )
  {
	  Pop_SeqStack( s, ＆ temp );
	  x = temp.x; y = temp.y; d = temp.d + 1;
	  while ( d < 8 )
	  {
		  i = x + move[d].x; j = y + move[d].y;
		  if ( maze[i][j] = = 0 )
		  {
			  temp = { x, y, d };
			  Push_SeqStack( s, temp );
			  x = i; y = j; maze[x][y] = -1;
			  if ( x == m && y = = n )
				  return(1);    /*迷宫有路*/
			  else d = 0;
		  }else d++;
	  } /*while (d<8)*/
  } /*while */
  return(0);                                    /*迷宫无路*/
}

栈中保存的就是一条迷宫的通路.

3. 表达式求值

表达式是由运算对象、运算符、括号组成的有意义的式子。运算符从运算对象的个数上分，有单目运算符和双目运算符；从运算类型上分，有算术运算、关系运算、逻辑运算。在此仅限于讨论只含二目运算符的算术表达式。

1． 中缀表达式求值：中缀表达式：每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：+ 、- 、*、/、%、^（乘方）和括号（）。

设运算规则为：
．运算符的优先级为：（）——> ^ ——>＊、/、%——> +、- ；
．有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；
．乘方连续出现时先算最右面的；

表达式作为一个满足表达式语法规则的串存储，如表达式“32^（4+22-１3）-5”,它的的求值过程为：自左向右扫描表达式，当扫描到32 时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：需要两个栈：对象栈s1 和算符栈s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符。

2.后缀表达式：

不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

运用后缀表达式进行计算的具体做法：

建立一个栈S 。从左到右读表达式，如果读到操作数就将它压入栈S中，如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作数运算，再将运算的结果代替原栈顶的n项，压入栈S中 。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。

3.前缀表达式：运算符位于操作数之前。

4.中缀表达式：常用的算术表示方法。

举例：
(3 + 4) × 5 - 6 就是中缀表达式

  • × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式

CSDN.前缀、中缀、后缀表达式

3.3 队列—队列的定义及基本运算

队列：先进先出FIFO，允许插入的一端叫队尾rear，允许删除的一端叫队头front（插入与删除操作分属两端）。

基本操作：

⑴ 队列初始化：Init_Queue(q)
初始条件： 队q 不存在。
操作结果： 构造了一个空队。

⑵ 入队操作： In_Queue(q,x),
初始条件： 队q 存在。
操作结果： 对已存在的队列q，插入一个元素x 到队尾，队发生变化。

⑶ 出队操作： Out_Queue(q,x)
初始条件: 队q 存在且非空
操作结果： 删除队首元素，并返回其值，队发生变化。

⑷ 读队头元素：Front_Queue(q,x)
初始条件: 队q 存在且非空
操作结果： 读队头元素，并返回其值，队不变；

⑸ 判队空操作：Empty_Queue(q)
初始条件： 队q 存在
操作结果： 若q 为空队则返回为1，否则返回为0。

3.3 队列—队列的存储实现及运算实现

与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。

1.顺序队

队头队尾都是活动的，有队头队尾两个指针。

1
2
3
4
5
define MAXSIZE 1024 //队列的最大容量
typedef struct{
    datatype data[MAXSIZE]; //队员的存储空间
    int rear, front; //定义队头队尾的指针
}SeQueue;

定义一个指向队的指针变量：SeQueue sq;
申请一个顺序队的存储空间： s= malloc(sizeof(SeQueue));
队列的数据区为：sq->data[0]——sq->data[MAXSIZE - 1]
*队头队尾指针：sq->front; sq->rear;（若垂直方向，则下面队头上面队尾）

设队头指针指向队头元素前面一个位置，队尾指针指向队尾元素（这样的设置是为了某些运算的方便，并不是唯一的方法）。

置空队则为：sq->front=sq->rear=-1;

在不考虑溢出的情况下，入队操作队尾指针加1，指向新位置后，元素入队。操作如下：
sq->rear++;
sq->data[sq->rear]=x; /原队尾元素送x 中/

在不考虑队空的情况下，出队操作队头指针加1，表明队头元素出队。操作如下：

sq->front++;
x=sq->data[sq->front];

队中元素的个数：m=(sq->rear)-(q->front);
队满时：m= MAXSIZE； 队空时：m=0。

循环队列

按照上述思想建立的空队及入队出队示意图如图所示，设MAXSIZE=10。从图中可以看到，随着入队出队的进行，会使整个队列整体向后，这样就出现了图中的现象：队尾指针已经移到了最后,再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”，这是由于“队尾入队头出”这种受限制的操作所造成。解决假溢出的方法之一是将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队”，“循环队”的示意图如图所示。

队列操作图

循环队列图

因为是头尾相接的循环结构，入队时的队尾指针加1 操作修改为：
sq->rear=(sq->rear+1) % MAXSIZE;

出队时的队头指针加1 操作修改为：
sq->front=(sq->front+1) % MAXSIZE;

设MAXSIZE=10，下图是循环队列操作示意图：

循环队列

从循环队可以看出，(a)中具有a5 、a6 、a7 、a8 四个元素，此时front=4,rear=8；随着a9~a14 相继入队，队中具有了10 个元素—-队满，此时front=4,rear=4,如（b）所示，可见在队满情况下有：front==rear。若在（a）情况下，a5~a8 相继出队，此时队空， front=4，rear=4，如（c）所示，即在队空情况下也有：front==rear。就是说“队满”和“队空”的条件是相同的了。这显然是必须要解决的一个问题。

方法之一是附设一个存储队中元素个数的变量如num，当num==0 时队空，当num==MAXSIZE 时为队满。

另一种方法是少用一个元素空间，把图（d）所示的情况就视为队满，此时的状态是队尾指针加1 就会从后面赶上队头指针，这种情况下队满的条件是： (rear+1) %MAXSIZE==front，也能和空队区别开。

循环队列基本操作

typedef struct {
datatype data[MAXSIZE]; /数据的存储区/
int front,rear; /队头队尾指针/
int num; /队中元素的个数/
}c_SeQueue; /循环队/

⑴ 置空队
c_SeQueue* Init_SeQueue()
{ q=malloc(sizeof(c_SeQueue));
q->front=q->rear=MAXSIZE-1;
q->num=0;
return q;
}

⑵ 入队
int In_SeQueue ( c_SeQueue q , datatype x)
{ if (num==MAXSIZE)
{ printf(＂队满＂);
return –1; /队满不能入队/
}
else
{ q->rear=(q->rear+1) % MAXSIZE;
q->data[q->rear]=x;
num++;
return 1; /入队完成*/
}
}

⑶ 出队
int Out_SeQueue (c_SeQueue q , datatype x)
{ if (num==0)
{ printf(＂队空＂)；
return –1; /队空不能出队/
}
else
{ q->front=(q->front+1) % MAXSIZE;
x=q->data[q->front]; /读出队头元素/
num—;
return 1; /出队完成*/
}
}

⑷ 判队空
int Empty_SeQueue(c_SeQueue *q)
{ if (num==0) return 1;
else return 0;
}

2.链队

链队：链式存储的队；和链栈类似，用单链表来实现链队，根据队的FIFO 原则，为了操作上的方便，我们分别需要一个头指针和尾指针，如：

链队

头指针front 和尾指针rear 是两个独立的指针变量，从结构性上考虑，通常将二者封装在一个结构中。

链队的描述：

1
2
3
4
5
6
7
typedef struct node
{
    datatype data;
    struct node *next;}QNode;/*链队结点的类型*/
    typedef struct
    {
    QNode *front, *rear;}LQueue; /*将头尾指针封装在一起的链队*/

定义一个指向链队的指针：LQueue *q;

带头结点的链队：

头尾指针封装在一起的链队

链队的基本运算如下：

(1) 创建一个带头结点的空队：
LQueue Init_LQueue()
{ LQueue q,p;
q=malloc(sizeof(LQueue)); /申请头尾指针结点/
p=malloc(sizeof(QNode)); /申请链队头结点*/
p->next=NULL; q->front=q->rear=p;
return q;
}

(2) 入队
void In_LQueue(LQueue q , datatype x)
{ QNode p;
p=malloc(sizeof(QNnode)); /申请新结点/
p->data=x; p->next=NULL;
q->rear->next=p;
q->rear=p;
}

(3) 判队空
int Empty_LQueue( LQueue *q)
{ if (q->front==q->rear) return 0;
else return 1;
}

(4) 出队
int Out_LQueue(LQueue q , datatype x)
{ QNnode p;
if (Empty_LQueue(q) )
{ printf (＂队空＂)； return 0;
} /队空，出队失败/
else
{ p=q->front->neat;
q->front->next=p->next; x=p->data;/队头元素放x 中/
free(p);
if (q->front->next==NULL)
q->rear=q->front;
/只有一个元素时，出队后队空，此时还要要修改队尾指针参考图/
return 1;
}
}

3.5 队列应用举例

例：求迷宫的最短路径：

现要求设计一个算法找一条从迷宫入口到出口的最短路径。本算法要求找一条迷宫的最短路径，算法的基本思想为：从迷宫入口点（1,1）出发，向四周搜索，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路径。

有关迷宫的数据结构、试探方向、如何防止重复到达某点以避免发生死循环的问题与之前的例子处理相同，不同的是：如何存储搜索路径。在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点先向下搜索，故引进一个“先进先出”数据结构———队列来保存已到达的坐标点。到达迷宫的出口点(m,n)后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，因此，用一个结构数组sq[num]作为队列的存储空间，因为迷宫中每个点至多被访问一次，所以num 至多等于m*n。sq 的每一个结构有三个域：x,y 和pre，其中x,y 分别为所到达的点的坐标，pre 为前驱点在sq 中的坐标，是一个静态链域。除sq 外，还有队头、队尾指针：front 和rear 用来指向队头和队尾元素。

队的定义如下：

typedef struct
{ int x,y;
int pre;
}sqtype;
sqtype sq[num];
int front,rear;

初始状态，队列中只有一个元素sq[１]记录的是入口点的坐标（１,１），因为该点是出发点，因此没有前驱点，pre 域为－１，队头指针front 和队尾指针rear 均指向它，此后搜索时都是以front 所指点为搜索的出发点，当搜索到一个可到达点时，即将该点的坐标及front 所指点的位置入队，不但记下了到达点的坐标，还记下了它的前驱点。front 所指点的８个方向搜索完毕后，则出队，继续对下一点搜索。搜索过程中遇到出口点则成功，搜索结束，打印出迷宫最短路径，算法结束；或者当前队空即没有搜索点了，表明没有路径算法也结束。

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
void path( maze move )
int maze[m][n] ；                                                /*迷宫数组*/
item move[8] ；                                                  /*坐标增量数组*/
{
	sqtype	sq[NUM];
	int	front, rear ；
	int x, y, i, j, v;
	front		= rear = 0;
	sq[０].x		= 1; sq[０].y = 1; sq[０].pre = -1;       /*入口点入队*/
	maze[1, 1]	= -1;
	while ( front <= rear )                                 /*队列不空*/
	{
		x = sq[front].x; y = sq[front].y;
		for ( v = 0; v < 8; v++ )
		{
			i = x + move[v].x; j = x + move[v].y;
			if ( maze[i][j] == 0 )
			{
				rear++;
				sq[rear].x	= i; sq[rear].y = j; sq[rear].pre = front;
				maze[i][j]	= -1;
			}
			if ( i == m && j == n )
			{
				printpath( sq, rear );  /*打印迷宫*/
				restore( maze );        /*恢复迷宫*/
				return(1);
			}
		} /*for v*/
		front++;                                /*当前点搜索完，取下一个点搜索*/
	} /*while*/
	return(0);
} /*path*/


void printpath( sqtype sq[], int rear )                 /*打印迷宫路径*/
{
	int i;
	i = rear;
	do
	{
		printf( ＂ (% d, % d)􀃅 ＂, sq[i].x, sq[i].y );
		i = sq[i].pre;                          /*回溯*/
	}
	while ( i != -1 );
} /*printpath*/

迷宫搜索过程如图：

迷宫搜索过程

队列中的数据

运行结果： (6,8)􀃅 (5,7)􀃅 (4,6)􀃅(4,5)􀃅 (3,4)􀃅 (3,3)􀃅 (2,2)􀃅(1,1)

在上面的例子中，不能采用循环队列，因为在本问题中，队列中保存了探索到的路径序列，如果用循环队列，则把先前得到的路径序列覆盖掉。而在有些问题中，如持续运行的实时监控系统中，监控系统源源不断的收到监控对象顺序发来的信息如报警，为了保持报警信息的顺序性，就要按顺序一一保存，而这些信息是无穷多个，不可能全部同时驻留内存，可根据实际问题，设计一个适当大的向量空间，用作循环队列，最初收到的报警信息一一入队，当队满之后，又有新的报警到来到时，新的报警则覆盖掉了旧的报警，内存中始终保持当前最新的若干条报警，以便满足快速查询。

Thanks!