Monday, December 26, 2011

Stack Using Link List

最近同學在學習 link list,使用C語言中的 structure 做堆疊(stack) ,所以我也練習了一次。

堆疊如同字面上的意思,將東西一層一層「疊」上去,故最後進來的東西,會放在最上面,即是LIFO(last in, first out)。

堆疊最常見的幾個操作有:

  • push:將東西放入。
  • pop:將東西取出。
  • display:顯示堆疊中的所有東西。
程式中有一個 struct node *top,這個指標會一直指向堆疊中最頂層的node。於是乎,實作push, pop, display的方法是:

  • push:將新進來的資料存到一個新的node(在此稱temp)裡面,再將這個node的下一個node指標指向top(temp->next = top),最後將top指向這新的node(即top = temp)。
  • pop:將top裡的數據印出,透過top = top->next的方式刪除掉最上層的node。
  • display:定義一個新指標指向top,然後讀取該node裡面的數據,之後再將自己指向next,再讀取數據,不斷循環至該指標為NULL(沒有指向任何node)為止。

    #include 
    #include 
    
    #define PUSH 1
    #define POP 2
    #define LIST 3
    #define EXIT 4
    
    struct node
    {
     int data;
     struct node *next;
    };
    
    struct node *top = NULL;
    
    /*
     * Functions Declarations
     */
    static void push(int num);
    static void pop();
    static void display();
    
    int main(void)
    {
    
     while(1)
     {
    
      int sel;
      printf("[Stack]\t(1)push\t(2)pop\t(3)display >> ");
      if(scanf("%d",&sel)==EOF) break;
    
      int temp;
      switch(sel)
      {
       case PUSH:
        printf("push >> ");
        scanf("%d",&temp);
        push(temp);
        break;
    
       case POP:
        pop();
        break;
    
       case LIST:
        display();
        break;
    
       default:
        printf("Wrong Selection.\n");
    
      }
    
     }
    
    
     //end
     printf("Exit Program.\n");
    
     return 0;
    }
    
    /*
     * Function : push
     */
    static void push(int num){
    
     struct node *temp;
    
     temp = (struct node *)malloc(sizeof(struct node));
     temp->data = num;
     temp->next = top;
     top = temp;
    
    }
    
    /*
     * Function : pop
     */
    static void pop(){
    
     if(top!=NULL)
     {
      printf("pop : %d\n", top->data);
      top = top->next;
     }
     else
     {
      printf("Stack Bottom.\n");
     }
    
    }
    
    /*
     * Function : display
     * Display all the elements in the stack.
     */
    static void display(){
    
     struct node *ptr = top;
    
     while(ptr){
    
      printf("%d\n", ptr->data);
      ptr = ptr->next;
    
     }
    
    }
    
    //end