Stack 只是在list最後面來進行新增'刪除的線性表。
queu則是只允計在一端進行插入操作，而在另一端進行刪除操作的線性表。
Stack 的定義
只限定只能在表尾進行插入和刪除操作的線性表(list)。
其可以插入和刪除的那一端稱為top，另一端則稱為bottom。不含任何數據元素時則稱為空堆疊。
又可稱為後進先出(First In Last Out，FILO)結構。
仍為線性表(一致、線性及有限)，即前後的關係。而只是其特殊在於只能在尾(top)進行新增(push)'刪除(pop)動作。
Stack的抽象數據類型
1: ADT STACK(堆疊) 2: Data 同list。元素都為相同類，且其元素間具有前、後間的關係。 3: 4: Operator5: InitStack(*S);//初始化，建立一個空stack
6: DestorStack(*S);//若stack存在，則銷
7: ClearStack(*S); //將stack清空
8: StackEmpty(S);//判斷是否為空,是return true; else return false
9: GetTop(S,*e);//取其top的元素.
10: Push(*S,e)//若Stack存在,插入新元素e到堆疊s並成為其top11: Pop(*S,*e);//刪除S中的top元素,並用e傳回
12: StackLength(S);//傳回其元素數.
13: endADT順序存儲結構的Stack(其存取均為o(1))
1: typedef int Status;
2: typedef int SElemType; /* SElemType類型根據實際情形而定，這裡假設為int */
3: 4: /* 堆疊結構 */
5: typedef struct
6: { 7: SElemType data[MAXSIZE];8: int top; /* 用於堆疊頂端指標 */
9: }SqStack;其top同，前面在list的counter。
而不同的是，它實際就是記憶体位置(以0為底時)
Push
/* 插入元素e為新的堆疊頂端元素 */Status Push(SqStack *S,SElemType e)
{if(S->top == MAXSIZE -1) /* 堆疊是滿的 */
{ return ERROR;}
S->top++; /* 堆疊頂端指標+1 */ S->data[S->top]=e; /* 將新插入元素推入到堆疊頂端空間 */ return OK;}
Pop
/* 若堆疊不為空，則刪除S的堆疊頂端元素，用e返回其值，並傳回OK；否則，傳回ERROR */Status Pop(SqStack *S,SElemType *e)
{ if(S->top==-1) return ERROR; *e=S->data[S->top]; /* 將要刪除的堆疊頂端元素傳給e */ S->top--; /* 堆疊頂端指標-1 */ return OK;}
鏈結存儲結構的Stack(與順序stack，相同存取均為O(1),不用有迴圈。不同處於其輸入問題規模大小)
因為其Stack只能在top中來進行push 'pop操作。
而在link list中，其top是要放在那邊(頭、尾)。
這裡是將頭node和top放在一起。
故其原本的頭node中,的意義改變。變成一般的元素。
將頭節點設為Stack的top
空：count=0
第一節點,count=1
typedef int Status;
typedef int SElemType; /* SElemType類型根據實際情形而定，這裡假設為int */
/* 堆疊的鏈結儲存結構 */typedef struct StackNode
{SElemType data;
struct StackNode *next;}StackNode,*LinkStackPtr;
typedef struct
{LinkStackPtr top;
int count;}LinkStack;
即將原本的link list再包一層變為link stack
Push
/* 插入元素e為新的堆疊頂端元素 */Status Push(LinkStack *S,SElemType e)
{ LinkStackPtr pnew=(LinkStackPtr)malloc(sizeof(StackNode)); pnew->data=e;
pnew->next=S->top; /* 把目前的堆疊頂元素傳給新節點的直接後繼者 */ //其LinkStack中為指向StackNode的陣列及一個counter S->top=pnew; /* 將新的節點s傳給堆疊頂指標 */S->count++;
return OK;}
Pop
/* 若堆疊不空，則刪除S的堆疊頂元素，用e返回其值，並返回OK；否則，返回ERROR */Status Pop(LinkStack *S,SElemType *e)
{ LinkStackPtr p;
if(StackEmpty(*S)) return ERROR;*e=S->top->data;
p=S->top; /* 將堆疊頂節點傳給p */ S->top=S->top->next; /* 使得堆疊頂指標下移一位，指向後一節點 */ free(p); /* 釋放節點p */ S->count--;
return OK;}
遞迴函式(迭代)
把一個直接called自己或通過一系列的statement來called自己的函式，稱為遞迴函式。
每個遞迴定義必須至少有一個條件，當滿足時其遞迴就不再進行。即不再called自己而是返回數值。
1: #include "stdio.h"
2: 3: int Fbi(int i) /* 費伯納西的遞迴函式 */
4: {5: if( i < 2 )
6: return i == 0 ? 0 : 1;
7: return Fbi(i - 1) + Fbi(i - 2); /* 這裡Fbi就是函式自己，等於在呼叫自己 */
8: } 9: 10: int main()
11: {12: int i;
13: int a[40];
14: printf("反覆運算顯示費伯納西數列：\n");
15: a[0]=0; 16: a[1]=1;17: printf("%d ",a[0]);
18: printf("%d ",a[1]);
19: for(i = 2;i < 40;i++)
20: { 21: a[i] = a[i-1] + a[i-2]; 22: printf("%d ",a[i]);
23: } 24: printf("\n");
25: 26: printf("遞迴顯示費伯納西數列：\n");
27: for(i = 0;i < 40;i++)
28: printf("%d ", Fbi(i));
29: return 0;
30: }Fbi(5)=
Fbi(4)+Fbi(3)=
Fbi(3)+Fbi(2)+Fbi(2)+Fbi(1)=
Fbi(2)+Fbi(1)+1+1+1=5
迭代是利用循環結構而遞迴是使用選擇結構。遞迴可以使程序結構清晰、理解，但需要大量的時間及存取空間。
應用參考:
四則運算
中綴表示：1+2*3/(4+2)=1+6/6=2
后綴表示：
a.數字直接輸出
b.遇符號時,若其符號為右括號(')')則把stack輸出到左括號(,
其它符號,則判斷stack top symbol 高於 輸入符號時輸出 或 是右括號時即輸出
如下：
a.input :1 , output :1 ,stack : none
b.input :+ , output :1 ,stack : +
c.input :2 , output :12 ,stack : +
d.input :* , output :12 ,stack : +* (top is +, input is * then not higher .)
e.input :3 , output :123 ,stack : +*
f.input :/ , output :123* ,stack : +/ (top is *, input is / then not higher .)
g.input :( , output :123* ,stack : +/(
h.input :4 , output :123*4 ,stack :+/(
i.input :+ , output :123*4 ,stack : +/(+
j.input :2 , output :123*42 ,stack : +/(+
k.input :) , output :123*42+ ,stack : +/
L. 最後, output :123*42+/+
而后綴運算:123*42+/+
1.數字push stack
2.符號pop 2 stack 運算並push
a. input :1 , output :none ,stack : 1
b. input :2 , output :none ,stack : 12
c. input :3 , output :none ,stack : 123
d. input :* , output :none ,stack : 16 (for 2*3)
e. input :4 , output :none ,stack : 164
f. input :2 , output :none ,stack : 1642
g. input :+ , output :none ,stack : 166 (for 4+2)
h. input :/ , output :none ,stack : 11(for 6/6)
e. input :+ , output :none ,stack : 2 (for 1+1)
程式下載
https://drive.google.com/?tab=mo&authuser=0#folders/0B2uYQcUgyMUJUW0wNXUxaXpHZEk
