堆棧與隊列都是抽象的數(shù)據(jù)類型，注意堆和棧不是同一個概念，這里的堆棧指的是棧；棧是一種具有后進先出的數(shù)據(jù)結(jié)構(gòu)，又稱為后進先出的線性表，簡稱 LIFO（Last In First Out）結(jié)構(gòu)。

隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，又稱為先進先出的線性表，簡稱 FIFO（First In First Out）結(jié)構(gòu)。

下面用數(shù)組來模擬一下堆棧與隊列，用數(shù)組比較容易實現(xiàn)和理解，但是開辟的數(shù)組過大過小都不合適，當(dāng)然也可以使用鏈表來實現(xiàn)；

數(shù)組實現(xiàn)堆棧:

?

#include "stdio.h"


#define MAXSTACK 10     // 堆棧最大容量
int stack[MAXSTACK];    // 定義一個數(shù)組


int top = -1;           // 堆棧的頂部


// 判斷堆棧是否為空
int isEmpty(void)
{
    if( top == -1 ) return 1;
    else return 0;
}


// 入棧
int push(int data)
{
    if(top >= MAXSTACK-1)
    {
        // 堆棧已滿
        printf("full
");
        return 0;
    }
    else
    {
        stack[++top] = data;
        return 1;
    }
}


// 出棧
int pop(void)
{
    // 判斷堆棧是否有數(shù)據(jù)
    if(isEmpty())
    {
        return 0;
    }
    else
    {
        return stack[top--];
    }
}


int main()
{
    // 推入十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        push(i);
    }
    // 獲取十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        printf("stack[%d]:%d
", i, pop());
    }
    printf("--------------
");
    // 推入十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        push(i);
    }
    // 獲取十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        printf("stack[%d]:%d
", i, pop());
    }
    printf("--------------
");
    return 0;
}

?

結(jié)果如下：

數(shù)組實現(xiàn)隊列:

?

#include "stdio.h"
#define MAXSTACK 10  // 定義隊列的大小
int stack[MAXSTACK];    // 定義一個數(shù)組


int front = 0;  // 隊列的頭
int rear = -1;   // 隊列的尾


// 判斷隊列是否為空
int isEmpty(void)
{
    if( rear == -1 ){
        return 0;
    }else{
        return 1;
    }
}


// 添加數(shù)據(jù)
int push(int data)
{
    if(rear >= MAXSTACK-1){
        // 隊列已滿
        printf("full
");
        return 0;
    }else{
        stack[++rear] = data;
        return 1;
    }
}


// 獲取數(shù)據(jù)
int pop(void)
{
    // 判斷隊列是否有數(shù)據(jù)
    if( isEmpty() )
    {
        rear--;
        return stack[front++];
    }
    else{
        // 重置
        front = 0;
        return 0;
    }
}


int main()
{
    // 推入十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        push(i);
    }
    // 獲取十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        printf("stack[%d]:%d
", i, pop());
    }
    printf("--------------
");
    // 推入十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        push(i);
    }
    // 獲取十個數(shù)據(jù)
    for(int i=0; i<12; i++){
        printf("stack[%d]:%d
", i, pop());
    }
    printf("--------------
");
    return 0;
}

?

結(jié)果如下：

總結(jié):?堆棧和隊列獲取的數(shù)據(jù)是反過來的,?本質(zhì)就是改變數(shù)組下標(biāo)實現(xiàn),?并不會清除數(shù)組對應(yīng)數(shù)據(jù)數(shù)據(jù);

　　審核編輯：湯梓紅

?