typedef struct node {
int data;
struct node *next;
}node;
// TOP of a stack
node *top = NULL;
// push a value into a stack
void push(int val)
{
// allocate a new node for val
node *new_node =(node*) malloc(sizeof(node));
new_node->data = val;
new_node->next = top;
top = new_node;
}
// pop a value out from the stack
int pop(void)
{
// tmp for record the top node
node *tmp;
int return_value;
// if there is an existing data in stack
if (top != NULL) {
// get the value of the top
return_value = top->data;
// record the top node
tmp = top;
// change top
top = top->next;
free(tmp);
return return_value;
}
else
printf("no existing data in the stack!\n");
}
// show the stack
void show_stack(void)
{
node *rush = top;
printf("\nthe stack is:\n");
while (rush != NULL) {
printf("%d ", rush->data);
rush = rush->next;
}
puts("");
}
int main()
{
printf("Enter values:\n");
int n;
while (scanf("%d", &n) != EOF) {
push(n);
printf("%d ",n);
}
puts("");
show_stack();
pop();
show_stack();
pop();
show_stack();
return 0;
}
堆疊顧名思義就如同一疊一疊很重的貨物，擺放的時候當然是從下往上疊，拿的時候就從上面拿到下面。這是最順手的方式。這種資料的存取就稱為是Last In First Out。在底層的角度來說，compiler在處理function也是如此實做，詳情也可參考計算機組織結構。os會在記憶體之中規畫一個stack區域，專門記錄函式的返回位置。比如一個主程式位址從0~100。中間有個function A位於49，那麼在執行完這function A的時候就需要回到第50這個位置，但是有可能function內又有一個function，於是我們不僅要把50放入stack先做儲存，也必須把function A內另一個function返回位置也儲存下來。但是先後順序當然是越裡面的位置要先要拿出來返回，於是最後放入的(Last In)位置就當然是會優先返回(First Out)。這就是stack。
當然實做上不是只有使用stack來當作function的返回記錄，以現今高速處理的計算機而言，要每次去access記憶體也是需要花很多時間的，因此目前採用的做法都是直接放入暫存器內而不放在記憶體中。另一種方式就是把返回位址寫在程式內，也就是直接在一個function的結尾多上一個jp (addr)的指令，這種方式就不用堆疊了。
題外話不多說，基本上他和linked list是差不多的架構，唯一不同的就是連接起來的方式，新加入的資料永遠都會擺在頭的位置。
void push(int val)
{
// allocate a new node for val
node *new_node =(node*) malloc(sizeof(node));
new_node->data = val;
new_node->next = top;
top = new_node;
}
首先create資料位置並輸入資料之後，我們就把資料擺在top之上，最後重新指定top，這就是堆疊放入新資料的做法：top總是指向最後放入的資料。這個function的做法應該一目了然。相對於push是把資料疊放在top；pop採取的做法就是把top上的資料移下去，後進先出(LIFO)就是如此。
if (top != NULL){
...
}
else
printf("no existing data in the stack!\n");
首先我們要判斷目前是否有資料在stack內，判斷的方式很簡單，從top就可以看出是否有資料在內。如果沒有就印出訊息提醒。而判斷如果內有資料後，我們便需要把資料拿取出來：
return_value = top->data;
// record the top node
tmp = top;
// change top
top = top->next;
free(tmp);
return return_value;
因為top在取出資料需要往下移動，因此需要一個暫時的指標tmp來儲放原先top的位置用來最後free()的動作。因此return_value取出資料之後，隨即記錄top的位置，接著top往下移動之後在free掉原先top的位置(也就是tmp)。要注意的是順序要對，如果沒有把top的位置記錄起來而往下移動的話，那麼到時候必定是出trouble的。最後return結果pop()便完成使命了。
