数据结构之栈

Stack

类型定义

栈是限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(last in first out)的线性表(LIFO结构),表尾称为栈顶,表头称为栈底,不含元素则称为空栈;
抽象数据类型:

InitStack(&S)               //构造空栈S
DestoryStack(&S)            //销毁栈S
ClearStack(&S)              //将S清为空栈
StackEmpty(S)               //若S为空栈返回TRUE,否则FALSE
StackLength(S)              //返回栈S的元素个数,即栈的长度
GetTop(S, &e)               //用e返回S的栈顶元素
Push(&S, e)                 //插入元素e为新的栈顶元素
Pop(&S, &e)                 //删除S的栈顶元素,并用e返回其值
StackTraverse(S, visit())   //从栈顶到栈底依次对S的每个元素调用visit(),visit()失败则操作失败

顺序存储结构

存储表示

其中base为NULL时表示栈结构不存在,top==base可作为栈空的标记;

#define STACK_INIF_SIZE 100  //存储空间初始分配量
#define STACKINCREMENT 10    //存储空间分配增量
#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

typedef struct
{
  SElemType *base;            //栈不存在为NULL
  SElemType *top;
  int stacksize;
}SqStack;

基本实现

InitStack

Status InitStack(SqStack *S)
{ // 构造空栈S
  S->base = (SElemType *)malloc(STACK_INIF_SIZE * sizeof(SElemType));
  if (!S->base)
    return ERROR;
  S->top = S->base;
  S->stacksize = STACK_INIF_SIZE;
  return OK;
}

GetTop

Status GetTop(SqStack S, SElemType *e)
{ // 若栈不空,用e返回S的栈顶元素
  if (S.top == S.base)
    return ERROR;
  (*e) = *(S.top - 1);
  return OK;
}

Push

Status Push(SqStack *S, SElemType e)
{ // 插入元素e为栈顶元素
  if (S->top - S->base >= S->stacksize)
  { // 栈满,追加储存空间
    S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
    if (!S->base)
      return ERROR;
    S->top = S->base + S->stacksize;
    S->stacksize += STACKINCREMENT;
  }
  *S->top++ = e;
  return OK;
}

Pop

Status Pop(SqStack *S, SElemType *e)
{ // 若栈不空,则删除S的栈顶元素,并用e返回其值
  if (S->top == S->base)
    return ERROR;
  (*e) = *--S->top;
  return OK;
}

测试

int main()
{
  SqStack *S = (SqStack *)malloc(sizeof(SqStack));
  InitStack(S);
  Push(S, 1);
  printf("%d %d\n", *S->base, *(S->top - 1));
  Push(S, 2);
  printf("%d %d\n", *S->base, *(S->top - 1));
  int *e = (int *)malloc(sizeof(int));
  Pop(S, e);
  printf("%d %d\n", *S->base, *(S->top - 1));
  printf("%d", *e);
  return 0;
}

链式存储结构

存储表示

链式存储便于多个栈共享存储空间以及提高其效率,且不存在栈满的情况,通常采用单链表实现,并规定所有操作都是在表头进行;这里没有头结点,直接指向栈顶元素,对于空栈即top == base = NULL;

//节点
typedef struct StackNode
{ 
  ElemType data;
  struct StackNode *next;
}StackNode, *LinkStackPrt;
//链栈
typedef struct LinkStack
{
  LinkStackPrt top;
  int count;
}LinkStack;

基本实现

Push

Status Push(LinkStack *S, ElemType e)
{ //插入新栈顶元素e
  //创建新节点
  LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));
  p->data = e;
  p->next = S->top;
  S->top = p;
  S->count++;
  return OK;
}

Pop

Status Pop(LinkStack *S, ElemType *e)
{
  LinkStackPrt P;
  if(StackEmpty(*S))
    return ERROR;
  *e = S->top->data;
  p = S->top;
  S->top = S->top->next;
  free(p);
  S->count--;
  return OK;
}

栈的应用

表达式求值

波兰式(前缀表达式)

从左向右读入表达式,如果一个操作符后面跟着两个操作数时,将计算结果作为操作数替换这个操作符和两个操作数,直至计算完成;
such as 2 + 3 * (5 - 1),其波兰式为 + 2 * 3 - 5 1;

逆波兰式(后缀表达式)

相较于波兰式,逆波兰式要更为直接,当遇到操作符时,将前面两个操作数与这个操作符进行计算,结果替换;
如上的 2 + 3 * (5 - 1)用逆波兰式表示为 2 3 5 1 - * +;
这个过程很容易用栈来实现,将2, 3, 5, 1依次压入栈中,当压入 - 时,判定为操作符,Pop 5, 1,计算结果后再压入栈中,直至压入完成,栈中元素即运算结果;

中缀表达式转化为逆波兰式

由于计算机中广泛应用后缀表达式,因此中缀表达式转为后缀表达式很有必要;
从左向右遍历,遇到数字,输出到逆波兰式中;遇到符号,判断其与栈顶符号的优先级,是右括号或者优先级低于栈顶符号,则栈顶元素依次出栈并输出到逆波兰式中,并将当符号进栈,直至输出结束

如 2 + 3 * (5 - 1)则过程如下:

  • 2,输出到表达式中,2,栈为空;
  • +,到栈中,2,+;
  • 3,输出到表达式中,2 3,+;
  • *,到栈中,2 3,+ *;
  • (,到栈中,2 3,+ * (;
  • 5,表达式,2 3 5,+ * (;
  • -,栈中,2 3 5,+ * ( -;
  • 1,表达式,2 3 5 1,+ * ( -;
  • ),栈顶元素依次出栈并输出到表达式中,即2 3 5 1 - * +;

行编辑程序

在栈的功能下,实现用户在终端输入出现差错时,及时更正;

栈与递归的实现

……

热门相关:帝少的专属:小甜心,太缠人   横行霸道   最强反套路系统   最强装逼打脸系统   惊世毒妃:轻狂大小姐