Stack

Stack 只是在list最後面來進行新增'刪除的線性表。

queu則是只允計在一端進行插入操作，而在另一端進行刪除操作的線性表。

 

Stack 的定義

只限定只能在表尾進行插入和刪除操作的線性表(list)。

其可以插入和刪除的那一端稱為top，另一端則稱為bottom。不含任何數據元素時則稱為空堆疊。

又可稱為後進先出(First In Last Out，FILO)結構。

仍為線性表(一致、線性及有限)，即前後的關係。而只是其特殊在於只能在尾(top)進行新增(push)'刪除(pop)動作。

Stack的抽象數據類型

   1: ADT STACK(堆疊)

   2: Data 同list。元素都為相同類，且其元素間具有前、後間的關係。

   3:  

   4: Operator

   5:     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並成為其top

  11:     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