在線性表中，順序表和鏈表可以訪問任意位置結(jié)點，在任意位置插入和刪除結(jié)點。棧和隊列是對上述操作加以限制。
- 在線性表的一端插入、刪除、訪問結(jié)點。
- 在線性表的一端插入結(jié)點、另一端刪除、訪問結(jié)點。
1. 棧是什么？
棧是一種只能從表的一端存取數(shù)據(jù)且遵循 LIFO(先進(jìn)后出)原則的線性存儲結(jié)構(gòu)。
棧的開口端被稱為棧頂
封口端被稱為棧底。
通常只會對棧執(zhí)行以下兩種操作：
- 向棧中添加元素，此過程被稱為"進(jìn)棧"（入?；驂簵＃?/li>
- 從棧中提取出指定元素，此過程被稱為"出棧"（或彈棧）；
2. 棧怎么用？
棧一般用來處理逆序和回退相關(guān)的處理。
3. 棧怎么實現(xiàn)？
棧是操作受限制的線性表，根據(jù)不同的存儲結(jié)構(gòu)可分成順序棧和鏈?zhǔn)綏！?/p>
- 在順序棧中，可以將順序表的有效長度作為棧頂指針，在順序表的末尾刪除和插入節(jié)點。
- 在鏈?zhǔn)綏Ｖ校梢詫㈡湵淼念^結(jié)點作為棧頂指針，入棧采用頭插法。
下面是順序棧的實現(xiàn)。
3.1 定義結(jié)構(gòu)
typedef int StackType; //存儲單元類型
typedef struct stackNode {
StackType *element; //存儲空間基地址
int size; //當(dāng)前長度
int capacity; //當(dāng)前分配的存儲容量
}Stack;
3.2 定義操作
- 初始化棧
Stack stack_init(int size);
- 入棧
void stack_push(Stack* stack,StackType element);
3.訪問棧頂元素
StackType* stack_top(Stack* stack);
- 出棧
StackType stack_pop(Stack* stack);
4. 練習(xí)
- 把一個十進(jìn)制的數(shù)轉(zhuǎn)換為一個二進(jìn)制的數(shù)，例如9轉(zhuǎn)換為二進(jìn)制是1001，可以使用棧來實現(xiàn)。
- 完成括號匹配-百度2018秋
- 牛牛的括號匹配-京東2018秋
5. 作業(yè)
雙棧
