Data Structures: Stacks

一. 何謂堆疊(Stacks)?

z 後進先出(LIFO, Last In First Out)的有序數列

z 加入與刪除資料只在頂端(top)進行

z 加入資料稱為 push, 刪除資料稱為 pop

加 入 p u sh 刪 除 p o p

頂 端 to p
資 料 n

資 料 2

資 料 1

堆 疊 = ( 資 料 1 , 資 料 2 , … .., 資 料 n )

二. 以陣列製作堆疊

最簡單之方法乃利用一維陣列。下面為一陣列堆疊宣告之例子;

#define N 100 /* N 為堆疊大小 */

int stack[N]; /* 陣列 stack 當作堆疊 */

int top= -1; /* top表頂端之位置 */

p.s stack[] 及 top 必須定義為全域變數(Global Variable)

Data Structure: Stacks 1

 加 入 d

N --1 N --1

p+1 Top=p+1
d
Top = p p

1
2 2

1 1
0 0

圖 一 ： 加 入 資 料 於 陣 列 堆 疊 中

因此加入資料 d 於堆疊之 push()函數可簡述如下

1. 檢查堆疊是否已滿，若已滿則加入失敗。
2. 否則將堆疊頂端之指標 top 值加 1 ，即 top 上移一格，新資料在加入目前
top 所指之陣列元素位置中。

P o p 時 ， 原 to p 值
為 p ， 傳 回
N -1 N -1
s t a c k [ to p ] 後 ， to p
值 減 1， 則 頂 端 位
Top =p p
置 to p = p - 1
p -1 T op = p -1

1
2 2
1 1
0 0

圖二：刪除堆疊頂端資料

因此刪除堆疊頂端資料之 pop()函數可簡述如下
1. 檢查堆疊是否空了，若是空堆疊則刪除失敗。
2. 否則傳回頂端資料後將 top 值減 1 ，即 top 向下移一格。

Data Structure: Stacks 2

【範例一】寫一程式可以執行 push, pop, +, -, exit 等功能。其中
(1). push:加入資料於堆疊內
(2). pop: 傳回並刪除堆疊的頂端資料
(3). +: 取出堆疊頂端兩筆資料相加後之結果在存回堆疊內
(4). - : 取出堆疊頂端兩筆資料相減後之結果在存回堆疊內
(5). exit： 直到輸入 exit 才結束程式之執行 (見課本 p.3-12 範例 4)

/**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

#define N 100 /* 陣列堆疊宣告 */

int stack[N];
int top=-1;

/*****************************************************************
* push 函式部分 ( 加入資料於堆疊內 )
*****************************************************************/
void push(int d) /*加入資料於堆疊內*/
{
if(top == N-1) {
printf("堆疊滿了\n"); /* 注意堆疊大小 */
exit(1); /* 加入失敗，執行結束 */
} /* end if */
stack[++top]=d;
} /* end of push 函數 */

/*****************************************************************
* pop 函式部分 (刪除堆疊的頂端資料) *
*****************************************************************/
int pop()
{
if(top == -1) /* 注意空堆疊情形*/
{ printf("堆疊空了\n");
exit(1); /*刪除失敗，執行結束 */
}
Data Structure: Stacks 3
 return(stack[top--]);
}

/*****************************************************************
* 主程式部分
*****************************************************************/
void main()
{
int d, loop=1; /*loop 表迴圈控制變數*/
char input[5];

clrscr(); /*清除螢幕畫面*/
printf("*** 陣列堆疊 ***\n");
printf("可執行下列指令 : push, pop, +, -, exit\n\n");
do {
printf("==>");
scanf("%s",input);
if(strcmp(input,"push")==0) /*字串比較若相等則傳回之值*/
/* 此時作 push 動作 */
{ printf("輸入數值:");
scanf("%d",&d);
push(d);
} /* end of if(strcmp(…..)指令 */

else if(strcmp(input,"pop")==0) /* 此時作 pop 動作 */

if(top == -1)
printf("堆疊空了\n");
else
printf("%d\n",pop());
else if(strcmp(input,"+")==0)
push(pop()+pop());
else if(strcmp(input,"-")==0)
push(pop()-pop());
else if(strcmp(input,"exit")==0) /* 此時 exit */
loop=0;
else
printf("輸入錯誤!\n");
} while(loop); /* 數值 loop= 0 代表 false, 此時迴圈結束 */
printf("Bye-Bye !\n"); }

Data Structure: Stacks 4

三. 以串列指標避免全域變數使用

指標形式亦可用來描述堆疊。

優點：在同一程式中可以供多種不同的堆疊使用，且避免全域變數之使用，

缺點：函數之呼叫變得更複雜。

/*****************************************************************

* push 函式部分 (加入資料於堆疊內) *

*****************************************************************/

void push(int d, int stack[ ], int *top ) /*此處之 top 為一指標型區域變數*/

{
(*top)++; /*指標指向頂端，增量增加 1*/
stack[*top]=d; /*儲存資料 d 於堆疊頂端 */

} /* end of push 函數 */

/*****************************************************************

* pop 函式部分 (刪除堆疊的頂端資料) *

*****************************************************************/

int pop(int stack[ ], int *top)

{ int d;

d = stack[*top];
(*top)--; /*減量減少 1*/
return(d);
}

Data Structure: Stacks 5

四. 堆疊之應用一：副程式之呼叫

假設有一個主程式 X 呼叫副程式 Y,，副程式 Y 呼叫副程式 Z，電腦之作業系

統會以堆疊來儲存返回(return)之位址，當副程式 Z 做完後，會由堆疊彈回副

程式 Y 之位址，當副程式 Y 做完後，再由堆疊彈回主程式 X 之位址。

主程式 X 副程式 Y 副程式 Z

…. ….. ……
Call Y Call Z ……
Statement A Statement B …..
….. …. ….. Statement B 位址
return return Statement A 位址

五. 堆疊之應用二：代數運算式的求值計算

1. 運算式之組成

一個運算式(expression) 是由運算元(operand)、運算子(operator)及間

隔符號(delimiter) 所構成。以 C 語言為例，運算式中包含下列三種符號；

z 運算元(operand)；0,1,2,3,….etc.

z 運算子(operator) ；+,-,*,/,**,<,<=, >=, ++, !=, ++, --, =, +=, ….. etc.

z 間隔符號(delimiter) ；(,)

Data Structure: Stacks 6

 2. 運算式之計算原則

z 優先權 (precedence)；運算子運算原則。優先權 較高之運算子先執行

z 結合性 (associatively) ；優先權 相同者，則視其結合性而定

1. 結合性由左而右(left to right)，則由左而右執行。如：(+)、(-)

2. 結合性由右而左(right to left)，則由右而左執行。如：次方($)

運算子性質 運算子 優先權 結合性

次方($) *(指標) +(正號)

算術運算子 由右而左
- (負號)
高
*(乘號) /(除號) %(整數
算術運算子 ↓ 由左而右
除號)
↓
算術運算子 +(加號) -(減號) 由左而右
↓
關係運算子 < <= == != > >= 由左而右
↓
邏輯運算子 && (and) 由左而右
低
邏輯運算子 || (or) 由左而右

指定運算子 = (指定) 由右而左

圖一； 常見運算子及優先權 次序表格

Data Structure: Stacks 7

 3. 運算式之表示法

z 中序運算式(Infix Order)：<運算元 1 > <運算子> <運算元 2 >

將運算子置於兩運算元中間之表示法。 例如： a+b ， 3*2-6

缺點：電腦無法一次依序讀取運算式。因運算式可能含有括號，且

運算子優先順序不同

z 後序運算式(Postfix Order)：<運算元 1 > <運算元 2 > <運算子>

將運算子置於兩運算元之後之表示法。 例如： ab+ ， 3 2 * 6 -

p.s 此法又稱為反波蘭記號法；RPN。其優點在於不必使用括號，且

運算子不具優先權

4. 後序運算式之計算表示法 (Evaluation of Postfix Expression)

規則如下：

z 由左而右讀進後序運算式的每個字元(Token)

z 判別字元，若為運算元(operand)，則將其放入堆疊中。

z 判別字元，若為運算子(operand)，則自堆疊中取出適當個數之運算元，

(單元運算子，取一個運算元；二元運算子，取兩個運算元)，並執行運

算子所對應之計算，並將計算結果放入堆疊中。

z 若字串結束(end of string)，堆疊內唯一值即為所要結果。

Data Structure: Stacks 8

 單元運算子(Unary Operator) 二元運算子(Binary Operator)

+(正號) - (負號) !(not) *(乘號) /(除號) +(加號)

-(減號) && (and) || (or)

圖二； 常見運算子

Start

Initialize Stack

Read Next Token

yes Pop result from

End of String?
Stack
no
yes
Operand? Push x to Stack

no
Uinary Binary
Pop 1 operand Binary or Unary? Pop 2 operands
Perform operation Perform operations
Push results to stack Push results to stack

圖三；後序運算式之流程圖

Data Structure: Stacks 9

【範例-二】計算後序運算式: ( 6 2 3 + - 3 8 2 / + * 2 $ 3

+ )之值

Token Opnd1 Opnd2 Value Stack

6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
$ 7 2 49 49
3 7 2 49 49,3
+ 49 3 52 52

Data Structure: Stacks 10

【範例-三】 以下為計算後序運算式值之程式 (p.s. 此程式只計算常見之二元

運算元)

# include <stdio.h>
# include <math.h>
# include <ctype.h>
# include <stdlib.h>

/* 陣列堆疊宣告 */

#define N 100
int stack[N];

/**********************************************************************
* push 函式部分 ( stack［］ 宣告為全域變數 )
*****************************************************************/

void push(int d, int *top ) /*此處之 top 為一指標型區域變數*/

{
if (*top == N-1)
{
printf("堆疊滿了\n"); /* 注意堆疊大小 */
exit(1); /* exit 定義在 stdlib.h 中 */
/* exit(0)表示正常，exit(1) 表示有誤*/
} /* end if */
else
{
(*top)++; /*指標指向頂端，增量增加 1*/
stack[*top]=d; /*儲存資料 d 於堆疊頂端 */
} /* end else */

} /* end of push 函數 */

Data Structure: Stacks 11

/**********************************************************************
* pop 函式部分 ( stack［］ 宣告為全域變數 )
*****************************************************************/

int pop(int *top)

{
if (*top == -1) /* 注意空堆疊情形*/
{ printf("堆疊空了\n");
exit(1); /*刪除失敗，執行結束 */
}
else
return(stack[(*top)--]);
}

/***************************************************************************
* oper 函數 ( 檢查有效二元運算子，並計算該運算運用在其後兩參數之結果) *
***************************************************************************/

double oper(int symb, double op1, double op2)

{
switch (symb) {
case ‘+’ : return (op1+op2); /* 相加運算 */
case ‘-’ : return (op1-op2); /* 相減運算 */
case ‘*’ : return (op1*op2); /* 相乘運算 */
case ‘/’ : return (op1/op2); /* 相除運算 */
case ‘$’ : return (pow(op1,op2))； /*次方運算, pow 定義在 math.h 中*/
default : printf(“%s”, “illegal operation”);
exit(1); /* 加入失敗，執行結束 */
} /* end switch*/
} /* end oper 函數 */

/*****************************************************************
* eva_postfix 函數 (計算後序運算式值)
*****************************************************************/
double eval_postfix(char expr[])
{

Data Structure: Stacks 12

 int c, position;
double opnd1, opnd2, value;
top = -1; /* initialize stack*/

for (position = 0; (c = expr[position]) != ‘\0’; position++)

/* 將儲存後序運算式從頭到尾依序讀出 */
/* 字串之 ‘\0’ 為字串終止控制指令 */
if (isdigit(c)) /* 將自十進位數值字元轉換為可計算之 double */
/* isdigit(c) 函數定義在 ctype.h 中 */
push( (double)(c –‘0’),&top);
/* c - ‘0’ 會將字元變數 c 之 ASCII 碼減去字元 ’0’ 之 ASCII 碼 */
else
{ /* 此時讀進之字元為 operator */
opnd2 = pop(&top);
opnd1 = pop(&top); /* 取出堆疊最頂端的兩個運算元 */
value = oper(c, opnd1, opnd2); /* 並執行運算子所對應之計算 */
push(value, &top); /* 將計算結果放入堆疊中 */
} /* end else */
return (pop(&top)); /* 傳回堆疊內唯一值 */
} /* end eval_postfix */

/*****************************************************************
* 主程式部分
*****************************************************************/

void main()
{
char expr[N];
int position = 0;

while ((expr[position++] = getchar()) != ‘\n’ )

﹔ /* getchar() 函數定義在 ctype.h 中 */
/* 從系統開啟檔案或鍵盤中讀取單一字元 */

expr[--position] = ‘\0’;
printf (“\n %s %s “, “ the original postfix expression is “, expr);
/* 列印原始後序運算式 */
printf(“ \n %f”, eval_postfix(expr));
/* 列印計算後之計算值 */
} /* end main*/

Data Structure: Stacks 13

六. 堆疊之應用三：中序運算式轉換為後序運算式

方法一：

算術運算式由中序變為後序可依下列三步驟進行：

1. 將式子中的運算單元適當的加以括號，此時須考慮運算子的運算優先順序。

2. 將所有的運算子移到其對應的右括號。

3. 將所有的括號去掉。

如將 A*B/C 化為後序表示式

(1) ( ( A * B ) / C)

(2) ( ( A * B ) / C) =>( ( A B ) * C ) /

(3) AB*C/

再舉一例將 A-B/C+D*E-F%G 化成後序表示式

(1) ( ( (A- ( B / C ) ) + ( D * E ) ) - ( F % G ) )

(2) ( ( (A- ( B / C ) ) + ( D * E ) ) - ( F % G ) )

(3) ABC/-DE*+FG%-

Data Structure: Stacks 14

方法二：

Start

Initialize Stack

Read Next Token A

yes Print A
Operand?

no
yes Pop from Stack Stop
End of String?
until empty
no
yes
‘(‘ ? Push this token

no
yes Pop A from
‘)’ ?
stack and print
no A until ‘(‘
yes
ICP>ISP? Push A to Stack

no
Pop from Stack

圖四；中序運算式轉換為後序運算式之流程圖

規則如下：

z 由左而右讀進中序運算式的每個字元(Token)

z 判別字元，若為運算元(operand)，則直接輸出。

Data Structure: Stacks 15

 z 判別字元，若為運算子(operator)，則

(1) 若 Token 為”(” ，則直接加入堆疊頂端。

(2) 若 Token 之優先權 (ICP, In-Coming Priority) 高於堆疊頂端之優先權

(ISP, In-Stack Priority)，則直接加入堆疊頂端。

(3) 若 Token 之優先權 (ICP) 小於或等於於堆疊頂端之優先權(ISP)，則

將堆疊中之運算子自頂端逐一取出並輸出，直到堆疊頂端之運算子

優先權低於 Token，再將此 Token 放入堆疊中。

(4) 若 Token 為”)”，則將堆疊中之運算子自頂端逐一取出並輸出，直到

取出對應之”(”為止，但”(”不須輸出。注意： ”)”永遠不會被放入堆

疊中。

(5) 若字串結束(end of string, eos)，則將堆疊中所有運算子自頂端逐一取

出並輸出，值到堆疊空了。

In-Stack Priority In-Coming Priority

符號
(ISP) (ICP)
( 1 5
) 4 4
+ 2 2
- 2 2
* 3 3
/ 3 3
% 3 3
operand 0 0

Data Structure: Stacks 16

【範例 四】試將下列中序運算式 (infix) 轉換為後序運算式 (postfix):

(( A - ( B + C ))*D)$(E+F)

Step Token Postfix Stack

1 ( (

2 ( ((

3 A A ((

4 - A ((-

5 ( A ((-(

6 B AB ((-(

7 + AB ((-(+

8 C ABC ((-(+

9 ) ABC+ ((-

10 ) ABC+- (

11 * ABC+- (*

12 D ABC+-D (*

13 ) ABC+-D*

14 $ ABC+-D* $

15 ( ABC+-D* $(

16 E ABC+-D*E $(

17 + ABC+-D*E $(+

18 F ABC+-D*EF $(+

19 ) ABC+-D*EF+ $

20 ABC+-D*EF+$

Data Structure: Stacks 17

/* 【變數宣告部分】 */

#define N 100 /* N 為全域變數 */

typedef enum{left_paren,right_paren, plus, minus, times,
divide, mode, operand} precedence; /* 定義優先順序之資料型態 */

precedence stack[N];

int ISP[]= {1,4,2,2,3,3,3,0}; /* 定義堆疊頂端之優先權 */

int ICP[]= {5,4,2,2,3,3,3,0}; /* 定義 Token 之優先權 */

/*【get_token 函數 】 (讀取字元 Token，並按照其優先順序分類) */

precedence get_token (char token)

{
switch (token) /* 將讀進之 Token 量化並分類 */
{ case '(' : return left_paren; /* 此時 '(' 等於 left_paren = 0 */
case ')' : return right_paren; /* 此時 ')'等於 right_paren = 1 */
case '+' : return plus; /* 依此類推 */
case '-' : return minus;
case '*' : return times;
case '/' : return divide;
case '%' : return mode;
default : return operand;
} /* end switch*/
} /* end get_token 函數 */

/* 【infix_to_postfix 函數 】 (將中序式轉換為計後序運算式) */

void infix_to_postfix(char expr[])

{
int position=0; /* 目前讀取位元之位置 */
char c; /* 讀取一個字元 */
precedence token; /* 分類後之 token */
top = -1; /* initialize stack */

Data Structure: Stacks 18

 for (position = 0; (c = expr[position]) != '\0'; position++)
/* 將儲存中序運算式從頭到尾依序讀出 */
/* 字串之 '\0' 為字串終止控制指令 */
{
token = get_token(c); /* 讀取一個字元 */
switch (token)
{
case operand : /* 此時 token 為運算元 */
printf("%c", c);
break;

case right_paren :
while(stack[top] != left_paren)
/* 自堆疊頂端逐一取出並輸出，直到取出 '(' 為止 */
{
print_symbol(stack[top]);
pop(&top); /* 移除堆疊頂端之'(', 不須印出 */
} /* end while */
break;

default:
if (empty(&top)) /* empty stack, push the token directly */
push(token, &top);
else
{
while ((!empty(&top)) && (ISP[stack[top]] >= ICP[token]))
print_symbol(pop(&top));
push(token, &top); /* push token to stack */
} /* end else */
} /* end switch */
} /* end for */

do { /* end of string , pop from stack until empty */

token = pop(&top);
print_symbol(token);
} while (!empty(&top));

} /* end infix_to_postfix */

→ p.s empty 及 print_symbol 函數須自行定義

Data Structure: Stacks 19
【範例-五】試將下列中序運算式 (infix) 轉換為後序運算式 (postfix):

a*(b+c/d–e)*f

輸入字元 堆疊內容 輸出字元 說明

\0

【習題】

1. 將下列中序運算式轉換後序式 2. 將下列後序運算式轉為中序式
(a.) a + ( b – c / d) * e (a.) a b + c-
(b.) (a - b + c ) / ( d – e / f * g) (b.) a b c - *
(c.) (a - b ) - ( c + d ) $ e * f (c.) a b – c + d e f - + $
(d.) (a - b ) $ (c * ( d – e ) + f) – g (d.) a b c d e - + $ * f g * -

3. 求下列後序式之值 4. 將下列中序運算式轉換前序式
(a.) 1 5 + 3 – 4 1 + 2 $ - (a.) a + ( b – c / d) * e
(b.) 6 2 4 + * 2 1 6 5 - + *\ (b.) (a - b + c ) / ( d – e / f * g)
(c.) (a - b ) - ( c + d ) $ e * f
(d.) (a - b ) $ (c * ( d – e ) + f) – g

Data Structure: Stacks 20