俗話說得好，線性表（尤其是鏈表）是一切數據結構和算法的基礎，很多復雜甚至是高級的數據結構和算法，細節處，除去數學和計算機程序基礎的知識，大量的都在應用線性表。
一、棧
其實本質還是線性表：限定僅在表尾進行插入或刪除操作。 俗稱：後進先出 (LIFO=last in first out結構)，也可說是先進後出（FILO）。
同樣的，棧也分為順序和鏈式兩大類。其實和線性表大同小異，只不過限制在表尾進行操作的線性表的特殊表現形式。
1、順序棧：利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時附設指針 top 指示棧頂元素在順序棧中的位置，附設指針 base 指示棧底的位置。 同樣，應該采用可以動態增長存儲容量的結構。且注意，如果棧已經空了，再繼續出棧操作，則發生元素下溢，如果棧滿了，再繼續入棧操作，則發生元素上溢。棧底指針 base 初始為空，說明棧不存在，棧頂指針 top 初始指向 base，則說明棧空，元素入棧，則 top++，元素出棧，則 top--，故，棧頂指針指示的位置其實是棧頂元素的下一位（不是棧頂元素的位置）。
復制代碼
1 #ifndef _____ADT__
2 #define _____ADT__
3 #include <stdbool.h>
4 #include <stdio.h>
5 #include <stdlib.h>
6 #define STACK_SIZE 50
7 #define STACK_INCREMENT 10
8
9 typedef struct{
10 int stackSize;//棧容量
11 char *base;//棧底指針
12 char *top;//棧頂指針
13 } SqStack;
14
15 //初始化
16 //本質還是使用動態數組
17 void initStack(SqStack *s)
18 {
19 s->base = (char *)malloc(STACK_SIZE * sizeof(char));
20 //分配成功
21 if (s->base != NULL) {
22 //空棧
23 s->top = s->base;
24 s->stackSize = STACK_SIZE;
25 }
26 else
27 {
28 puts("分配失敗！");
29 }
30 }
31
32 //判空
33 bool isEmpty(SqStack s)
34 {
35 return s.top == s.base ? true : false;
36 }
37
38 //判滿
39 bool isFull(SqStack s)
40 {
41 return (s.top - s.base) >= STACK_SIZE ? true : false;
42 }
43
44 //求當前長度
45 int getLength(SqStack s)
46 {
47 int i = 0;
48 char *q = s.top;
49
50 while (q != s.base) {
51 q--;
52 i++;
53 }
54
55 return i;
56 }
57
58 //求棧頂元素
59 char getTop(SqStack s, char topElement)
60 {
61 if (isEmpty(s)) {
62 puts("棧空！");
63 }
64
65 topElement = *(s.top - 1);
66 return topElement;
67 }
68
69 //入棧
70 void push(SqStack *s, char topElement)
71 {
72 char *q = NULL;
73
74 if (isFull(*s)) {
75 q = (char *)realloc(s->base, STACK_INCREMENT * sizeof(char));
76
77 if (NULL == q) {
78 exit(0);
79 }
80
81 s->base = q;
82 s->stackSize = s->stackSize + STACK_INCREMENT;
83 }
84 //進棧
85 *s->top++ = topElement;
86 }
87
88 //出棧
89 void pop(SqStack *s, char *topElement)
90 {
91 if (isEmpty(*s)) {
92 exit(0);
93 }
94
95 s->top--;
96 *topElement = *s->top;
97 }
98
99 //遍歷
100 void traversal(SqStack s)
101 {
102 for (int i = 0; i < getLength(s); i++) {
103 printf("棧中元素遍歷：%c \n", s.base[i]);
104 }
105 }
106
107 //清空
108 void cleanStack(SqStack *s)
109 {
110 if (!isEmpty(*s)) {
111 s->top = s->base;
112 puts("棧已經清空！");
113 }
114 }
115
116 //銷毀
117 void destroyStack(SqStack *s)
118 {
119 if (s->base != NULL) {
120 free(s->base);
121 s->base = NULL;
122 s->top = NULL;
123 s->stackSize = 0;
124 puts("棧成功銷毀！");
125 }
126 }
127
128 #endif /* defined(_____ADT__) */
復制代碼
函數: void exit(int status); 所在頭文件：stdlib.h
功 能: 關閉所有文件，終止正在執行的進程。
exit(1)表示異常退出.這個1是返回給操作系統的。
exit(x)（x不為0）都表示異常退出
exit(0)表示正常退出
exit()的參數會被傳遞給一些操作系統，包括UNIX,Linux,和MS DOS，以供其他程序使用。
exit()和return的區別：
按照ANSI C，在最初調用的main()中使用return和exit()的效果相同。 但要注意這裡所說的是“最初調用”。如果main()在一個遞歸程序中，exit()仍然會終止程序；但return將控制權移交給遞歸的前一級，直到最初的那一級，此時return才會終止程序。
return和exit()的另一個區別在於，即使在除main()之外的函數中調用exit()，它也將終止程序。
_exit()與exit的區別：
頭文件不同：
exit:#include<stdlib.h>
_exit:#include<unistd.h>
_exit()函數:直接使進程停止運行,清除其使用的內存空間,並銷毀其在內核中的各種數據結構;
exit()函數則在這些基礎上作了一些包裝,在執行退出之前加了若干道工序。比如系統調用之前exit（）要檢查文件的打開情況,把文件緩沖區中的內容寫回文件。
復制代碼
1 #include "ADT.h"
2
3 int main(void) {
4 char temp = '0';
5 SqStack stack;
6 initStack(&stack);
7
8 printf("%d\n", getLength(stack));
9
10 push(&stack, 'b');
11 push(&stack, 'k');
12 push(&stack, 'y');
13
14 printf("%d\n", getLength(stack));
15 // 函數使用temp之前必須初始化
16 temp = getTop(stack, temp);
17 printf("%c\n", temp);
18
19 traversal(stack);
20
21 pop(&stack, &temp);
22 printf("%d\n", getLength(stack));
23
24 traversal(stack);
25
26 cleanStack(&stack);
27
28 destroyStack(&stack);
29
30 return 0;
31 }
復制代碼
測試結果：
0
3
y
棧中元素遍歷：b
棧中元素遍歷：k
棧中元素遍歷：y
2
棧中元素遍歷：b
棧中元素遍歷：k
棧已經清空！
棧成功銷毀！
Program ended with exit code: 0
順序棧的小結：
1）、盡量使用指向結構的指針做函數參數，這樣的操作比結構體變量作函數參數效率高，因為無需傳遞各個成員的值，只需傳遞一個結構的地址，且函數中的結構體成員並不占據新的內存單元，而與主調函數中的成員共享存儲單元。這種方式還可通過修改形參所指成員影響實參所對應的成員值。
2）、棧清空，一定是棧頂指向棧底，不可顛倒，否則析構出錯！
3）、再次注意二級指針和一級指針做函數參數的不同
4）、使用一個指針變量之前，必須初始化，不為指針分配內存，即指針沒有指向一塊合法的內存，那麼指針無法使用，強行運行出錯，這就是野指針的危害。類似其他類型變量都是如此，（這也是為什麼建議聲明變量的同時就立即初始化，哪怕是一個不相干的數值），就怕程序寫的復雜的話，一時忘記變量是否初始化，導致出錯。
5）、為什麼順序棧（包括順序表）在初始化函數的傳入參數裡不用二級指針傳參？
個人理解：
首先清楚函數傳參的類型，值傳遞，引用（c++）傳遞，和指針傳遞，且函數修改的是實參的一份拷貝，並不是直接去修改實參。
問題是，在之前的鏈表裡，定義結點結構（ Node）和指向結點的指針 p，有 struct Node *p；為了給結點分配內存，把這個指針（p本身占據一份內存空間，在棧區操作系統分配，但是 p 的指向是沒有初始化的）p 傳入初始化函數內，等於是傳入的指向結點Node的一個指針 p 的拷貝 _p，而這個拷貝 _p 本身（假設指針變量p自己在內存的地址是0x1111）和拷貝 _p 存儲的（指針 p指向的 內存區域）內容是不一樣的，此時給 拷貝 _p 使用malloc函數分配內存，看似是修改了 _p ，實際上是把 _p 指向的內存區域改變了， p 本身在內存的地址（0x1111）沒有被改變，故函數執行完畢，棧分配的內存被操作系統回收，然後參數返回給主調函數，那份拷貝 _p 還是以前傳入的那份拷貝 _p， 高矮胖瘦那是紋絲未動，故不會對實參起到修改的作用，完全類似值傳遞，在值傳遞，就是把實參的本身的值傳入函數，如果函數內部對其拷貝進行修改，其實傳入的參數本身並沒有被改變，雖然函數體內，他的值被修改了，但是一旦函數執行完，棧的內存被系統回收，修改就變得徒勞。
順序棧裡，一般是定義的整個表List結構，struct List p；變量p 就是一個實例化的棧結構，注意 p 已經分配了內存（主調函數 main ，操作系統在棧區給p分配），這和主調函數裡鏈表的指針 p 不一樣，鏈表的指針 p 在 main 函數，只是給指針本身分配了內存空間，但是對 其指向的表結點沒有分配，需要在初始化函數初始化！故到了順序棧裡，當給函數傳入&p（因為開始main 已經給棧結構分配了內存空間，而&p 是棧結構 p 在內存的地址0x1111，也就是棧本身的首地址，也是 base指向的棧的基址），同樣是傳入一份拷貝 _&p ，且不是給 _&p malloc 內存，而是給 _&p 指向的內容分配空間—— (&p)->base（表的基地址）分配內存，也就是說，這裡堆 p 修改也是沒用的，但是對 p 的指向修改，也就是 base，是有用的。而 base 本身就是一個指針，p 其實和 base 值相等，只不過變量的類型不一樣，故不需要再傳入二級指針。
6）、初始化那裡，其實寫的不好，主調函數裡 s 分配了內存，如果沒有對這個結構體初始化，就不代表 s 的成員 base 或者 top 等就是有指向的，更別說 NULL 了。很大程度是指向是垃圾值，不確定的內存區域，故這裡的判斷
if (s->base != NULL)
在這個前提下，是沒有用處的語句。故還是聲明變量的同時，最好是初始化，哪怕是0或者 NULL。
2、鏈棧
其實就是鏈表的特殊情形，一個鏈表，帶頭結點，棧頂在表頭，插入和刪除（出棧和入棧）都在表頭進行，也就是頭插法建表和頭刪除元素的算法。顯然，鏈棧還是插入刪除的效率較高，且能共享存儲空間。
是棧頂在表頭！棧頂指針指向表頭結點。棧底是鏈表的尾部，base 就是尾指針。還有，理論上，鏈式結構沒有滿這一說，但是理論上是這樣的，也要結合具體的內存，操作系統等環境因素。
復制代碼
1 #ifndef _____ADT__
2 #define _____ADT__
3 #include <stdbool.h>
4 #include <stdio.h>
5 #include <stdlib.h>
6
7 typedef struct Node{
8 char data;
9 struct Node *next; //next 指針
10 } Node, *ListStack;
11
12 //初始化頭結點，top 指針指向頭結點
13 void initStack(ListStack *top)
14 {
15 //top就是頭指針！也就是棧頂指針
16 *top = (ListStack)malloc(sizeof(Node));
17 //就一個結點，也就是空棧，其實和鏈表一樣，沒啥意思
18 (*top)->next = NULL;
19 //內容初始化
20 (*top)->data = '0';
21 }
22
23 //判空
24 bool isEmpty(ListStack top)
25 {
26 //棧頂指針的next==NULL 就是空棧，沒有滿的判斷，但是也要悠著點。小心內存受不了。
27 return top->next == NULL ? true : false;
28 }
29
30 //入棧
31 void push(ListStack top, char topElement)
32 {
33 ListStack q = NULL;
34 q = (ListStack)malloc(sizeof(Node));
35
36 if (NULL == q) {
37 exit(0);
38 }
39 //類似頭插法建表，進棧
40 q->next = top->next;
41 top->next = q;
42 //賦值
43 top->data = topElement;
44 //棧底永遠是表尾指針
45 }
46
47 //出棧
48 void pop(ListStack top, char *topElement)
49 {
50 ListStack p = NULL;
51
52 if (isEmpty(top)) {
53 exit(0);
54 }
55 //棧頂元素出棧，記住，棧頂指針永遠是指向棧頂元素的下一位，p 指向棧頂元素
56 p = top->next;
57 *topElement = p->data;
58 //刪除這個元素
59 top->next = p->next;
60 free(p);
61 }
62
63 //求當前長度
64 int getLength(ListStack top)
65 {
66 int i = 0;
67 ListStack q = top->next;
68
69 while (q != NULL) {
70 i++;
71 q = q->next;
72 }
73
74 return i;
75 }
76
77 //求棧頂元素
78 char getTop(ListStack top, char topElement)
79 {
80 if (isEmpty(top)) {
81 puts("棧空！");
82 }
83
84 topElement = top->next->data;
85 return topElement;
86 }
87
88 //遍歷
89 void traversal(ListStack top)
90 {
91 ListStack p = top->next;
92
93 for (int i = 0; i < getLength(top); i++) {
94 printf("棧中元素遍歷：%c \n", p->data);
95 p = p->next;
96 }
97 }
98
99 //銷毀
100 void destroyLinkStack(ListStack *top)
101 {
102 ListStack p = *top;
103 ListStack pn = (*top)->next;
104
105 while (pn != NULL)
106 {
107 free(p);
108 p = pn;
109 pn = pn->next;
110 }
111 //銷毀最後一個
112 free(p);
113 p = NULL;
114 puts("棧成功銷毀！");
115 }
116
117 #endif /* defined(_____ADT__) */
復制代碼
main 函數
復制代碼
1 #include "ADT.h"
2
3 int main(void) {
4 ListStack stack = NULL;
5 initStack(&stack);
6
7 printf("棧長度 = %d\n", getLength(stack));
8
9 push(stack, 'a');
10 push(stack, 'b');
11 push(stack, 'c');
12 push(stack, 'd');
13
14 printf("棧長度 = %d\n", getLength(stack));
15
16 traversal(stack);
17
18 char temp = '0';
19 printf("棧頂元素 = %c\n", getTop(stack, temp));
20 pop(stack, &temp);
21
22 printf("棧長度 = %d\n",getLength(stack));
23
24 traversal(stack);
25
26 destroyLinkStack(&stack);
27
28 return 0;
29 }
復制代碼
其實鏈棧和鏈表是一樣的，沒什麼新鮮的東西。可見，線性表，尤其是鏈表，是數據結構和算法裡的重中之重，後續很多復雜高級的數據結構和算法，都會無數次的用到鏈表的相關知識和概念。
