数据结构和算法学习第2天:栈的相关知识

时间:2021-11-02 10:22:08

数据结构和算法学习第2天:栈的相关知识

通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表            栈            队列

Insert(L, i, x)   Insert(S, n+1, x)     Insert(Q, n+1, x)

1≤i≤n+1

Delete(L, i)     Delete(S, n)        Delete(Q,1)

1≤i≤n

栈是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端称为栈顶,相应地,表头端称为栈底。不含元素的空表称为空栈。   

假设栈S=(a1,a2, …,an),则an 端为栈顶,a1 端为栈底。

根据栈的存储结构的不同分为顺序栈和链栈

以下函数的实现均以顺序栈为例

数据结构和算法学习第2天:栈的相关知识数据结构和算法学习第2天:栈的相关知识

算法1:栈的数据结构

#define STACK_INIT_SIZE    100;

#define STACKINCREMENT   10; 

typedef struct {

SElemType *base;   

SElemType *top; 

int stacksize;   

} SqStack;

数据结构和算法学习第2天:栈的相关知识

算法2:InitStack(&S)操作结果:构造一个空栈 S。         

Status InitStack (SqStack &S)

{S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if (!S.base) exit (OVERFLOW);

S.top = S.base; //栈空的条件

S.stacksize = STACK_INIT_SIZE;

return OK;}

栈空的条件为: S.top ==S.base

数据结构和算法学习第2天:栈的相关知识

算法3:得到栈顶元素

Status GetTop (SqStack S, SElemType &e)

 { // 若栈不空,用e返回其值,并返回OK

   // 否则返回ERROR

if (S.top == S.base) return ERROR;

e = *(S.top1);

return OK;

数据结构和算法学习第2天:栈的相关知识

算法4:入栈           

Status Push (SqStack &S, SElemType e)

{if (S.top - S.base >= S.stacksize) {//栈满,追加存储空间

S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT)* sizeof (ElemType));

if (!S.base) exit (OVERFLOW); //存储分配失败

S.top = S.base + S.stacksize;

S.stacksize += STACKINCREMENT;

}   

*S.top++ = e;    return OK;

}

数据结构和算法学习第2天:栈的相关知识

算法5:出栈

Status Pop (SqStack &S, SElemType &e) // 若栈不空,则删除S的栈顶元素,

     // 用e返回其值,并返回OK;

     // 否则返回ERROR

    if (S.top == S.base) returnERROR;

    e = *--S.top;

return OK;

 数据结构和算法学习第2天:栈的相关知识

 

栈的应用问题:

例一、   数制转换

void conversion (){

InitStack(S);

scanf("%d",N);

while (N) {

Push(S, N % 8);

N = N/8;

}

while(!StackEmpty(S)) {

Pop(S,e);

printf ("%d", e );

}

} // conversion

数据结构和算法学习第2天:栈的相关知识

数据结构和算法学习第2天:栈的相关知识数据结构和算法学习第2天:栈的相关知识

例二:括号匹配的检验

算法的设计思想:

1)凡出现左括弧,则进栈;

2)凡出现右括弧,首先检查栈是否空

   若栈空,则表明该“右括弧”多余,

   否则和栈顶元素比较,

   若相匹配,则“左括弧出栈” ,

   否则表明不匹配

3)表达式检验结束时,

   若栈空,则表明表达式中匹配正确,

   否则表明“左括弧”有余。


Status matching(string& exp) {

  int state = 1;  i=0;

  while (i<=Length(exp)&& state) {

     switch of exp[i] {

       case 左括弧:{Push(S,exp[i]); i++; break;}

       case 右括弧: {

      if(NOTStackEmpty(S)&&GetTop(S)=左括弧)

            {Pop(S,e); i++;}

          else {state = 0;}

          break;  } }

  if(StackEmpty(S)&&state) return OK; }

数据结构和算法学习第2天:栈的相关知识

数据结构和算法学习第2天:栈的相关知识

例三:行编辑程序问题

每接受一个字符即存入存储器并不恰当!

在用户输入一行的过程中,允许用户输入出差错,并在发现有误时可以及时更正。

合理的作法是:

设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区,并假设#”为退格符,“@”为退行符

while (ch != EOF){ //EOF为全文结束符

while (ch != EOF&& ch != '\n') {

      switch (ch) {

       case '#' : Pop(S, c); break;

       case '@': ClearStack(S); break;// 重置S为空栈

       default : Push(S, ch);  break; 

      }

      ch = getchar();  // 从终端接收下一个字符    }

将从栈底到栈顶的字符传送至调用过程的数据区;

ClearStack(S);      // 重置S为空栈

if (ch !=EOF)  ch = getchar();}

 数据结构和算法学习第2天:栈的相关知识