C語(yǔ)言|堆棧與隊(duì)列

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

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

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

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

?

#include "stdio.h"


#define MAXSTACK 10     // 堆棧最大容量
int stack[MAXSTACK];    // 定義一個(gè)數(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()
{
    // 推入十個(gè)數(shù)據(jù)
    for(int i=0; i<12; i++){
        push(i);
    }
    // 獲取十個(gè)數(shù)據(jù)
    for(int i=0; i<12; i++){
        printf("stack[%d]:%d
", i, pop());
    }
    printf("--------------
");
    // 推入十個(gè)數(shù)據(jù)
    for(int i=0; i<12; i++){
        push(i);
    }
    // 獲取十個(gè)數(shù)據(jù)
    for(int i=0; i<12; i++){
        printf("stack[%d]:%d
", i, pop());
    }
    printf("--------------
");
    return 0;
}

?

結(jié)果如下：

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

?

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


int front = 0;  // 隊(duì)列的頭
int rear = -1;   // 隊(duì)列的尾


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


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


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


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

?

結(jié)果如下：

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

　　審核編輯：湯梓紅

?