這兩天翻了下數據結構與算法分析、嚴蔚敏的數據結構、C和指針、C Primer Plus這些本書，受益很多。不過大多的示例不夠完整，需要自己動手編寫程序。又看了遍培訓時的筆記，雖然很糙但是精華的部分還是可以借鑒的。還有看到了不錯的博文，參看：數據結構與算法分析 學習筆記?對于數據結構與算法，盡量做到多方面的參考。多的不說了，下面就開始總結！！

一、首先講一些基本的概念

1、數據結構的基本概念

在計算機學科中數據結構表示數據在計算機中的存儲和組織形式。主要描述數據元素之間和位置關系等。一般來說，選擇適當的數據結構可以提高計算機程序的運行效率（時間復雜度）和存儲效率（空間復雜度）。

2、數據結構的三種層次

（1）邏輯結構--抽象層

主要描述的是數據元素之間的邏輯關系

（2）物理結構--結構層

主要描述的是數據元素之間的位置關系

（3）運算結構--實現層

主要描述的是如何實現數據結構

3、邏輯結構的分類 (抽象數據類型 ADT)

（1）集合結構（集）

主要描述所有的元素都屬于一個總體，除了同屬于一個集合外沒有其他關系。集合結構不強調元素之間的任何關聯性。

（2）線性結構（表）

主要描述元素之間具有一對一的前后關系。結構中必須存在唯一的首元素和唯一的尾元素。除了首元素之外結構中的每一個元素有且僅有一個前趨元素，除了尾元素之外結構中的每一個元素有且僅有一個后繼元素。

（3）樹形結構（樹）

主要描述元素之間存在一對一個關系。樹形結構中必須存在唯一跟關系，頂端的元素叫做葉元素。除了根元素之外，結構中每一個元素有且僅有一個前趨元素，除了葉元素之外，結構中每一個元素擁有一個到多個后繼元素。如：樹，家譜。

（4）網狀結構（圖）
主要描述數據元素之間存在多對多的交叉映射關系，也叫做圖形結構。結構中的每個元素都可以擁有多個任意數量，前驅和后繼元素，結構中的任意兩個元素都可以建立關聯。如：蜘蛛網 網球拍。

4、物理結構的分類

（1）順序結構

順序結構就是使用一組連續的存儲單元依次存儲邏輯上相鄰的各個元素，順序結構可以借助計算機程序設計語言（如C/C++）提供的數組類型加以描述。

優點：

只需要申請存放數據本身的內存空間即可，不需要額外的內存來表達數據元素之間的邏輯關系。

支持下標訪問，也可以實現隨機訪問。

缺點：

連續的存儲空間導致內存空間的利用率比較低。

向順序存儲結構中插入/刪除元素時，可能需要移動大量元素，效率比較低。

（2）鏈式結構

表示在計算機中使用一組任意的存儲單元來存儲所有的元素（這組存儲單元可以是連續的，也可以是不連續的）。不要求邏輯上相鄰的元素在物理位置上也相鄰。

鏈式存儲結構不使用連續的存儲空間存放結構的元素，而是為每一個元素構造一個節點。節點中除了存放數據本身以外，還需要存放指向下一個節點的指針。絕大多數程序設計語言（如C/C++）都沒有提供用于描述鏈式結構的數據類型，需要編寫額外的代碼去實現。
優點：
不采用連續的存儲空間導致內存空間利用率比較高，克服順序存儲結構中預知元素個數的缺點
插入或刪除元素時，不需要移動大量的元素，比較當便。
缺點：
除了申請存放數據本身的內存空間外，還需要額外的空間來表達數據之間的邏輯關系
不支持下標訪問和隨機訪問。

5、邏輯結構和物理結構的關系

每種邏輯結構采用何種物理結構來實現，并沒有具體的規定。通過根據實現的難易程度，以及在時間復雜程度和空間復雜程度方面的要求，來選擇合適的物理結構。

6、運算結構

（1）分配資源，建立結構，釋放資源

如：int arr[5]； ->棧區，系統自動分配內存和回收內存。

（2）插入和刪除

增加和減少元素

（3）獲取和遍歷

查看具體的元素值，以及遍歷結構中所有的元素值

（4）修改和排序

修改元素的值，采用排序算法進行排序

二、棧 ADT

棧（stack）是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端，叫做棧頂（top）。它是后進先出（LIFO）的。對棧的基本操作只有push（進棧）和pop（出棧）兩種，前者相當于插入，后者相當于刪除最后的元素。上篇文章講遞歸的有講到，程序在運行時，如果調用一個函數，則將該函數壓棧（push），調用完一個函數則出棧（pop）。遞歸過程中，不斷的壓棧(因為該函數并沒有執行完畢，因為還沒有執行到函數的最后一個大括號 } )。因為內存是有限的，因此會造成棧溢出。 由于棧在本質上是一種受限制的表，所以可以使用任何一種表的形式來實現它，我們最常用的一般有兩種： （1）順序棧：數組 （2）鏈式棧：鏈表 它們在復雜度上的優缺點對比如下： 1、新增和刪除元素時的時間復雜度 鏈表：在動態申請內存（new或者malloc）上的花銷非常昂貴。 數組：幾乎沒有花銷，以常數 O(1) 時間運行，在帶有自增和自減尋址功能的寄存器上操作時，編譯器會把整數的 push 和 pop 操作編譯成一條機器指令。 2、空間復雜度 鏈表：由于空間是動態申請、釋放的，因此不會浪費空間，而且只要物理存儲器允許，理論上能夠滿足最大范圍未知的情況。 數組：必須在初始化時執行棧的大小，有可能會浪費空間，也有可能不夠空間用。 結論： （1）如果對運動時的效率要求非常高，并且能夠在初始化時預知棧的大小，那么應該首選數組形式，否則應該選用鏈表形式。 （2）由于對棧的操作永遠都是針對棧頂（top）進行的，因此數組的隨機存取的優點就沒有了，而且數組必須預先分配空間，空間大小也受到限制，所以一般情況下（對運行時效的要求不是太高）鏈表應該是首選。

三、順序棧

其中又分為靜態數組和動態數組兩類。
靜態數組：特點是要求結構的長度固定，而且長度在編譯時候就得確定。其優點是結構簡單，實現起來方便而不容易出錯。而缺點就是不夠靈活以及固定長度不容易控制，適用于知道明確長度的場合。
動態數組：特點是長度可以在運行時候才確定以及可以更改原來數組的長度。優點是靈活，缺點是由此會增加程序的復雜性。

1、靜態數組

在靜態數組堆棧中，棧的長度以一個 #define 定義的形式出現，在模塊被編譯之間用戶必須對數組長度進行設置。變量top_element 保存棧頂元素的下標值。它的初始值為 -1，提示棧為空。push 函數在存儲新元素前先增加這個變量的值，這樣 top_elelment 始終包含棧頂元素的下標志。如果把它的初始值設為 0，top_element 將指向數組的下一個可用位置。這種方法當然也可以，但它的效率稍差一些，因為它需要執行一次減法運算才能訪問棧頂元素。執行 pop 函數，top_element ?在元素被復制出數組之后才減 1，這和 push 相反，后者是在被元素復制到數組之前先加 1。pop 函數不需要從數組中刪除元素，只需減少棧頂指針的值就足矣，因為用戶此時已不能再訪問這個舊值了。 參看：C語言再學習-- assert 斷言宏 使用斷言，相對來說比較簡單。但是也會有困擾就是入棧出棧時檢測到棧為滿或棧為空?程序會終止。但如果用戶希望確保程序不會終止，那么程序壓棧一個新值之前必須檢測堆棧是否仍有空間。因此，斷言必須只能夠對那些用戶自己也能進行檢查的內容進行檢查。后面會再寫一個例子，講到這種情況。travel (); pop (); 輸出結果： 這個棧為空 棧為空 a.out: a_stack.c:73: pop: Assertion `!is_empty ()' failed. 已放棄 (核心已轉儲) 再有注意：所有不屬于外部接口的內容都被聲明為 static，這可以防止用戶預定義接口之外的任何方式訪問堆棧中的值。
代碼實現說明： 很簡單，一句話使用數組下標
#include <stdio.h> #include <assert.h> #include <stdlib.h> #define STACK_TYPE int /* 堆棧所存儲的值的數據類型 */ #define STACK_SIZE 100 /* 堆棧最大容納元素數量 */ /* 存儲堆棧中的數組和一個指向堆棧頂部元素的指針 */ static STACK_TYPE stack[STACK_SIZE]; static int top_element = -1; /* 將一個新值壓入堆棧中，參數是被壓入的值。*/ void push (STACK_TYPE value); /* 彈出堆棧中棧頂的一個值，并丟棄。*/ void pop (void); /* 返回堆棧頂部元素的值，但不改變堆棧結構。*/ STACK_TYPE top (void); /* 如果堆棧為空，返回TRUE,否則返回FALSE。*/ int is_empty (void); /* 如果堆棧為滿，返回TRUE,否則返回FALSE。*/ int is_full (void); /* 自定義函數實現遍歷操作 */ void travel (void); /* 計算棧中元素的個數 */ int size (void); int main (void) { travel (); pop (); printf("%s\n", is_empty() ? "棧為空" : "棧未空"); int i = 0; for (i = 0; i <= 9; i++) { push (i); } puts ("push 壓棧后的數值為: "); travel (); printf ("此時棧頂元素為：%d\n", top ()); printf ("此時棧元素個數為：%d\n", size ()); pop (); pop (); puts ("經過pop彈出幾個元素后的棧元素： "); travel (); printf("%s\n", is_full() ? "棧為滿" : "棧未滿"); printf("%s\n", is_empty() ? "棧為空" : "棧未空"); printf ("此時棧頂元素為：%d\n", top ()); printf ("此時棧元素個數為：%d\n", size ()); return 0; } void push (STACK_TYPE value) { //assert (!is_full ()); /* 壓入堆棧之前先判斷是否堆棧已滿*/ if (is_full ()){printf ("棧已滿，入棧失敗\n"); return ;}top_element += 1; stack[top_element] = value; } void pop (void) { //assert (!is_empty ()); /* 彈出堆棧之前先判斷是否堆棧已空 */ if (is_empty ()) { printf ("棧已空，出棧失敗\n"); return ; } top_element -= 1; } STACK_TYPE top (void) { //assert (!is_empty ()); if (is_empty ()) { printf ("棧已空，出棧失敗\n"); return ; } return stack[top_element]; } int is_empty (void) { return top_element == -1; } int is_full (void) { return top_element == STACK_SIZE -1; } void travel (void) { int i = 0; if (top_element == -1) printf ("這個棧為空"); for (i = 0; i <= top_element; i++) printf ("%d ", stack[i]); printf ("\n"); } int size (void) { return top_element + 1; } 輸出結果： 這個棧為空 棧已空，出棧失敗 棧為空 push 壓棧后的數值為: 0 1 2 3 4 5 6 7 8 9 此時棧頂元素為：9 此時棧元素個數為：10 經過pop彈出幾個元素后的棧元素： 0 1 2 3 4 5 6 7 棧未滿 棧未空 此時棧頂元素為：7 此時棧元素個數為：8

2、動態數組

和靜態數組主要區別在于在接口中定義了兩個新函數：創建堆棧、銷毀堆棧。 參看：C語言再學習 -- 再論數組和指針? 其實不是數組，而是指針以下標形式訪問。 create_stack 函數首先檢查堆棧是否已經創建。然后分配所需要數量的內存并檢查分配是否成功。 destroy_stack 函數在釋放內存之后把長度設置為 0、指針變量重新設置為 NULL，這樣它們可以用于創建另一個堆棧。 在is_full he ?is_empty 函數中都增加了一條斷言。這條斷言可以防止任何堆棧函數在堆棧被創建前就被調用。其余的堆棧函數并不需要這條斷言，因為它們都調用了這兩個函數之一。 警告：在內存有限的環境中，使用 assert 檢查內存分配是否成功并不合適，因為它很可能導致程序終止。這未必是你希望的結果。
代碼實現說明： 也很簡單，一句話動態分配內存，使用數組下標 /* 堆棧的長度在創建堆棧的函數被調用時給出，該函數必須在任何其他操作堆棧的函數被調用之前調用 */ #include <stdio.h> #include <assert.h> #include <stdlib.h> #define STACK_TYPE int /* 堆棧所存儲的值的數據類型 */ /* 用于存儲堆棧元素的數組和指向堆棧頂部元素的指針 */ static STACK_TYPE *stack; static int stack_size; static int top_element = -1; /* 創建對棧，參數指定對棧可以保存多少個元素 注意：此函數只適用于動態分配數組形式的堆棧。 */ void create_stack (size_t size); /* 銷毀一個堆棧，釋放堆棧所適用的內存 注意，此函數只適用于動態分配數組和鏈表結構的堆棧。 */ void destroy_stack (void); /* 將一個新值壓入堆棧中，參數是被壓入的值。*/ void push (STACK_TYPE value); /* 彈出堆棧中棧頂的一個值，并丟棄。*/ void pop (void); /* 返回堆棧頂部元素的值，但不改變堆棧結構。*/ STACK_TYPE top (void); /* 如果堆棧為空，返回TRUE,否則返回FALSE。*/ int is_empty (void); /* 如果堆棧為滿，返回TRUE,否則返回FALSE。*/ int is_full (void); /* 自定義函數實現遍歷操作 */ void travel (void); /* 計算棧中元素的個數 */ int size (void); int main (void) { create_stack (50); travel (); pop (); printf("%s\n", is_empty() ? "棧為空" : "棧未空"); int i = 0; for (i = 0; i <= 9; i++) { push (i); } puts ("push 壓棧后的數值為: "); travel (); printf ("此時棧頂元素為：%d\n", top ()); printf ("此時棧元素個數為：%d\n", size ()); pop (); pop (); puts ("經過pop彈出幾個元素后的棧元素： "); travel (); printf("%s\n", is_full() ? "棧為滿" : "棧未滿"); printf("%s\n", is_empty() ? "棧為空" : "棧未空"); printf ("此時棧頂元素為：%d\n", top ()); printf ("此時棧元素個數為：%d\n", size ()); destroy_stack (); printf ("此時棧元素個數為：%d\n", size ()); return 0; } void create_stack (size_t size) { //assert (stack_size == 0); if (size < stack_size) { printf ("棧元素個數太少\n"); return ; } stack_size = size; stack = (STACK_TYPE *)malloc (stack_size * sizeof (STACK_TYPE)); if (NULL == stack) perror ("malloc分配失敗"), exit (1); } void destroy_stack (void) { //assert (stack_size > 0); if (stack != NULL) { printf ("銷毀堆棧\n");stack_size = 0; free (stack); stack = NULL; top_element = -1; } } void push (STACK_TYPE value) { //assert (!is_full ()); if (is_full ()) { printf ("棧已滿，入棧失敗\n"); return ; } top_element += 1; stack[top_element] = value; } void pop (void) { //assert (!is_empty ()); if (is_empty ()) { printf ("棧已空，出棧失敗\n"); return ; } top_element -= 1; } STACK_TYPE top (void) { //assert (!is_empty ()); if (is_empty ()) { printf ("棧已空，出棧失敗\n"); return ; } return stack[top_element]; } int is_empty (void) { //assert (stack_size > 0); if (stack != NULL) { return top_element == -1; } } int is_full (void) { //assert (stack_size > 0); if (stack != NULL) { return top_element == stack_size - 1; } } void travel (void) { int i = 0; if (top_element == -1) printf ("這個棧為空"); for (i = 0; i <= top_element; i++) printf ("%d ", stack[i]); printf ("\n"); } int size (void) { return top_element + 1; } 輸出結果： 這個棧為空 棧已空，出棧失敗 棧為空 push 壓棧后的數值為: 0 1 2 3 4 5 6 7 8 9 此時棧頂元素為：9 此時棧元素個數為：10 經過pop彈出幾個元素后的棧元素： 0 1 2 3 4 5 6 7 棧未滿 棧未空 此時棧頂元素為：7 此時棧元素個數為：8 銷毀堆棧 此時棧元素個數為：0

3、自寫順序棧

在壓棧和出棧的時，使用 if 語句來判斷棧是否為滿或是否為空。如此，可以避免程序不必要的終止。 需要注意：if 語句最后使用的是 return ;而非 exit (1); 這方面參看：C語言再學習 -- 關鍵字return和exit ()函數 //使用順序存儲結構實現棧的基本操作 #include <stdio.h> #include <stdlib.h> #define SIZE 5 //給數據類型起別名，支持其他的數據類型 int arr[SIZE]; //存儲具體的元素值 int pos; //記錄數據的下表 //自定義函數實現入棧操作 //入棧==賦值 void push (int data); //自定義函數實現遍歷操作 // 遍歷==打印 void travel (void); //自定義函數實現出棧操作 int pop (void); //查看棧頂元素 int top (void); //判斷棧是否為滿 int full (void); //判斷棧是否為空 int empty (void); //計算棧中元素的個數 int size (void); int main (void) { printf ("出棧的元素是：%d\n", pop ()); printf ("棧頂元素是：%d\n", top ()); int i = 0; for (i = 0; i <= 6; i++) push (i); travel (); printf ("出棧的元素是：%d\n", pop ()); travel (); printf ("棧頂元素是：%d\n", top ()); printf ("%s\n", full () ? "棧為滿" : "棧未滿"); printf ("%s\n", empty () ? "棧為空" : "棧未空"); printf ("棧元素個數為：%d\n", size ()); return 0; } void push (int data) { //判斷為不為滿 ，避免可能編譯報錯 if (full ()) { printf ("棧已滿，入棧失敗\n"); return ; } arr[pos++] = data; } void travel (void) { printf ("棧中元素有："); int i = 0; for (i = 0; i <= pos - 1; i++) printf ("%d ", arr[i]); printf ("\n"); } int pop (void) { //判斷棧是否為空 if (!pos) { printf ("棧已空，出棧失敗\n"); return ; } return arr[--pos]; } int top (void) { //判斷棧是否為空 if (!pos) { printf ("棧已空， 查看棧元素失敗\n"); return ; } return arr[pos - 1]; } int full (void) { return SIZE == pos; } int empty (void) { return 0 == pos; } int size (void) { return pos; } 輸出結果： 棧已空，出棧失敗 出棧的元素是：25 棧已空， 查看棧元素失敗 棧頂元素是：35 棧已滿，入棧失敗 棧已滿，入棧失敗 棧中元素有：0 1 2 3 4 出棧的元素是：4 棧中元素有：0 1 2 3 棧頂元素是：3 棧未滿 棧未空 棧元素個數為：4

4、順序棧總結

（1）預分配空間 由用戶指定堆棧最多能容納得元素個數，即堆棧容量，分配足量的內存，幾下堆棧容量，并將棧頂指針初始化為 0? （2）壓入彈出 被壓入的元素放在棧頂指針處，同時棧頂指針上移，被彈出的元素從棧頂指針的下面獲得，同時棧頂指針下移。 （3）判空判滿 棧頂指針為 0 表示堆棧已空，此時不可再彈出，棧頂指針大于等于堆棧容量比哦啊好似堆棧已滿，此時不可再壓入。

四、鏈式棧

由于只有堆棧頂部元素才可以被訪問，因此使用單鏈表可以很好實現鏈式堆棧，而且無長度限制。把一個新元素壓入堆棧是通過在鏈表的起始位置添加一個元素實現的。從堆棧中彈出一個元素是通過從鏈表中移除第 1 個元素實現的。位與鏈表頭部的元素總是很容易被訪問。由于沒有長度限制，故不需要create_stack函數，但可以實現destroy_stack函數用于清空堆棧。由于用于存儲元素的內存是動態分配的，它必須予以釋放以避免內存泄漏。
代碼實現說明： 主要講下壓棧和出棧。壓棧：新建一個節點，讓它后面的節點指向原來的棧頂節點，它成為新的棧頂節點。出棧：為棧頂節點找個替身，然后將棧頂節點指向棧頂后面的節點。

1、鏈式棧

/* 單鏈表實現堆棧，沒有長度限制 */ #include <stdio.h> #include <stdlib.h> #include <assert.h>#define STACK_TYPE int /* 堆棧所存儲的值的數據類型 */ #define FALSE 0/* 定義一個結構以存儲堆棧元素。 */ typedef struct STACK_NODE {STACK_TYPE value;struct STACK_NODE *next; }StackNode; /* 指向堆棧中第一個節點的指針 */ static StackNode *stack; /*棧元素個數*/ static int cnt;/* 創建對棧，參數指定對棧可以保存多少個元素 注意：此函數只適用于動態分配數組形式的堆棧。*/ void create_stack (size_t size);/*銷毀一個堆棧，釋放堆棧所適用的內存注意，此函數只適用于動態分配數組和鏈表結構的堆棧。*/ void destroy_stack (void);/* 將一個新值壓入堆棧中，參數是被壓入的值。*/ void push (STACK_TYPE value);/* 彈出堆棧中棧頂的一個值，并丟棄。*/ void pop (void);/* 返回堆棧頂部元素的值，但不改變堆棧結構。*/ STACK_TYPE top (void);/* 如果堆棧為空，返回TRUE,否則返回FALSE。*/ int is_empty (void);/* 如果堆棧為滿，返回TRUE,否則返回FALSE。*/ int is_full (void);/* 自定義函數實現遍歷操作 */ void travel (void);/* 計算棧中元素的個數 */ int size (void);int main (void) {travel (); pop (); printf("%s\n", is_empty() ? "棧為空" : "棧未空"); int i = 0; for (i = 0; i <= 9; i++) { push (i); } puts ("push 壓棧后的數值為: "); travel (); printf ("此時棧頂元素為：%d\n", top ()); printf ("此時棧元素個數為：%d\n", size ()); pop (); pop (); puts ("經過pop彈出幾個元素后的棧元素： "); travel (); printf("%s\n", is_full() ? "棧為滿" : "棧未滿"); printf("%s\n", is_empty() ? "棧為空" : "棧未空"); printf ("此時棧頂元素為：%d\n", top ()); printf ("此時棧元素個數為：%d\n", size ()); destroy_stack ();printf ("此時棧元素個數為：%d\n", size ()); return 0; } /* 不再需要create_stack 函數 */ void create_stack (size_t size) {}void destroy_stack (void) {printf ("銷毀堆棧\n");while (!is_empty ())pop (); /* 逐個彈出元素，逐個釋放節點內存 */ }void push (STACK_TYPE value) {StackNode *new_node;new_node = (StackNode *)malloc (sizeof (StackNode));if (NULL == new_node)perror ("malloc fail");new_node->value = value; new_node->next = stack; /* 新元素插入鏈表頭部 */ stack = new_node; /* stack 重新指向鏈表頭部 */ cnt++; }void pop (void) {StackNode *first_node;//assert (!is_empty ());if (is_empty ()) { printf ("棧已空，出棧失敗\n"); return ; } first_node = stack;stack = first_node->next;free (first_node);first_node = NULL;cnt--; }STACK_TYPE top (void) {//assert (!is_empty ());if (is_empty ()) { printf ("棧已空，出棧失敗\n"); return ; } return stack->value; }int is_empty (void) {return stack == NULL; }int is_full (void) {return FALSE; }void travel (void) {StackNode *p_node;p_node = stack;printf ("打印出鏈式堆棧里面的值：");if (NULL == p_node)printf ("堆棧為空\n");while (p_node != NULL){printf ("%d ", p_node->value);p_node = p_node->next;}printf ("\n"); }int size (void) {return cnt; } 輸出結果： 打印出鏈式堆棧里面的值：堆棧為空棧已空，出棧失敗 棧為空 push 壓棧后的數值為: 打印出鏈式堆棧里面的值：9 8 7 6 5 4 3 2 1 0 此時棧頂元素為：9 此時棧元素個數為：10 經過pop彈出幾個元素后的棧元素： 打印出鏈式堆棧里面的值：7 6 5 4 3 2 1 0 棧未滿 棧未空 此時棧頂元素為：7 此時棧元素個數為：8 銷毀堆棧 此時棧元素個數為：0

2、自寫鏈式棧

//基于鏈式存儲結構的堆棧實現 #include <stdio.h> #include <stdlib.h>typedef struct Node {int data; //存放的具體元素struct Node *next; //存放下一個節點地址 }Node;typedef struct {int cnt;Node *head; }Stack;//入棧操作 void push (Stack *ps, int data);//遍歷操作 void travel (Stack *ps);//出棧操作 int pop (Stack *ps);//查看棧頂元素 int top (Stack *ps);//判斷堆棧是否為空 int empty (Stack *ps);//判斷堆棧是否為滿 int full (Stack *ps);//查看堆棧元素個數 int size (Stack *ps);int main (void) {Stack stack;stack.head = 0;stack.cnt = 0;printf ("%s\n", empty (&stack)? "堆棧為空" : "堆棧未空");printf ("出棧元素是：%d\n", pop (&stack));printf ("堆棧中元素的個數為：%d\n", size (&stack));printf ("--------------------------\n");push (&stack, 11); //11push (&stack, 22); //22 11push (&stack, 33); //33 22 11push (&stack, 44); //44 33 22 11travel (&stack); //44 33 22 11printf ("出棧元素是：%d\n", pop (&stack));travel (&stack); //33 22 11printf ("--------------------------\n");printf ("棧頂元素為：%d\n", top (&stack));printf ("%s\n", full (&stack) ? "堆棧為滿" : "堆棧未滿");printf ("%s\n", empty (&stack)? "堆棧為空" : "堆棧未空");printf ("堆棧中元素的個數為：%d\n", size (&stack));return 0; }void push (Stack *ps, int data) {//創建新節點并初始化Node *pn = (Node *)malloc (sizeof (Node));pn->data = data;pn->next = NULL;//插入新節點pn->next = ps->head;ps->head = pn;ps->cnt++; }void travel (Stack *ps) {printf ("堆棧中的元素有：\n");Node *p = ps->head;//判斷堆棧為不為空while (p != NULL){printf ("%d ", p->data);//指向下一個節點p = p->next;}printf ("\n"); }int pop (Stack *ps) {//判斷為不為空if (NULL == ps->head)return ;//保存要刪除的節點地址Node *p = ps->head;//頭指針指向下一個節點ps->head = ps->head->next;ps->cnt--;//存儲要刪除的節點元素值int tmp = p->data; //釋放內存完畢后就沒有元素值了free (p); //釋放內存p = NULL; //置為空指針return tmp; }int top (Stack *ps) {//判斷堆棧是否為空if (empty (ps))return ;return ps->head->data; }int empty (Stack *ps) {return NULL == ps->head; }int full (Stack *ps) {return 0; }int size (Stack *ps) {return ps->cnt; } 輸出結果： 堆棧為空 出棧元素是：0 堆棧中元素的個數為：0 -------------------------- 堆棧中的元素有： 44 33 22 11 出棧元素是：44 堆棧中的元素有： 33 22 11 -------------------------- 棧頂元素為：33 堆棧未滿 堆棧未空 堆棧中元素的個數為：3

3、鏈式棧總結

（1）無需預分配 不需要預分配存儲空間，不需要記住堆棧容量，也不需要判斷堆棧是否滿，隨壓入隨分配，隨彈出隨釋放，提升內存空間利用率 （2）壓入彈出 被壓入的元素放在新建節點中，令其后指針指向棧頂節點，并令其成為新的棧頂節點，被彈出的元素由棧頂節點獲得，釋放棧頂節點，并令其后節點成為新的棧頂節點。 （3）判滿判空 棧頂指針為空表示堆棧已空，此時不可再彈出。

五、棧實現計算器

參看：棧實現計算器 1、自左向右掃描表達式，凡是遇到操作數一律進操作數棧。
2、當遇到運算符時，如果它的優先級比運算符棧棧頂元素的優先級高就進棧。反之，取出棧頂運算符和操作數棧頂 的兩個連續操作數運算，并將結果存入操作數棧，然后繼續比較該運算符與棧頂的運算符的優先級。 3、左括號一律進運算符棧，右括號一律不進運算符棧，取出棧頂運算符和操作數棧頂的兩個連續操作數運算，并將 結果存入操作數棧，直到取出左括號為止。 #include <stdio.h> #include <stdlib.h>#define MAX_SIZE 1024int operand[MAX_SIZE]; int top_num = -1;char oper[MAX_SIZE]; int top_oper = -1;//輸入數據，將數據壓入數據棧 void insert_operand (int value) {if (top_num == MAX_SIZE - 1)return ;top_num += 1;operand[top_num] = value; }//輸入操作符，將操作符壓入符號棧 void insert_oper (char ch) {if (top_oper == MAX_SIZE - 1)return ;top_oper += 1;oper[top_oper] = ch; }//比較操作符優先級 int compare (char ch) {//判斷當前優先級是否比棧頂操作符優先級高if ((oper[top_oper] == '-' || oper[top_oper] == '+') && (ch == '*' || ch == '/'))return 0; //判斷操作符是否為空，棧頂操作符是否為'(' else if (top_oper == -1 || ch == '(' || (oper[top_oper] == '(' && ch != ')'))return 0; //判斷括號內的表達式是否計算完畢 else if (oper[top_oper] == '(' && ch == ')'){top_oper--;return 1;}elsereturn -1; }//進行數據運算 void deal_date (void) {//取出數據棧中兩個數據int num1 = operand[top_num];int num2 = operand[top_num - 1];int value = 0;//進行加減乘除操作if (oper[top_oper] == '+')value = num1 + num2;else if (oper[top_oper] == '-')value = num2 -num1;else if (oper[top_oper] == '*')value = num1 * num2;else if (oper[top_oper] == '/')value = num2 / num1;//將數據棧頂下移一位，然后將得到的值壓入數據棧，將操作符棧頂下移一位top_num--;operand[top_num] = value;top_oper--; }int main (void) {char ch;int i = 0;int num = 0;char *temp;char dest[MAX_SIZE];char *str = (char*)malloc (sizeof (char) * MAX_SIZE);scanf ("%s", str);while (*str != '\0') {temp = dest;while (*str >= '0' && *str <= '9') //判斷是否為數據，遇到符號退出*(temp++) = *(str++);if (*str != '(' && *(temp - 1) != '\0') //判斷是否為符號'('{*temp = '\0';num = atoi (dest); //將字符串轉為數字insert_operand (num); }while (1){i = compare (*str); //判斷操作符優先級if (i == 0) //壓入操作符{insert_oper (*str);break;}else if (i == 1) //判斷括號內表達式是否結束str++;else if (i == -1) //進行數據處理deal_date ();}str++; //指向表達式下一個字符}printf ("num = %d\n", operand[0]);return 0; } 輸出結果： 1+2*(1+2)-2+(6/2) num = 8

六、逆波蘭式計算器

參看：逆波蘭算數表達式
擴展：波蘭式、逆波蘭式與表達式求值 傳統的算術表達式是由操作數（又叫運算對象或運算量）和運算符以及改變運算次序的圓括號鏈接而成的式子。其運算規則如下： （1）先計算括號內，后計算括號外 （2）在無括號或同層括號內，先進行乘除運算，后進行加減運算，即乘除運算的優先級高于加減運算的優先級 （3）同一優先級運算，從左向右依次進行 在這種表達式的計算過程中，既要考慮括號的作用，又要考慮運算符的優先級，還要考慮運算符出現的先后次序。 波蘭科學家盧卡謝維奇(Lukasiewicz)提出了算術表達式的另一種表示，即后綴表示，又稱逆波蘭式，其定義是把運算符放在兩個運算對象的后面。在后綴表達式中，不存在括號，也不存在優先級的差別，計算過程完全按照運算符出現的先后次序進行，整個計算過程僅需一遍掃描便可完成。例如：
3/5+6的逆波蘭表達式為3 5 / 6 +
2*(3+4)的逆波蘭表達式為2 3 4 + * #include <stdio.h> #include <string.h> int tranfer(char *s) { int k=1,result=0,len = strlen(s); while(len--) { result += (s[len]-'0')*k; k *= 10; } return result; } main( ) { char s[50]; int j=0,num[100]; while((scanf("%s",s))!=EOF) { if(s[0]>='0'&&s[0]<='9') num[j++] = tranfer(s); else { switch(s[0]){ case '+': num[j-2] += num[j-1]; j--; break; case '-': num[j-2] -= num[j-1]; j--; break; case '*': num[j-2] *= num[j-1]; j--; break; case '/': num[j-2] /= num[j-1]; j--; break; } } } printf("%d\n",num[0]); } 輸出結果： 2 3 + 5 * （按 CTRL + D 結束） num = 25

總結

以上是生活随笔為你收集整理的数据结构与算法 -- 栈 ADT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。