資料結構 【棧與隊列】

 棧

棧滿足下列兩點：

1.棧隻能從表的一端存取資料，另一端是封閉的。

2.在棧中，無論是存資料還是取資料，都必須遵循"先進後出"的原則，即最先進棧的元素最後出棧。

總結：棧是一種隻能從表的一端存取資料且遵循 "先進後出" 原則的線性存儲結構。

如圖：棧存儲結構存儲 

{1,2,3,4}

 棧的順序表實作：

順序表就是采用數組+尾指針的方式，尾指針一直指向最後一個元素，這裡特殊的地方在于，棧為空時，尾指針指向-1.

#include <stdio.h>
#define Size 100

typedef struct stacktag
{
    int a[Size];
    int top;
}stack;
   
#入棧
int rush(int* a,int top,int elem){
    if(++top>=Size)
    {
        printf("棧已滿\n");
        return --top;
    }
    a[++top]=elem;
    printf("插入元素：%d\n",a[top]);
    return top;
}

#出棧
int pop(int * a,int top){
    if (top==-1) {
            printf("空棧");
            return -1;
        }
        printf("彈棧元素：%d\n",a[top]);
        top--;
        return top;

}


int main () {
    stack stack1;
    stack1.top = -1;
    printf("初始化成功\n");
    
    stack1.top = rush(stack1.a,stack1.top,1);
    
    stack1.top = rush(stack1.a,stack1.top,5);

    stack1.top = pop(stack1.a,stack1.top);
          
    return 0;
}      

初始化成功
插入元素：1
插入元素：5
彈棧元素：5
      

 棧的連結清單實作：

使用連結清單實作注意一點：

資料插入采用頭插法，資料每次彈出頭部的元素

#include <stdio.h>
#include<malloc.h>

//聲明連結清單節點類型
typedef struct LISTtag LISTtagNode;
struct    LISTtag{
    int value;
    LISTtagNode *next;
};
int size=0;


//建立連結清單
LISTtagNode * create(){
    LISTtagNode *head;
    head = (LISTtagNode*)malloc(sizeof(LISTtagNode));
    head->next =  NULL;
    return head;
}


//在連結清單頭新增節點
int push(LISTtagNode *head,int value){
    if(head == NULL){
        return -1;
    }
    //建立節點
    LISTtagNode *node;
    node = (LISTtagNode*)malloc(sizeof(LISTtagNode));
    //節點指派，此節點跟在頭節點後
    node->value = value;
    node->next = head->next;
    head->next = node;
    size++;
    return 1;
}


//列印連結清單
int PrindLinKList(LISTtagNode *head){
     if(head == NULL){
        return -1;
    }
    LISTtagNode *t = head;
    while (t->next != NULL) {
        t = t->next;
        printf("%d ", t->value);
    }
    return 1;
}


int pop(LISTtagNode *head){
    if(head ==NULL){
        return -1;
    }
    LISTtagNode *node;
    int index = 0;
    while(head->next!=NULL&&index<1){
        node = head->next;
        index++;
    }
    if(index == 1){
         printf("\n%d ",node->value);
        if(head->next->next != NULL){
            head->next = head->next->next;  
        }else{
            head->next =NULL;
        }
        free(node);
        size--;
        return 1;
    }  
    return -1;
}

int top(LISTtagNode *head){
    if(head ==NULL){
        return -1;
    }
    LISTtagNode *node;
    int index = 0;
    while(head->next!=NULL&&index<1){
        node = head->next;
        index++;
    }
    if(index == 1){
        printf("%d ",node->value);
        return 1;
    }
    return -1;
}

int empty(LISTtagNode *head){
    if(head ==NULL){
        return -1;
     }
    if(head->next!=NULL){
        return 0;
    }
    return 1;
}

int length(LISTtagNode *head){
    if(head ==NULL){
        return -1;
     }
    return size;
}

int main () {
    LISTtagNode *head = create();
    push(head,7);
    push(head,9);
    push(head,23);
    push(head,43);
    push(head,45);
    push(head,65);
    printf("\n正序列印連結清單：");
    PrindLinKList(head);
    printf("\n連結清單長度：%d",length(head));
    pop(head);
    printf("\n正序列印連結清單：");
    PrindLinKList(head);
    printf("\n連結清單長度：%d",length(head));
    return 0;
}      

隊列

隊列滿足下列兩點：

1.隊列從一端表存儲資料，從另一端是讀取資料。

2.資料的入隊和出隊遵循"先進先出"的原則；

總結：隊列是一種從表的一端存儲資料，從另一端讀取資料，滿足“先進先出”的資料結構。

隊列的實作：

#include <stdio.h>
#define max 5//表示順序表申請的空間大小
int enQueue(int *a,int front,int rear,int data){
    //添加判斷語句，如果rear超過max，則直接将其從a[0]重新開始存儲，如果rear+1和front重合，則表示數組已滿
    if ((rear+1)%max==front) {
        printf("空間已滿");
        return rear;
    }
    a[rear%max]=data;
    rear++;
    return rear;
}
int  deQueue(int *a,int front,int rear){
    //如果front==rear，表示隊列為空
    if(front==rear%max) {
        printf("隊列為空");
        return front;
    }
    printf("%d ",a[front]);
    //front不再直接 +1，而是+1後同max進行比較，如果=max，則直接跳轉到 a[0]
    front=(front+1)%max;
    return front;
}
int main() {
    int a[max];
    int front,rear;
    //設定隊頭指針和隊尾指針，當隊列中沒有元素時，隊頭和隊尾指向同一塊位址
    front=rear=0;
    //入隊
    rear=enQueue(a,front,rear, 1);
    rear=enQueue(a,front,rear, 2);
    rear=enQueue(a,front,rear, 3);
    rear=enQueue(a,front,rear, 4);
    //出隊
    front=deQueue(a, front, rear);
    //再入隊
    rear=enQueue(a,front,rear, 5);
    //再出隊
    front=deQueue(a, front, rear);
    //再入隊
    rear=enQueue(a,front,rear, 6);
    //再出隊
    front=deQueue(a, front, rear);
    front=deQueue(a, front, rear);
    front=deQueue(a, front, rear);
    front=deQueue(a, front, rear);
    return 0;
}      

1 2 3 4 5 6 　      

使用環形表實作順序隊列的方法需要注意的是，順序隊列在判斷數組是否已滿時，出現下面情況：

• 當隊列為空時，隊列的頭指針等于隊列的尾指針；
• 當數組滿員時，隊列的頭指針等于隊列的尾指針；