stack-push & pop

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()便完成使命了。