栈和队列--栈

                                    栈

---

从组成元素的逻辑关系来看，栈和队列都属于线性结构。栈和队列与线性表的不同之处在于它们的相关运算具有一些特殊性。更准确的说，一般线性表上的插入，删除运算不受限制，而栈和队列上的插入，删除运算均受某种特殊限制，因此栈和队列也称为操作受限的线性表。

1.栈的定义

栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。
栈顶的当前位置是动态的，栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。
当栈中没有数据元素时，称为空栈。
栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。

　　栈的主要特点是“后进先出”，即后进栈的元素先出栈。栈也称为后进先出表。
例：设有4个元素a、b、c、d进栈，给出它们所有可能的出栈次序。

解：所有可能的出栈次序如下:

    abcd  abdc  acbd  acdb
    adcb  bacd  badc  bcad
    bcda  bdca  cbad  cbda
    cdba  dcba

2.栈的顺序存储结构

　　①.假设栈的元素个数最大不超过正整数MaxSize，所有的元素都具有同一数据类型ElemType，则可用下列方式来定义栈类型SqStack:

typedef struct 
{  ElemType data[MaxSize]； 
   int top；     //栈顶指针
} SqStack；

②.顺序栈：利用顺序存储方式实现的栈称为顺序栈

顺序栈4要素：

  栈空条件：top=-1
  栈满条件：top=MaxSize-1
  进栈e操作：top++; 将e放在top处
  退栈操作：从top处取出元素e; top--;

3.在顺序栈中实现栈的基本运算算法。

（1）初始化栈initStack(&s)
建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:

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

（2）销毁栈ClearStack(&s)
释放栈s占用的存储空间。对应算法如下:

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

（3）判断栈是否为空StackEmpty(s)
栈S为空的条件是s->top==-1。对应算法如下:

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

（4）进栈Push(&s,e)
在栈不满的条件下，先将栈指针增1，然后在该位置上插入元素e。对应算法如下:

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

（5）出栈Pop(&s,&e)
在栈不为空的条件下，先将栈顶元素赋给e，然后将栈指针减1。对应算法如下:

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

（6）取栈顶元素GetTop(s)
在栈不为空的条件下，将栈顶元素赋给e。对应算法如下:

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

例：编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。
　　解：对于字符串str，先将其所有元素进栈。然后从头开始扫描str，并出栈元素，将两者进行比较，若不相同则返回false。当str扫描完毕仍没有返回时返回true。实际上，从头开始扫描str是从左向右读，出栈序列是从右向左读，两者相等说明该串是对称串。

bool symmetry(ElemType str[])
{  int i;  ElemType e;
   SqStack *st;
   InitStack(st);           //初始化栈
   for (i=0;str[i]!='\0';i++)   //将串所有元素进栈
    Push(st,str[i]);        //元素进栈
   for (i=0;str[i]!='\0';i++)
   {    Pop(st,e);        //退栈元素e
    if (str[i]!=e)    //若e与当前串元素不同则不是对称串
    {  DestroyStack(st);//销毁栈
       return false;
    }
   }
   DestroyStack(st);      //销毁栈
   return true;
}

例：编写一个算法判断输入的表达式中括号是否配对（假设只含有左、右圆括号）。
解:该算法在表达式括号配对时返回true，否则返回false。设置一个顺序栈St，扫描表达式exp，遇到左括号时进栈；遇到右括号时：若栈顶为左括号，则出栈，否则返回false。当表达式扫描完毕，栈为空时返回true；否则返回false。

bool Match(char exp[],int n)
{  int i=0; char e;  bool match=true; SqStack *st;
   InitStack(st);             //初始化栈
   while (i<n && match)       //扫描exp中所有字符
   {    if ( exp[i]=='(‘ )  //当前字符为左括号,将其进栈
       Push(st,exp[i]);
    else if (exp[i]==')')   //当前字符为右括号
      {if (GetTop(st,e)==true)
        {f (e!='(')    //栈顶元素不为'('时表示不匹配
           match=false;
        else
           Pop(st,e);    //将栈顶元素出栈
        }
       else  match=false;  //无法取栈顶元素时表示不匹配
      }
    i++;                 //继续处理其他字符
   }
   if (!StackEmpty(st))      //栈不空时表示不匹配
    match=false;
   DestroyStack(st);         //销毁栈
   return match;
}