棧：
- 線性的集合。
- 后進先出（LIFO，last in first out）。
- 兩個指針：指向棧頂和棧底。棧頂指向最后進入且第一個出去的元素。棧底指向第一個進入且最后一個出去的元素。
- 兩個操作：入棧（往棧尾添加元素），出棧（從棧尾取出元素）。
- 可以使用鏈表實現，也可以使用數組實現。本文使用雙鏈表舉例。
入棧：往棧頂（棧尾部）添加元素。
（頭指針：指向第一個元素。尾指針：指向最后的元素。）
?
出棧：從棧頂（棧尾部）刪除元素。
（頭指針：指向第一個元素。尾指針：指向最后的元素。）
C語言實現（雙鏈表）：
創建節點（結構體數據類型），并創建具體節點實例的函數：
// 節點（結構體數據類型）
typedef struct Node
{int value; // 存儲數據為整數struct Node *next; // 指向下一個數據的指針struct Node *prev; // 指向上一個數據的指針
} LinkNode; // 別名LinkNode// 創建具體節點實例的函數
LinkNode * createNode(int data)
{LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode)); // 分配內存空間if(node == NULL){perror("Memory allocation failed");exit(-1);}node->value = data;node->prev = NULL;node->next = NULL;return node;
}本文將頭指針、尾指針和棧長度作為全局變量：
LinkNode *header = NULL; // 頭指針,指向第一個節點,初始化為NULL
LinkNode *tail = NULL; // 尾指針,指向最后節點,初始化為NULL
int length = 0; // 統計棧有多少元素,初始化為0入棧：
// 入棧（往棧頂即尾部添加數據）
void push(int data)
{LinkNode *node = createNode(data);if(length == 0) // 空棧，頭指針和尾指針都指向新節點{header = node;tail = node;length++;return ;}tail->next = node; // 原最后節點的下一個為新節點node->prev = tail; // 新節點的上一個為原最后節點tail = node; // 尾指針指向新節點，即新節點為最后節點 length++; // 每添加一個元素，length+1
}獲取棧頂元素：
int gettop(void)
{// 棧不為空，則棧頂元素為尾指針指向的最后節點的值if(length != 0) return tail->value;
}出棧：
int pop(void)
{if(length != 0){// 獲取最后節點的值int top = tail->value;// 通過最后節點的prev找到倒數第二個節點,其next指向NULL,則原倒數第二個節點為新的最后節點tail->prev->next = NULL;// 每刪除一個節點,length-1length--;// 返回原最后節點的值return top;}
}遍歷棧：
void travel(void)
{if(length == 0) return ;LinkNode *cur = header; // 從鏈表頭部開始遍歷，直到最后printf("stack elements:");while(cur != NULL){printf("%d \t", cur->value);cur = cur->next;}printf("\n");
}完整代碼：（stack.c）
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>/* structrue */
typedef struct Node // node structure
{int value;struct Node *next;struct Node *prev;
} LinkNode;/* global variables */
LinkNode *header = NULL; // the header pointer
LinkNode *tail = NULL; // the tailer pointer
int length = 0; // the number of the stack elements/* function prototype */
void push(int data); // add element to the end of the stack
int pop(void); // delete element from the end of the stack
int gettop(void); // show element at the end of the stack
void travel(void); // show element one by one/* main function */
int main(void)
{// cycle input a number until 'q' or non-numeric, add the number to the stackwhile(1) // 循環輸入數字,并入棧,輸入q退出輸入循環{int data = 0, c;printf("if quit,input 'q'. Input a number: ");c = getchar(); // 獲取輸入的一個字符if(tolower(c) == 'q') break; // 若輸入q,則退出輸入循環if(c < '0' || c > '9') break; // 輸入的不是數字,則退出輸入循環while(c != '\n') // 若整數為多位數,通過一位一位計算最終獲得多位整數{data *= 10;data += c - 48; // ASCII碼表中，0對應碼值48c = getchar();}push(data); // 入棧printf("length is %d \n", length); // 輸出棧元素個數travel(); // 遍歷棧}// when stack not empty,cycle look and delete the top element until input 'n'if(length == 0) exit(-1);char k;printf("if you want to look and delete the top element? (y/n) ");scanf(" %c", &k); // 獲取輸入的內容while(tolower(k) == 'y' && length != 0) // 循環輸入是否查看并刪除棧頂元素{printf("top element is %d \n", gettop()); // 輸出棧頂元素pop(); // 出棧printf("length is %d \n", length); // 輸出棧元素個數travel(); // 遍歷棧printf("if you want to look and delete the top element? (y/n) ");scanf(" %c", &k); // 獲取下一個輸入的內容}
}/* subfunction */
LinkNode * createNode(int data) // create a node
{LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));if(node == NULL){perror("Memory allocation failed");exit(-1);}node->value = data;node->prev = NULL;node->next = NULL;return node;
}void push(int data) // add element to the end of the stack
{LinkNode *node = createNode(data);if(length == 0){header = node;tail = node;length++;return ;}tail->next = node;node->prev = tail;tail = node;length++;
}int pop(void) // delete element from the end of the stack
{if(length != 0){int top = tail->value;tail->prev->next = NULL;length--;return top;}
}int gettop(void) // show element at the end of the stack
{if(length != 0) return tail->value;
}void travel(void) // show element one by one
{if(length == 0) return ;LinkNode *cur = header;printf("stack elements:");while(cur != NULL){printf("%d \t", cur->value);cur = cur->next;}printf("\n");
}?
編譯鏈接： gcc -o stack stack.c
執行可執行文件： ./stack
)
