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 = https://www.cnblogs.com/houchaoqun/p/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 - * +；

行編輯程式

在堆疊的功能下，實作用戶在終端輸入出現差錯時，及時更正；

堆疊與遞回的實作

……

標籤：其他

上一篇：程式員不得不了解的計算機進制轉換

下一篇：返回列表