第 3 章　堆疊與佇列

3.1　堆疊抽象資料型態

回想一下，$A = a_0, a_1, \ldots, a_{n-1}$ 為一個有 $n \ge 0$ 元素的有序串列。$a_i$ 稱為分子或元素，它自某些集合中取出。虛串列或空串列以 () 表示，具有 $n=0$ 個元素。

堆疊運算的限制暗示了如果我們依序將元素 A、B、C、D、E 加入堆疊中，則當我們要從堆疊刪除資料時，E 為第一個元素。因為最後插入堆疊的元素為第一個被刪除的元素，所以堆疊又稱為後進先出（Last-In-First-Out，LIFO）串列。

結構 3.1 與陣列實作

structure Stack is
  objects: a finite ordered list with zero or more elements.
  functions:
    for all stack in Stack, item in element,
    max_stack_size in positive integer

    Stack CreateS(max_stack_size) ::=
        create an empty stack whose maximum size is max_stack_size
    Boolean IsFull(stack, max_stack_size) ::=
        if (number of elements in stack == max_stack_size)
        return TRUE
        else return FALSE
    Stack Add(stack, item) ::=
        if (IsFull(stack)) stack_full
        else insert item into top of stack and return
    Boolean IsEmpty(stack) ::=
        if (stack == CreateS(max_stack_size))
        return TRUE
        else return FALSE
    Element Delete(stack) ::=
        if (IsEmpty(stack)) return
        else remove and return the item on the top of the stack.

end Stack

結構 3.1：抽象資料型態 stack

實作這個 ADT 最簡單的方法是使用一維陣列 stack[MAX_STACK_SIZE]。堆疊第一個（或底端的）元素儲存於 stack[0]，第二個在 stack[1]，而第 $i$ 個在 stack[i-1]。與此陣列相關的變數為 top，它指向堆疊頂端的元素。起初，top 設定為 −1，表示一個空的堆疊。

Stack CreateS(max_stack_size) ::=

     #define MAX_STACK_SIZE 100 /*maximum stack size*/
     typedef struct {
             int key;
             /* other fields */
             } element;
     element stack[MAX_STACK_SIZE];
     int top = -1;

Boolean IsEmpty(Stack) ::= top < 0;
Boolean IsFull(Stack)  ::= top >= MAX_STACK_SIZE-1;

void add(int *top, element item)
{
/* add an item to the global stack */
   if (*top >= MAX_STACK_SIZE-1) {
      stack_full();
      return;
   }
   stack[++*top] = item;
}

程式 3.1：加入元素到堆疊中

element delete(int *top)
{
/* return the top element from the stack */
   if (*top == -1)
      return stack_empty(); /* returns an error key */
   return stack[(*top)--];
}

程式 3.2：自堆疊中刪除元素

堆疊是總體變數，而且被「隱藏」，因為我們想要強調只有透過頂端指標才能存取堆疊的觀念。

3.2　佇列抽象資料型態

佇列運算上的限制暗示了如果我們依序將 A、B、C、D 插入佇列中，則 A 是第一個可以自佇列刪除的元素。因為第一個加入佇列的元素也是第一個刪除的元素，佇列又稱先進先出（First-In-First-Out，FIFO）串列。

structure Queue is
  objects: a finite ordered list with zero or more elements.
  functions:
    for all queue in Queue, item in element,
    max_queue_size in positive integer

    Queue CreateQ(max_queue_size) ::=
        create an empty queue whose maximum size is max_queue_size
    Boolean IsFullQ(queue, max_queue_size) ::=
        if (number of elements in queue == max_queue_size)
        return TRUE
        else return FALSE
    Queue AddQ(queue, item) ::=
        if (IsFullQ(queue)) queue_full
        else insert item at rear of queue and return queue
    Boolean IsEmptyQ(queue) ::=
        if (queue == CreateQ(max_queue_size))
        return TRUE
        else return FALSE
    Element DeleteQ(queue) ::=
        if (IsEmptyQ(queue)) return
        else remove and return the item at front of queue.

end Queue

結構 3.2：抽象資料型態 Queue

Queue CreateQ(max_queue_size) ::=
     #define MAX_QUEUE_SIZE 100 /*Maximum queue size*/
     typedef struct {
             int key;
             /* other fields */
             } element;
     element queue[MAX_QUEUE_SIZE];
     int rear = -1;
     int front = -1;

Boolean IsEmptyQ(queue) ::= front == rear
Boolean IsFullQ(queue)  ::= rear == MAX_QUEUE_SIZE-1

void addq(int *rear, element item)
{
/* add an item to the queue */
   if (*rear == MAX_QUEUE_SIZE-1) {
      queue_full();
      return;
   }
   queue[++*rear] = item;
}

程式 3.3：插入元素到佇列中

element deleteq(int *front, int rear)
{
/* remove element at the front of the queue */
   if (*front == rear)
      return queue_empty(); /*return an error key */
   return queue[++*front];
}

程式 3.4：自佇列中刪除元素

環形佇列 (circular queue)

如果將陣列 queue[MAX_QUEUE_SIZE] 看成一個環狀，則可以得到一種更有效率的佇列表示法。在這種表示法中：

要為環形佇列製作 addq 和 deleteq 有一些困難，因為我們必須保證它以環形轉動。這可以用模數運算來達成。於 addq 中，後端索引的環形轉動發生在指令 *rear = (*rear+1) % MAX_QUEUE_SIZE;

void addq(int front, int *rear, element item)
{
/* add an item to the queue */
   *rear = (*rear+1) % MAX_QUEUE_SIZE;
   if (front == *rear) {
     queue_full(rear); /* reset rear and print error*/
     return;
   }
   queue[*rear] = item;
}

程式 3.5：插入元素到環形佇列 —— 注意先轉動後端索引，再放入元素

element deleteq(int *front, int rear)
{
   element item;
   /* remove front element from the queue and put it
   in item */
     if (*front == rear)
       return queue_empty(); /* queue_empty returns an
       error key */
     *front = (*front+1) % MAX_QUEUE_SIZE;
     return queue[*front];
}

程式 3.6：自環形佇列中刪除元素 —— 同樣先轉動 front，再刪除元素

3.3　迷宮問題

長久以來，迷宮問題一直是個令人感到有興趣的題目。實驗心理學者訓練老鼠在迷宮中找尋食物，許多偵探小說家使用英國式的花園迷宮來安排謀殺案。我們對迷宮也有興趣，因為它可供很好的一種堆疊應用。

三個表示法的決定

typedef struct {
        short int vert;
        short int horiz;
        } offsets;
offsets move[8]; /*array of moves for each direction*/

如果目前位在 maze[row][col] 而想要找到下一個走到的位置 maze[next_row][next_col]，我們可設定：

next_row = row + move[dir].vert;
next_col = col + move[dir].horiz;

圖 3.10：移動的表格 —— 這張表把「八個方向」從一串 if 變成一次陣列查表。

回溯演算法

initialize a stack to the maze's entrance coordinates and
direction to north;
while (stack is not empty) {
  /* move to position at top of stack */
  <row,col,dir> = delete from top of stack;
  while (there are more moves from current position) {
     <next_row, next_col> = coordinates of next move;
     dir = direction of move;
     if ((next_row == EXIT_ROW) && (next_col == EXIT_COL))
       success;
     if (maze[next_row][next_col] == 0 &&
                mark[next_row][next_col] == 0) {
     /* legal move and haven't been there */
       mark[next_row][next_col] = 1;
       /* save current position and direction */
       add <row,col,dir> to the top of the stack;
       row = next_row;
       col = next_col;
       dir = north;
     }
  }
}
printf("No path found\n");

程式 3.7：迷宮演算法初版

void path(void)
{
/* output a path through the maze if such a path exists */
  int i, row, col, next_row, next_col, dir, found = FALSE;
  element position;
  mark[1][1] = 1; top = 0;
  stack[0].row = 1;  stack[0].col = 1;  stack[0].dir = 1;
  while (top > -1 && !found) {
    position = delete(&top);
    row = position.row;  col = position.col;
    dir = position.dir;
    while (dir <  8 && !found) {
      /* move in direction dir */
      next_row = row + move[dir].vert;
      next_col = col + move[dir].horiz;
      if (next_row == EXIT_ROW && next_col == EXIT_COL)
        found = TRUE;
      else if ( !maze[next_row][next_col] &&
      ! mark[next_row][next_col]) {
        mark[next_row][next_col] = 1;
        position.row = row; position.col = col;
        position.dir = ++dir;
        add(&top, position);
        row = next_row; col = next_col; dir = 0;
      }
      else ++dir;
    }
  }
  if (found) {
    printf("The path is:\n");
    printf("row  col\n");
    for (i = 0; i <= top; i++)
      printf("%2d%5d",stack[i].row, stack[i].col);
    printf("%2d%5d\n",row,col);
    printf("%2d%5d\n",EXIT_ROW,EXIT_COL);
  }
  else printf("The maze does not have a path\n");
}

程式 3.8：迷宮搜尋函數

3.4　運算式計算

3.4.1　簡介

運算式的表示法與計算法在計算機科學上是極有興趣的。對程式設計者而言，當寫下複雜的運算式，如：

或者複雜的指派指令，如：

C 語言的優先權等級

在任何程式語言中，都有一種用來決定計算運算符號先後順序的優先權等級。運算符號由高優先權到低優先權排列，具有相同優先權的符號放在同一個方格中。

圖 3.12：C 語言優先權等級（優先順序由 Harbison 和 Steele 提供）

3.4.2　計算後序運算式

圖 3.13：中序和後序表示法

圖 3.14：後序運算式計算 —— 輸入為九個字元的字串 62/3-42*+

#define MAX_STACK_SIZE 100 /*maximum stack size*/
#define MAX_EXPR_SIZE 100 /*max size of expression*/
typedef enum {lparen, rparen, plus, minus, times, divide,
                        mod, eos, operand} precedence;
int stack[MAX_STACK_SIZE]; /* global stack */
char expr[MAX_EXPR_SIZE]; /* input string */

為了簡化工作，假設運算式中僅包含二元運算符號 + - * / %，且運算元均為一位整數。

int eval(void)
{
/* evaluate a postfix expression, expr, maintained as a
global variable. '\0' is the the end of the expression.
The stack and top of the stack are global variables.
get_token is used to return the tokentype and
the character symbol. Operands are assumed to be single
character digits */
   precedence token;
   char symbol;
   int op1, op2;
   int n = 0; /* counter for the expression string */
   int top = -1;
   token = get_token(&symbol, &n);
   while (token != eos) {
     if (token == operand)
       add(&top, symbol-'0'); /* stack insert */
     else {
       /* remove two operands, perform operation, and
       return result to the stack */
       op2 = delete(&top); /*stack delete */
       op1 = delete(&top);
       switch(token) {
          case plus: add(&top,op1+op2);
                      break;
          case minus: add(&top, op1-op2);
                      break;
          case times: add(&top, op1*op2);
                      break;
          case divide: add(&top,op1/op2);
                       break;
          case mod: add(&top, op1%op2);
       }
     }
     token = get_token(&symbol, &n);
   }
   return delete(&top); /* return result */
}

程式 3.9：用以計算後序運算式的函數

precedence get_token(char *symbol, int *n)
{
/* get the next token, symbol is the character
representation, which is returned, the token is
represented by its enumerated value, which
is returned in the function name */
   *symbol = expr[(*n)++];
   switch (*symbol) {
      case '(' : return lparen;
      case ')' : return rparen;
      case '+' : return plus;
      case '-' : return minus;
      case '/' : return divide;
      case '*' : return times;
      case '%' : return mod;
      case ' ' : return eos;
      default  : return operand; /* no error checking,
                         default is operand */
   }
}

程式 3.10：從輸入字串中取得一個符號的函數

3.4.3　中序轉成後序

例如，a/b-c+d*e-a*c 完全地加上括號以後變成 ((((a/b)-c)+(d*e))-(a*c))，執行步驟 2 和 3 以後得到 ab/c-de*+ac*-。

因為中序和後序運算式中的運算元是相同的，我們可以藉著由左而右掃描中序運算式來產生對等的後序運算式。在這次的掃描中，每遇到運算元就將它們傳送到輸出運算式中。但是，運算符號的輸出順序則根據它們的優先權來決定。

isp 與 icp：兩種優先權

precedence stack[MAX_STACK_SIZE];
/* isp and icp arrays -- index is value of precedence
lparen, rparen, plus, minus, times, divide, mod, eos */
static int isp[] = {0,19,12,12,13,13,13,0};
static int icp[] = {20,19,12,12,13,13,13,0};

void postfix(void)
{
/* output the postfix of the expression. The expression
string, the stack, and top are global */
   char symbol;
   precedence token;
   int n = 0;
   int top = 0;   /* place eos on stack */
   stack[0] = eos;
   for (token = get_token(&symbol, &n); token != eos;
                     token = get_token(&symbol,&n)) {
     if (token == operand)
       printf("%c",symbol);
     else if (token == rparen) {
       /* unstack tokens until left parenthesis */
       while (stack[top] != lparen)
         print_token(delete(&top));
       delete(&top);  /* discard the left parenthesis */
     }
     else {
       /* remove and print symbols whose isp is greater
       than or equal to the current token's icp */
       while(isp[stack[top]] >= icp[token])
         print_token(delete(&top));
       add(&top, token);
     }
   }
   while ( (token=delete(&top)) != eos)
     print_token(token);
   printf("\n");
}

程式 3.11：將中序運算式轉成後序運算的函數

3.5　多元堆疊與佇列

直到目前為止，我們僅討論單一堆疊或單一佇列的表示法。在這兩種情況下，我們已明白它們可獲得有效率的循序表示法。現在，我們想要討論多元堆疊之狀況。（多元佇列的表示法留待習題討論。）

#define MEMORY_SIZE 100 /* size of memory */
#define MAX_STACKS 10 /* max number of stacks plus 1 */
/* global memory declaration */
element memory[MEMORY_SIZE];
int top[MAX_STACKS];
int boundary[MAX_STACKS];
int n;  /* number of stacks entered by the user */

要將陣列分割成大約相等的段落，使用下列的程式碼：

top[0] = boundary[0] = -1;
for (i = 1; i < n;i++)
   top[i] = boundary[i] = (MEMORY_SIZE/n)*i;
boundary[n] = MEMORY_SIZE-1;

void add(int i, element item)
{
/* add an item to the ith stack */
   if (top[i] == boundary[i+1])
      stack_full(i);
   memory[++top[i]] = item;
}

程式 3.12：將一個 item 加入堆疊 stack_no 中

element delete(int i)
{
/* remove top element from the ith stack */
   if (top[i] == boundary[i])
      return stack_empty(i);
   return memory[top[i]--];
}

程式 3.13：從堆疊 stack_no 中刪除一個 item

stack_full 的三步策略

因此，我們建立一個錯誤修復函數 stack_full，來決定在記憶體中是否仍有閒置空間。如果仍有空間可取用，應將堆疊移位以配置空間給滿載的堆疊。只要在陣列 memory 中仍有閒置空間，我們即可保證 stack_full 可加入元素，如果：

3.6　精選參考文獻

3.7　綜合習題

本章重點回顧