栈的定义以及栈的顺序结构(C语言实现)

之前学完了线性表,现在就要开始进行全新的一章了,我们就要开始学习栈了。那么啥叫栈嘞。其实栈也是一种线性表,不过是一种限定性线性表,是将线性表的插入和删除运算限制为仅在表的一端进行。那么这要这么理解呢。首先,我们要熟悉两个概念。栈顶和栈底。

栈顶:通常将表中允许进行插入、删除操作的一端称为栈顶 (Top),因此栈顶的当前位 置是动态变化的,它由一个称为栈顶指针的位置指示器指示。
栈底:同时表的另一端被称为栈底 (Bottom)。当栈中没有元素时称为空栈。栈的插入 操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。

根据上述定义,每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶,而每次出栈 的总是当前栈中“最新”的元素,即最后进栈的元素。


既然是线性表,那么和线性表一样,栈也会有它的基本操作。那么就来总结一下。
基本操作:
(1) InitStack(S)
操作前提:S 为未初始化的栈。
操作结果:将 S 初始化为空栈。

(2) ClearStack(S)
操作前提:栈 S 已经存在。
操作结果:将栈 S 置成空栈。

(3) IsEmpty(S)
操作前提:栈 S 已经存在。
操作结果:判栈空函数,若 S 为空栈则函数值为“TRUE”,否则为“FALSE”。

(4) IsFull(S)
操作前提:栈 S 已 经存在。
操作结果:判栈满函数,若 S 栈已满,则函数值为“TRUE”,否则为“FALSE”。

(5) Push(S,x)
操作前提:栈 S 已经存在。
操作结果:在 S 的顶部插入(亦称压入)元素 x;若 S 栈未满,将 x 插入栈顶 位置,若栈已满,则返回 FALSE,表示操作失败,否则返回 TRUE。

(6) Pop(S, x)
操作前提:栈 S 已经存在。
操作结果:删除(亦称弹出)栈 S 的顶部元素,并用 x 带回该值; 若栈为空,返回值为FALSE,表示操作失败,否则返回 TRUE。

(7) GetTop(S, x)
操作前提:栈 S 已经存在。
操作结果:取栈 S 的顶部元素赋给 x 所指向的单元。与 Pop(S, x)不同之处在 于 GetTop(S,x)不改变栈顶的位置。

事实上栈真的和线性表一样存在顺序结构和链式结构。那么我们就先来看看顺序结构的实现。

顺序栈是用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时由于栈操作的特殊性,还必须附设一个位置指示器 top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。通常以 top=-1 表示空栈。代码定义如下:

#define Stack_Size 50 typedef struct 
{ 
   StackElementType  elem[Stack_Size];   /*用来存放栈中元素的一维数组*/ 
   int  top;  /*用来存放栈顶元素的下标,top 为-1 表示空栈*/ 
}SeqStack; 

那么我们来看看基本操作。

//初始化 
void  InitStack(SeqStack *S) 
{/*构造一个空栈 S*/ 
  S->top= -1; 
} 

//进栈 
int Push(SeqStack * S, StackElementType x) 
{ 
  if(S->top== Stack_Size-1)  
      return(FALSE);  /*栈已满*/ 
  S->top++; 
  S->elem[S->top]=x; 
  return(TRUE); 
} 

//出栈 
int Pop(SeqStack * S, StackElementType *x) 
{  /* 将栈 S 的栈顶元素弹出,放到 x 所指的存储空间中 */ 
       if(S->top= =-1)  /*栈为空*/
           return(FALSE);           
       else 
      { 
             *x= S->elem[S->top]; 
              S->top--;/* 修改栈顶指针 */   
              return(TRUE); 
      } 
} 

//取栈顶元素。 
int GetTop(SeqStack *S, StackElementType *x) 
{  /* 将栈 S 的栈顶元素弹出,放到 x 所指的存储空间中,但栈顶指针保持不变 */       if(S->top==-1)  /*栈为空*/ 
         return(FALSE); 
    else 
    { 
          *x = S->elem[S->top];  
          return(TRUE); 
    }      
} 

关于顺序栈的操作,我觉得吧,重点在于对于栈点指示器的位置,也就是top的值。在放入和取出时都需要考虑是否为空或是满。其次不需要关注数组中是否有数据存在,因为整个栈的操作重点在于top指针,不在内的数组空间就视为不在栈内。

事实上,由于栈底不变的特殊性,我们可以有一个比较奇怪的用法,那就是共享栈。(什么什么??这都可以共享?)

首先为两个栈申请一个共享的一维数组空间 S[M],将两个栈的栈底分别放在一维数组的两端,分别是 0,M-1。由于两个栈顶动态变化,这样可以形成互补,使得每个栈可用的最大空间与实际使用的需求有关。由此可见,两栈共享要比两个栈分别申请 M/2 的空间利用率要高。

既然有两个栈了,那么之前的操作和定义又要不一样咯。(其实差别比较大的只有进栈和出栈啦)

//初始化操作。 
void InitStack(DqStack *S) 
{ 
         S->top[0]=-1; 
         S->top[1]=M; 
} 

//进栈操作。  
int Push(DqStack *S, StackElementType x, int i) 
{/*把数据元素 x 压入 i 号堆栈*/ 
     if(S->top[0]+1==S->top[1]) /*栈已满*/ 
          return(FALSE);      
     switch(i) 
     { 
         case 0: 
                S->top[0]++; 
                 S->Stack[S->top[0]]=x; 
               break;      
        case 1:           
               S->top[1]--; 
                 S->Stack[S->top[1]]=x; 
               break; 
         default:  /*参数错误*/ 
               return(FALSE) 
     } 
         return(TRUE); 
} 

//出栈操作。 
int Pop(DqStack *S, StackElementType *x, int i) 
{/* 从 i 号堆栈中弹出栈顶元素并送到 x 中 */ 
     switch(i) 
     { 
         case 0: 
               if(S->top[0]==-1)  
                   return(FALSE); 
                  *x=S->Stack[S->top[0]];                
                S->top[0]--;                
                break;           
        case 1: 
                if(S->top[1]==M) 
                   return(FALSE); 
                   *x=S->Stack[S->top[1]];             
                 S->top[1]++;           
                  break;           
        default:  
                   return(FALSE); 
         } 
         return(TRUE); 
} 

其实和之前的顺序结构差不多,操作的重点依旧在于对于top指针的理解与判断。