栈及其基本运算

1、栈的定义
    　堆栈（Stack）可以看成是一种“特殊的”线性表，这种线性表上的插入和删除运算限定在表的某一端进行的。
　　(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
　　(2)当表中没有元素时称为空栈。
　　(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
    　栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

2、栈的基本运算
（1）InitStack（S）
    　初始化操作，设定一个空栈S。
（2）EmptyStack（S）
    　判空栈操作，若S为空栈，则返回TRUE，否则返回FALSE。
（3）FullStack（S）
    　判栈满。若S为满栈，则返回TRUE，否则返回FALSE。
注意：
　    该运算只适用于栈的顺序存储结构。
（4）Push（S，e）
    　进栈。若栈S不满，在S栈顶插入一个元素e，栈顶位置由top指针指出。
（5）Pop（S）
    　退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。
（6）GetTop（S）
    　取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
（7）ClearStack（S）
    　置栈空操作，已知S为栈，不论操作之前的栈是否为空栈，本操作的结果都是将S置为空栈。
（8）CurrentStack（S）
    　求当前栈中元素的个数。
（9）DestroyStack（S）
    　销毁S栈。

顺序栈


   与线性表类似栈也有两种存储结构，即顺序存储结构和链表存储结构。栈的顺序存储结构亦称为顺序栈,它是运算受限的顺序表。
1、 顺序栈的类型定义
  const int MAXSIZE=100; //假定预分配的栈空间最多为100个元素
  typedef int ElemType;//假定栈元素的数据类型为整型
  struct SqStack{ ElemType elem[MAXSIZE]; //一维数组
      int top;//指针top指向栈顶元素的当前位置
     }
  注意：
　    ①SqStack就是栈的顺序存储结构的类型标识符。
    　②顺序栈中元素用向量存放
    　③栈底位置是固定不变的，可设置在向量两端的任意一个端点
    　④栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置

 

2、 顺序栈的基本操作
  前提条件：
    　设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S.elem[0]是栈底元素。
（1） 进栈操作
    　进栈时，需要将top加1
  注意：
　   ①top==MAXSIZE-1表示栈满
　   ②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。
      上溢是一种出错状态，应设法避免。
【算法3.1】
void SqStack::push( ElemType e)
{ if(top= =MAXSIZE-1)
{cout<<"栈满溢出"<exit(1);
}
else {top++;
elem[top]=e;
}
}

（2） 退栈操作
    　退栈时，需将top减1
  注意：
　    ①top<0表示空栈
    　②"下溢"现象——当栈空时，做退栈运算产生的溢出现象。
      下溢是正常现象，常用作程序控制转移的条件。
【算法3.2】
ElemType SqStack::pop()
{ElemType x;
if(top= =0)
{ cout<< " 栈为空，不能出栈操作"<else { x=elem[top];
top--;
return x;
}
}

 

链栈

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

1、链栈的类型定义
　　栈可以用单链表做为存储结构，链表中数据元素结点描述如下：
typedef int ElemType;
struct Lsnode { ElemType data;
struct Lsnode *next;
};

【算法3.3】
LsStack:: LsStack () //构造函数,建立一个空栈
{ top=NULL;
}
void LsStack::Display() //输出显示单链表栈内容
{ Lsnode *p; p=top;
while(p!=NULL)
{ cout<<” ”<data;
p=p->next;
}
cout<<"结束！outend!" ;
}
上述算法可以输出单链表栈。首先，判别是否栈空。如果不是空栈，即将线性表的数据元素一一输出。在这个算法中，我们又复习到单链表的相关内容。可见，栈是一种特殊的线性结构，它与前一章中的线性表数据结构有密切的联系。


2、链栈的基本运算

（1） 入栈
【算法3.4】 void LsStack::Push(ElemType x)
{ Lsnode *p;
p=new Lsnode; // 申请一个结点空间
p->data=x; p->next=top; top=p;
} //进栈Push
首先，建立一新结点。然后，把这个结点插到栈顶，并且令栈顶指针top 指向它。

（2） 出栈
【算法3.5】
ElemType LsStack::Pop()
{ Lsnode *p; ElemType x;
if(top!=NULL) { p=top; top=top->next;
x=p->data; free(p);
return(x);
}
else {cout<<"Stack null! \n";exit(1); }
}/*出栈Pop*/
　　由上述算法可看出，栈在链表存储结构条件下进栈一个元素时一般不考虑栈满上溢出问题，而出栈时必须考虑栈空问题。