Bear Duen

Stack的概念

想像有一個容器，我們依序放入東西進去，當要拿出東西時，一定是先取出最後放進去的那樣東西。

此即為先進後出之概念 ->  first in last out  FILO 

函式介紹

push()：將元素放入stack中。

pop()：將最上面的元素取出。有時候我們可以依需要，回傳最上面的值再將其取出。

isEmpty()：判斷stack是否為空。

isFull()：判斷stack是否為滿。

print()：列印出stack裡的所有元素，從下而上。(也可由上而下，視需要)

top：表示最上面元素之索引位置。

函式實作

陣列：利用陣列實作時，一定要宣告stack之容量(不然也無法malloc)，也就是top的最大值(   maxTop   )。.陣列的第一個位置存放最先放入的元素。

#include <stdio.h>
#include <stdlib.h>

typedef struct stack{
    int top;
    int maxTop;
    int *data;
}stack_t;

void create_stack(stack_t *st, int size){
    st->top=-1;
    st->maxTop=size-1;
    st->data=(int *)malloc(sizeof(int)*size);
}

int isEmpty(stack_t *st){
    if (st->top == -1)
        return 1;
    return 0;
}

int isFull(stack_t *st){
    if (st->top == st->maxTop)
        return 1;
    return 0;
}

void push(stack_t *st, int num){
    if (isFull(st) == 1)
        printf("The stack is full.\n");
    else
        st->data[++st->top]=num;
}

int pop(stack_t *st){
    if (isEmpty(st) == 1)
        printf("The stack is empty.\n");
    else
        return (st->data[st->top--]);
}

void print(stack_t *st){
    if (isEmpty(st) == 1)
        printf("The stack is empty.\n");
    else{
        int i;
        for (i=0; i<=st->top; i++)
            printf("%d ", st->data[i]);
        printf("\n");
    }
}

int main(){
    stack_t *s=(stack_t *)malloc(sizeof(stack_t));

    printf("Create a stack which size is 5.\n");
    create_stack(s, 5);
    printf("Push:1,2,3,4,5:\n");
    push(s, 1);
    push(s, 2);
    push(s, 3);
    push(s, 4);
    push(s, 5);
    print(s);
    printf("First time pop, the top is %d:\n", pop(s));
    print(s);
    printf("Second time pop, the top is %d:\n", pop(s));
    print(s);
    return 0;
}

鏈結串列：不須宣告 stack 大小。head 永遠指向 stack 最上方。

#include <stdio.h>
#include <stdlib.h>

typedef struct stack{
    int data;
    struct stack *next;
}stack_t;
stack_t *head;

void create_stack(){
    head=NULL;
}

int isEmpty(){
    if (head == NULL)
        return 1;
    return 0;
}

void push(int num){
    stack_t *new_node=(stack_t *)malloc(sizeof(stack_t));
    new_node->data=num;
    new_node->next=NULL;

    if (isEmpty() == 1)
        head=new_node;
    else{
        new_node->next=head;
        head=new_node;
    }
}

int pop(){
    if (isEmpty() == 1)
        printf("The stack is empty.\n");
    else{
        stack_t *temp=head;
        head=head->next;
        return temp->data;
    }
}

void print(){
    if (isEmpty() == 1)
        printf("The stack is empty.\n");
    else{
        stack_t *curr=head;
        while (curr != NULL){
            printf("%d ", curr->data);
            curr=curr->next;
        }
        printf("\n");
    }
}

int main(){
    head=(stack_t *)malloc(sizeof(stack_t));
    printf("Create a stack which size is 5.\n");
    create_stack();
    printf("Push:1,2,3,4,5:\n");
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    print();
    printf("First time pop, the top is %d:\n", pop());
    print();
    printf("Second time pop, the top is %d:\n", pop());
    print();
    return 0;
}
 

執行結果

Create a stack which size is 5.
Push:1,2,3,4,5:
1 2 3 4 5
First time pop, the top is 5:
1 2 3 4
Second time pop, the top is 4:
1 2 3