前言

●資料結構作為計算機專業基礎課，綜合性強，抽象性高，在一定程度上增加了學習難度，本次我們共同從資料結構的基礎探討，由淺入深進行資料結構的學習，
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教！

●本文只淺顯的探討了堆疊的基本知識，作者相信隨著學習課程的深入，我們將會對資料結構有更深的理解與識訓！

正文————————————————

一、堆疊

1.堆疊的概念及術語

1.定義：

2.邏輯結構：

3.存盤結構：

4.運算規則：

5.實作方式：

6.堆疊是一種特殊的線性表，它的邏輯結構和存盤結構與線性表相同，其特殊性體現在“運算受限” ，

2.堆疊的特點：

二、堆疊的表示及基本操作：

1.順序堆疊：

順序堆疊的型別定義

說明：

順序堆疊的演算法實作

2.鏈堆疊：

鏈堆疊的型別定義

說明：

鏈堆疊的演算法實作

三、堆疊與遞回

遞回的定義

以下三種情況常常用到遞回方法

總結：

本文共同探討了堆疊的相關內容，在日常生活中有極其豐富的應用，作者認為要認真對待資料結構的學習，搭建基本知識框架，隨著榷訓月累的學習逐漸填補總結，從腳踏實地做起，祝愿大家能夠熟悉掌握這門課程，并將其能夠熟悉的應用！

●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教！————————————————

前言

●資料結構作為計算機專業基礎課，綜合性強，抽象性高，在一定程度上增加了學習難度，本次我們共同從資料結構的基礎探討，由淺入深進行資料結構的學習，
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教！

●本文只淺顯的探討了堆疊的基本知識，作者相信隨著學習課程的深入，我們將會對資料結構有更深的理解與識訓！

正文
————————————————

一、堆疊

1.堆疊的概念及術語

1.定義：

只能在表的一端（堆疊頂）進行插入和洗掉運算的線性表

2.邏輯結構：

與線性表相同，仍為一對一關系

3.存盤結構：

用順序堆疊或鏈堆疊存盤均可，但以順序堆疊更常見

4.運算規則：

只能在堆疊頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則

5.實作方式：

關鍵是撰寫入堆疊和出堆疊函式，具體實作依順序堆疊或鏈堆疊的不同而不同基本操作有入堆疊、出堆疊、讀堆疊頂元素值、建堆疊、判斷堆疊滿、堆疊空等

6.堆疊是一種特殊的線性表，它的邏輯結構和存盤結構與線性表相同，其特殊性體現在“運算受限” ，

限制在表的一端進行插入和洗掉操作， 能夠進行操作的一端是浮動端，稱之為堆疊頂，通常用一個“堆疊頂指標”指示，它的位置會隨著操作而發生變化；與此相對，表的另一端是固定端，稱之為堆疊底， 如同線性表可以為空表一樣，當堆疊中沒有元素時稱為空堆疊，往堆疊中插入元素的操作稱為入堆疊，洗掉堆疊中元素的操作稱堆疊，

2.堆疊的特點：

二、堆疊的表示及基本操作：

1.順序堆疊：

順序堆疊的型別定義

#define MAXSIZE 100
typedef struct
{ 
	DataType data[MAXSIZE];
	int top;
}SqStack;

說明：

在順序堆疊中，用于指示堆疊頂的當前位置的top是整型，它的實質是堆疊頂元素在陣列中的下標，堆疊頂指標top直接反映出堆疊的當前狀態：空堆疊時，堆疊頂指標top為-1；

堆疊滿時，堆疊頂指標top為MAXSIZE-1；

入堆疊時，堆疊頂指標top加1；

出堆疊時，堆疊頂指標top減1，

堆疊底位置固定不變，可以設定在陣列的任意端，一般習慣上將陣列低下標端作為堆疊底，

順序堆疊的演算法實作


(1)初始化堆疊(置堆疊空) 
初始化堆疊主要是分配存盤空間，并將堆疊頂指標置為-1， 
int  InitStack(SqStack &S)
{   //構造一個空堆疊
	S.top= -1;
	return OK;
}

(2)判堆疊空
int  StackEmpty(SqStack S) 
//判堆疊為空堆疊時回傳值為真，反之為假
{ return(S.top==-1? TRUE:FALSE);} 

(3)判堆疊滿
int StackFull(SqStack S)
//判堆疊為滿堆疊時回傳值為真，反之為假
{   return(S.top==MAXSIZE-1?TRUE:FALSE);}

(4)進堆疊
進堆疊時應首先判堆疊滿，若堆疊不滿則將堆疊頂指標top上移，存入元素，
int Push(SqStack &S, DataType e)
{ //將元素e插入到堆疊中，作為的新堆疊頂
	if(StackFull(S))  return ERROR; //堆疊滿
	S.top++;    // top加1，堆疊頂位置上移
	S.data[S.top]=e;   //資料e存入當前堆疊頂
	return  OK;
}

(5)出堆疊
出堆疊時應首先判斷堆疊是否為空，若堆疊不為空，則取出堆疊頂元素，將堆疊頂指標top下移，再回傳堆疊頂元素，
int Pop(SqStack &S,DataType &e)
{//若堆疊不為空，則洗掉堆疊頂元素
	if(StackEmpty(S)) return ERROR; //堆疊空
	e=S.data[S.top];   //取出資料放入e所指單元中
	S.top--;     // top減1，堆疊頂位置下移
	return OK;
}

(6)取堆疊頂元素1
int GetTop(SqStack S,DataType &e)
{//若堆疊不為空，則取堆疊頂元素
	if(StackEmpty(S)) return ERROR;  //堆疊空
	e=S.data[S.top];    //取出資料，top不變
	return OK;
}

(6)取堆疊頂元素2
DataType GetTop(SqStack S)
{//若堆疊不為空，則取堆疊頂元素
    DataType e;
	if(StackEmpty(S)) return ERROR;  //堆疊空
	e=S.data[S.top];    //取出資料，top不變
	return e;
}

2.鏈堆疊：

鏈堆疊的型別定義

鏈堆疊：通常用一個無頭結點的單鏈表表示，其結點結構與單鏈表的結點結構相同，
typedef struct node
{ 
       DataType data;
       struct node* next;
} StackNode,*LinkStack;
LinkStack top;   //top為堆疊頂指標

說明：

對于單鏈表來說，在表頭插入和洗掉結點要比在表尾相對簡單，因此將單鏈表表頭作為堆疊頂，則單鏈表的頭指標即為堆疊頂指標，

鏈堆疊的演算法實作

鏈堆疊的本質是簡化的單鏈表，top作為堆疊頂指標始終指向鏈表首結點，進堆疊操作就是在鏈表表頭插入一個新的結點，出堆疊操作就是洗掉當前的表頭結點并釋放空間，

(1)初始化堆疊(置空堆疊)
LinkStack  InitStack()
//空堆疊的top指標為NULL
｛  return NULL;   ｝
(2)判堆疊空
int  StackEmpty(LinkStack top)      
//判堆疊為空堆疊時回傳值為真，反之為假
{   return(top==NULL? TRUE:FALSE);  }
(3)進堆疊
void Push(LinkStack top, DataType e)
{   //將元素e進鏈堆疊,即在表頭插入新的結點
	StackNode  *s;
	s=(StackNode*)malloc(sizeof(StackNode));
	s->data=e;
	s->next=top;
	top=s;
}
(4)出堆疊
int Pop(LinkStack top,DataType &e)
{   //若堆疊不為空將堆疊頂元素出堆疊，即為洗掉表頭結點
	StackNode *p;
	if(StackEmpty(top)) return  ERROR;  //堆疊空
	e=top->data;
	p=top;
	top=top->next;
	free(p);
	retrun OK;
}

三、堆疊與遞回

遞回的定義

若一個物件部分地包含它自己, 或用它自己給自己定義, 則稱這個物件是遞回的；

若一個程序直接地或間接地呼叫自己, 則稱這個程序是遞回的程序，
long Fact ( long n ) {
    if ( n == 0) return 1;
    else return n * Fact (n-1); }