您的位置: 网站首页 > 程序开发 > 数据结构 > 第3章 栈和队列 > 【3.1 栈】

3.1 栈

 

在第2章中学习了线性表,其中对于线性表的操作允许在表的任何位置进行,使用比较灵活,同时也使得实现操作时需要考虑的因素较多。本章要介绍的栈和队列是一类操作受限制的特殊线性表,其特殊性在于限制线性表插入和删除等运算的位置。栈和队列在各种类型的软件系统中应用广泛。栈技术被广泛应用于编译软件和程序设计中,队列技术被广泛应用在操作系统和事务管理中。

栈和队列是两种重要的线性数据结构,也是两种特殊的线性数据结构。从数据的逻辑结构角度看,栈和队列是线性表;从运算的角度看,栈和队列的基本运算是线性表运算的子集,是操作受限的线性表。本章介绍栈和队列的概念、存储结构和基本运算的实现算法。

本章主要内容

&        栈和队列的特性及它们之间的差异

&        顺序栈上和链栈上实现栈的基本操作

&        链队上和顺序队上实现队列的基本操作

&        栈和队列各种基本操作的实现原理

3.1 

我们在编写程序的时候经常会发现,程序中处理的信息往往具有线性的结构,但并不需要用到线性表数据类型中的所有操作。在某些特定的应用中,检查、修改、插入和删除操作仅在表的一端进行。由于这种受限的线性结构在程序设计中用得十分普遍,因此,有必要将它作为单独的抽象数据类型来考虑。本节将讨论这种重要的受限线性结构——栈。

3.1.1  抽象数据类型栈的定义

栈是一种特殊的线性表,这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶,另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。不含任何数据元素的栈称为空栈。

栈的特点是后进先出。举一个例子说明栈结构的特征,假设有一个很窄的死胡同,胡同里能容纳若干人,但每次只能容许一个人进出。现有5个人,分别编号为①~⑤,按编号的顺序依次进入此胡同,如图3-1所示。此时若编号为④的人要退出胡同,必须等⑤退出后才可以。若①要退出,则必须等到⑤④③②依次都退出后才行。这里,人进出胡同的原则是后进去的先出来。死胡同示意图如图3-1所示。

3-1  死胡同示意图

 

栈可以比作这里的死胡同,栈顶相当于胡同口,栈底相当于胡同的另一端,进、出胡同可看作栈的插入、删除运算。插入、删除都在栈顶进行,相当于进出都经过胡同口。这表明栈修改的原则是先进后出(或称后进先出)。因此,栈又称为后进先出线性表。在栈顶进行插入运算,被称为进栈,在栈顶进行删除运算,被称为出栈。

栈的基本运算至少应包括以下5种:

1)初始化栈InitStack(st)。其作用是设置一个空栈st

2)进栈Push(st,x)。其作用是将元素x插入栈st中,使x成为栈st的栈顶元素。

3)出栈Pop(st,x)。其作用是当栈st不空时,将栈顶元素赋给x,并从栈中删除当前栈顶。

4)取栈顶元素GetTop(st)。若栈st不空,则由x返回栈顶元素;当栈st为空时,结果为一特殊标志。

5)判断栈空StackEmpty(st)。若栈st为空栈,则结果为1;否则结果为0

【例3-1跟踪以下代码,显示每次调用后栈中的内容。

InitStack(st);                      /*设置一个空栈st*/

Push(st,'A');                       /*将元素A插入栈st*/

Push(st,'B');                       /*将元素B插入栈st*/

Push(st,'C');                       /*将元素C插入栈st*/

Pop(st,x);                          /*从栈中删除当前栈顶元素*/

Pop(st,x);                          /*从栈中删除当前栈顶元素*/

Push(st,'D');                       /*将元素D插入栈st*/

Push(st,'E');                       /*将元素E插入栈st*/

Push(st,'F');                       /*将元素F插入栈st*/

Pop(st,x);                          /*从栈中删除当前栈顶元素*/

Push(st,'G');                       /*将元素G插入栈st*/

Pop(st,x);                          /*从栈中删除当前栈顶元素*/

Pop(st,x);                          /*从栈中删除当前栈顶元素*/

Pop(st,x);                          /*从栈中删除当前栈顶元素*/

解:栈中的内容见以下说明。

InitStack(st);                      /*空栈*/

Push(st,'A');                       /*栈内容:A*/

Push(st,'B');                       /*栈内容:A,B*/

Push(st,'C');                       /*栈内容:A,B,C*/

Pop(st,x);                          /*栈内容:A,B*/

Pop(st,x);                          /*栈内容:A*/

Push(st,'D');                       /*栈内容:A,D*/

Push(st,'E');                       /*栈内容:A,D,E*/

Push(st,'F');                       /*栈内容:A,D,E,F*/

Pop(st,x);                          /*栈内容:A,D,E*/

Push(st,'G');                       /*栈内容:A,D,E,G*/

Pop(st,x);                          /*栈内容:A,D,E*/

Pop(st,x);                          /*栈内容:A,D*/

Pop(st,x);                          /*栈内容:A*/

3.1.2  栈的表示和实现

1.栈的顺序存储及其基本运算

和线性表类似,栈也有两种存储结构:顺序存储结构和链式存储结构。

栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组和一个记录栈顶元素位置的变量组成。习惯上将栈底放在数组下标小的那端。假设用一维数组sq[5](下标04)表示一个栈,则需使用一个变量top记录当前栈顶下标值。图3-2所示为这个顺序栈的几种状态。

3-2  顺序栈的几种状态

a)表示顺序栈为空栈,这也是初始化运算得到的结果。此时栈顶下标值top= -1。如果作出栈运算,则产生“下溢”。

b)表示栈中只含一个元素A,在(a)的基础上用进栈运算Push(sq,'A'),可以得到这种状态。此时栈顶下标值top=0

c)表示在(b)基础上又有2个元素BC先后进栈,此时栈顶下标值top=2

d)表示在(c)状态下,执行一次Pop(sq,x)运算得到。此时栈顶下标值top=1。故B为当前的栈顶元素。

e)表示在(d)状态下,执行2Pop(sq,x)运算得到。此时栈顶下标值top= -1,又变成空栈状态。

顺序栈类型定义如下:

#define StackSize                       /*顺序栈的初始分配空间*/

typedef struct

{  

   ElemType data[StackSize];            /*保存栈中元素*/

   int top;                             /*栈指针*/

} SqStack;

顺序栈被定义为一个结构体类型,它有两个域:datatopdata为一个一维数组,用于存储栈中元素,ElemType为栈元素的数据类型,可以根据需要而指定为某种具体的类型。topint型,它的实际取值范围为0StackSize-1

顺序栈st的四要素:

·    栈空  st.top= -1

·    栈满  st.top=StackSize-1

·    进栈操作  st.top++; st.data[st.top]=x

·    出栈操作  x=st.data[st.top]; st.to--

顺序栈的基本运算算法如下。

1)初始化栈运算算法。

用于创建一个空栈,并将栈顶下标top初始化为-1

void InitStack(SqStack &st)                 /*st为引用型参数*/

{

   st.top=-1;

}

2)进栈运算算法。

其主要操作是:栈指针加1,将进栈元素放进栈顶位置上。

int Push(SqStack &st,ElemType x)            /*进栈运算,st为引用型参数*/

{

   if(st.top==StackSize-1)                  /*栈满*/

     return 0;

   else                                     /*栈不满*/

   {

     st.top++;

     st.data[st.top]=x;

     return 1;      

   }

}

3)出栈运算算法。

其主要操作是:先将栈顶元素取出,然后将栈指针减1

int Pop(SqStack &st,ElemType &x)            /*出栈运算,stx为引用型参数*/

{

   if(st.top==-1)                           /*栈空*/

     return 0;

   else                                     /*栈不空*/

   {

     x=st.data[st.top];

     st.top--;

     return 1;

   }

}

4)取栈顶元素运算算法。

其主要操作是:将栈指针处的元素取出赋给变量x

int GetTop(SqStack st,ElemType &x)      /*取栈顶元素,x为引用型参数*/

{

   if(st.top==-1)                       /*栈空*/

     return 0;

   else

   {

     x=st.data[st.top];

     return 1;

   }

}

5)判断栈空运算算法。

其主要操作是:若栈为空(top== -1)则返回1,否则返回0

int StackEmpty(SqStack st)              /*判断栈空运算*/

{

   if(st.top==-1)                       /*栈空*/

     return 1;

   else                                 /*栈不空*/

     return 0;

}

当顺序栈的基本运算函数设计好后,给出以下程序调用这些基本操作函数,读者可以对照程序执行结果进行分析,进一步体会顺序栈各种操作的实现过程。

void main()

{

   SqStack st;                          /*定义顺序栈st*/

   ElemType e;                          /*定义栈元素e的类型*/

   InitStack(st);                       /*创建空栈st*/

   printf("%s\n",(StackEmpty(st)==1?"":"不空"));

   printf("a进栈\n");Push(st,'a');

   printf("b进栈\n");Push(st,'b');

   printf("c进栈\n");Push(st,'c');

   printf("d进栈\n");Push(st,'d');

   printf("%s\n",(StackEmpty(st)==1?"":"不空"));

   GetTop(st,e);                        /*取栈顶元素*/

   printf("栈顶元素:%c\n",e);

   printf("出栈次序:");

   while(!StackEmpty(st))               /*栈不空时循环*/     

   {

     Pop(st,e);                         /*栈不空时元素出栈*/

     printf("%c ",e);                   /*显示出栈元素*/

   }

   printf("\n");

}

上述程序的执行结果如下:

栈空

a进栈

b进栈

c进栈

d进栈

栈不空

栈顶元素:d

出栈次序:d c b a

【例3-2利用栈的基本运算编写一个算法,输入若干整数,以0标识输入结束。然后按与输入相反次序输出这些整数。

解:使用一个栈实现本例要求,先将输入的整数进栈,然后出栈并输出。对应的算法如下。

void Invert()

{

   int n;                               /*ElemType类型改为int*/

   SqStack st;                          /*定义顺序栈st*/

   InitStack(st);                       /*创建空栈st*/

   printf("输入一串整数(0标识结束)");

   while (1)

   {

     scanf("%d",&n);

     if (n==0) break;                   /*输入值n0时退出循环*/

     Push(st,n);                        /*每输入一个n进栈*/

   }

     printf("输出序列:");

     while(!StackEmpty(st))             /*栈不空时循环*/

   {

     Pop(st,n);                         /*出栈n*/

     printf("%d ",n);                   /*输出n*/

   }

}

2.栈的链式存储及其基本运算

栈的链式存储结构是以某种形式的链表作为栈的存储结构,栈的链式存储结构简称为链栈,其组织形式与单链表类似,如图3-3所示。其中,单链表的第一个节点就是链栈栈顶节点。ls称为栈顶指针。类似地,栈由栈顶指针ls唯一确定。栈中的其他节点通过它们的next域链接起来。栈底节点的next域为NULL。因链栈本身没有容量限制,所以在用户内存空间的范围内不会出现栈满情况。

3-3  用不带头节点的单链表表示链栈

链栈的类型定义如下:

typedef struct stnode

{  

   ElemType data;                       /*存储节点数据*/

   struct stnode *next;                 /*指针域*/

} LinkStack;

链栈ls的四要素如下:

·    栈空  ls==NULL

·    栈满  不存在

·    进栈操作  p->next=ls; ls=p

·    出栈操作  ls=ls->next

栈的基本运算算法如下。

1)初始化栈运算算法。

创建一个栈头节点*ls,用ls=NULL标识栈为空栈。

void InitStack(LinkStack *&ls)          /*ls为引用型参数*/

{

   ls=NULL;

}

2)进栈运算算法。

其主要操作是:先创建一个新节点,其data域值为x;然后将该节点插入到单链表表头作为栈顶节点。

void Push(LinkStack *&ls,ElemType x)    /*进栈运算,ls为引用型参数*/

{

   LinkStack *p;

   p=(LinkStack *)malloc(sizeof(LinkStack));

   p->data=x;

   p->next=ls;

   ls=p;

}

3)出栈运算算法。

其主要操作是:将栈顶节点(即ls所指节点)的data域值赋给x,然后删除该栈顶节点。

int Pop(LinkStack *&ls,ElemType &x)     /*出栈运算,ls为引用型参数*/

{

   LinkStack *p;

   if(ls==NULL)                          /*栈空,下溢出*/

      return 0;

   else

   {

      p=ls;

      x=p->data;

      ls=p->next;

      free(p);

      return 1;

      }

}

4)取栈顶元素运算算法。

其主要操作是:将栈顶节点(即ls所指节点)的data域值赋给x

int GetTop(LinkStack *ls,ElemType &x)       /*取栈顶元素运算*/

{

   if(ls==NULL)                              /*栈空,下溢出*/

      return 0;

   else

   {

      x=ls->data;

      return 1;

   }

}

5)判断栈空运算算法。

其主要操作是:若栈为空(即ls==NULL)则返回1,否则返回0

int StackEmpty(LinkStack *ls)               /*判断栈空运算*/

{

   if(ls==NULL)

      return 1;

   else

      return 0;

}

当链栈的基本运算函数设计好后,给出以下程序调用这些基本操作函数,读者可以对照程序执行结果进行分析,进一步体会链栈各种操作的实现过程。

void main()

{

   LinkStack *ls;                           /*定义链栈ls*/

   ElemType e;                              /*定义栈元素e的数据类型*/

   InitStack(ls);                           /*创建链栈ls*/

   printf("%s\n",(StackEmpty(ls)==1?"":"不空"));

   printf("a进栈\n");Push(ls,'a');

   printf("b进栈\n");Push(ls,'b');

   printf("c进栈\n");Push(ls,'c');

   printf("d进栈\n");Push(ls,'d');

   printf("%s\n",(StackEmpty(ls)==1?"":"不空"));

   GetTop(ls,e);                                /*取栈顶元素*/

   printf("栈顶元素:%c\n",e);

   printf("出栈次序:");

   while (!StackEmpty(ls))                  /*栈不空时循环*/

   {   

     Pop(ls,e);                                 /*出栈*/

     printf("%c ",e);

   }

   printf("\n");

}

上述程序执行结果与顺序栈对应主程序的执行结果相同。

【例3-3假设以IO分别表示进栈和出栈操作,栈的初态和终态均为空,进栈和出栈的操作序列可表示为仅由IO组成的序列。

1)下面所示的序列中哪些是合法的?

AIOIIOIOO  BIOOIOIIO  CIIIOIOIO  DIIIOOIOO

2)通过对(1)的分析,写出一个算法判定所给的操作序列是否合法。若合法则返回1;否则返回0(假设被判定的操作序列已存入一维数组中)。

解:

1AD均合法,而BC不合法。因为在B中,先进栈一次,立即出栈两次,这会造成栈下溢。在C中共进栈5次,出栈3次,栈的终态不为空。

2)本例用一个链栈来判断操作序列是否合法,其中A为存放操作序列的字符数组,n为该数组的元素个数(这里的ElemType类型设置为char)。

int Judge(char A[ ],int n)

{ 

   int i;

   ElemType x; 

   LinkStack *ls;

   InitStack(ls);                           /*初始化*/

   for (i=0;i<n;i++)

{      

      if(A[i]=='I')                           /*进栈*/

         Push(ls,A[i]);

      else if (A[i]=='O')                    /*出栈*/

         Pop(ls,x);

      else return 0;                          /*其他值无效退出*/

   }

   return(ls->next==NULL);                   /*栈为空时返回1;否则返回0*/

}