1、栈:仅在表尾进行插入和删除操作的线性表。后进先出LIFO。

1)表尾端(允许插入和删除的一端)为栈顶,表头端(不允许插入和删除的一端)为栈底。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

2)入栈:插入元素的操作。出栈:删除栈顶元素

3)栈的应用:数值转化、括号匹配检验、行编辑程序、迷宫求解、表达式求值

2、栈的两种存储表示方式

1)顺序栈(栈的顺序存储结构):利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。top=0表示空栈。

2)链栈(栈的链式存储结构);优点是便于多个栈共享存储空间和提高效率。

3、括号匹配检验

1)左括号,则进栈。

2)右括号,若栈为空,则右括号多。

3)右括号,与栈顶元素比较,若相等则左括号出栈,若不相等则不匹配。

4)表达式检验结束时,若栈空则匹配成功,否则左括号多。

4、栈的基本操作

InitStack(&S):构造空栈

DestroyStack(&S):销毁栈

ClearStack(&S):清空栈

StackEmpty(S):判断栈是否为空,若为空则返回true,否返回false

StackLength(S):返回栈的长度

GetTop(S,&e):用e返回栈的栈顶元素

Push(&S,e):插入e为新栈顶

Pop(&S,&e):删除栈顶元素,并用e返回其值。

5、共享栈:利用栈底位置相对不变性的特性,使得两个顺序栈共享一个一维数据空间,将两个栈底设置在共享空间的两端。

1)top0=-1时0号栈为空,top1=maxsize时1号栈为空,仅当两个栈顶指针相邻(top1-top0=1)时,栈满。

2)当0号栈进栈时top0先加1再赋值,1号栈进栈时top1先减1在赋值。

6、栈的顺序存储类型描述

#define maxsize 50
typedef struct {
 int data[maxsize];
 int top;//栈顶指针,初始时设置S.top=-1,栈顶元素为:S.data[S.top],栈空条件:S.top==-1栈满条件:S.top==maxsize-1栈长:S.top+1
}Sqstack; 1)初始化栈
void initstack(Sqstack &S)
{
 S.top = -1;
}
2)判断栈空
bool stackempty(Sqstack S)
{
 if (S.top == -1)
 {
  return true;
 }
 else
 {
  return false;
 }
}
3)进栈
bool push(Sqstack &S, int e)
{
 if (S.top == maxsize - 1)
 {
  return false;
 }
 S.data[++S.top] = e;
 return true;
}
5)出栈
bool pop(Sqstack &S, int &e)
{
 if (S.top == -1)
 {
  return false;
 }
 e = S.data[S.top--];
 return true;
}
6)读栈顶元素
bool GetTop(Sqstack S, int &e)
{
 if (S.top == -1)
 {
  return false;
 }
 e = S.data[S.top--];
 return true;
} 7、栈的链式存储结构类型描述
typedef struct Linkstack {
 int data;
 struct Linkstack *next;
}*Listack; 8、一些基本问题的解决 1)以IO分别表示入栈和出栈操作,栈的初态和终态都为空,可以操作的序列称为合法序列,判断序列是否合法。
int judge(cha A[])
{
 int i = j = k = 0;
 while (A[i]!='\0')
 {
  switch (A[i])
  {
  case 'I':j++;
   break;
  case 'O':k++;
   if (k > j)
   {
    printf("序列非法\n");
    exit(0);
   }
  }
  i++;
 }
 if (j != k)
 {
  printf("序列非法");
  return false;
 }
 else
 {
  printf("序列合法");
  return true;
 }
}
2)设栈S1,S2都擦用顺序栈,并共享一个存储区[0,...,maxsize-1],采用栈顶相向、迎面增长的存储方式,出栈和入栈的实现。i为栈号,i=0表示左边的栈s1,i=1表示右边的栈s2,e为入栈元素。
typedef struct {
 int stack[maxsize];
 int top[2];
}stk;
stk s;
//入栈
int push1(int i, int e)
{
 if (i < 0 || i>1)
 {
  printf("栈号输入错误");
  exit(0);
 }
 if (s.top[1] - s.top[0] == 1)
 {
  printf("栈以满\n");
  return 0;
 }
 switch (i)
 {
 case 0:s.stack[++s.top[0]] = e;
  return 1;
  break;
 case 1:s.stack[--s.top[1]] = e;
  return 1;
 }
}
//出栈
int pop1(int i)
{
 if (i < 0 || i>1)
 {
  printf("栈号输入错误\N");
  exit(0);
 }
 switch (i)
 {
 case 0:
  if (s.top[0] == -1)
  {
   printf("栈空\n");
   return -1;
  }
  else
  {
   return s.stack[s.top[0]--];
  }
 case 1:
  if (s.top[1] == maxsize)
  {
   printf("栈空\n");
   return -1;
  }
  else
  {
   return s.stack[s.top[1]++];
  }
 }
}
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄