??堆棧Stack 和 隊列Queue是兩種非常重要的數(shù)據(jù)結(jié)構(gòu)，兩者都是特殊的線性表：

• 對于堆棧，所有的插入和刪除（以至幾乎所有的存取）都是在表的同一端進行
• 對于隊列，所有的插入都是在表的一端進行，所有的刪除（以至幾乎所有的存?。┒际窃诒淼牧硪欢诉M行。

一、堆棧

1. 定義

??堆棧（簡稱棧）是一種操作受限的線性表，只允許在表的同一端進行插入和刪除操作，且這些操作是按后進先出的原則進行的。進行插入和刪除的一端被稱為棧頂，另一端被稱為棧底。當棧中無元素時稱其為空棧。根據(jù)上述定義，每次刪除（退棧）的總是最后插入（進棧）的元素。

??如圖所示的堆棧中，諸元素以a1，a2，a3，a4，a5的順序進棧，而退棧的次序則是a5，a4，a3，a2，a1。 也就是說，從棧中取走元素是按后進先出的原則進行的，因此棧又被稱作后進先出（Last in First Out）的線性表，簡稱為LIFO表。

2. 基本操作

• 堆棧是受限的線性表，其基本操作包括
  • push ( ) : 壓入一個元素（插入）；
  • pop ( ) : 彈出一個元素（刪除）；
  • peek ( ) : 存取棧頂元素值；
  • clear ( ) : 清空棧；
  • IsEmpty ( ) : 判斷棧是否為空；
• 同普通線性表一樣，堆棧也可以用順序存儲和鏈接存儲兩種方式來實現(xiàn)：

二、順序棧

??用順序存儲方式實現(xiàn)的堆棧稱為順序棧。

• 順序棧用數(shù)組存放棧元素，可方便地進行各種棧操作；
• 某一堆棧的規(guī)模指該堆棧最多能容納的元素個數(shù)；
• 存放堆棧的數(shù)組規(guī)模（或大?。?yīng)按堆棧的規(guī)模來確定：
  • 當堆棧中元素的個數(shù)達到堆棧規(guī)模（簡稱為棧滿）時，則無法再向堆棧插入元素，換言之此時的插入操作將產(chǎn)生上溢出。
• 如何確保既不上溢也不下溢？
  • 需要一個整型變量size來存放數(shù)組規(guī)模，以及一個整型變量top來存放棧頂元素在數(shù)組中的位置（下標）
    • 當棧為空時，top值為0
    • 每入棧（或出棧）一個元素，top值加1（或減1）
    • 當top等于size時，說明棧滿

0. 順序表

參考前文：順序表及其基本操作

1. 頭文件和常量

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

   #define MAX_SIZE 100

• 兩個頭文件
  • stdio.h用于輸入輸出操作
  • stdlib.h用于內(nèi)存分配和釋放
• 通過#define指令定義了一個常量MAX_SIZE，它表示棧的最大容量為100。

2. 棧結(jié)構(gòu)體

   typedef struct {
       int data[MAX_SIZE];
       int top;
   } Stack;

??使用結(jié)構(gòu)體定義了一個棧的數(shù)據(jù)結(jié)構(gòu)，data是一個整型數(shù)組，用于存儲棧中的元素，top表示棧頂?shù)乃饕?/p>

3. 棧的初始化

   void init(Stack* stack) {
       stack->top = -1;
   }

??初始化棧，將棧頂索引top置為-1，表示棧為空。

4. 判斷棧是否為空

   int isEmpty(Stack* stack) {
       return stack->top == -1;
   }

??判斷棧是否為空，如果棧頂索引top等于-1，表示棧為空，函數(shù)返回1；否則，返回0。

5. 判斷棧是否已滿

   int isFull(Stack* stack) {
       return stack->top == MAX_SIZE - 1;
   }

??isFull函數(shù)用于判斷棧是否已滿，如果棧頂索引top等于MAX_SIZE - 1，表示棧已滿，函數(shù)返回1；否則，返回0。

6. 入棧

   void push(Stack* stack, int value) {
       if (isFull(stack)) {
           printf("Stack is full. Cannot push element.\n");
           return;
       }
       stack->data[++stack->top] = value;
   }

??push函數(shù)用于將元素入棧，首先判斷棧是否已滿，如果已滿，則打印錯誤信息并返回；否則，將元素存儲在棧頂索引top的位置，并將棧頂索引加1。

7. 出棧

   int pop(Stack* stack) {
       if (isEmpty(stack)) {
           printf("Stack is empty. Cannot pop element.\n");
           return -1;
       }
       return stack->data[stack->top--];
   }

??pop函數(shù)用于將棧頂元素出棧，首先判斷棧是否為空，如果為空，則打印錯誤信息并返回-1；否則，返回棧頂元素的值，并將棧頂索引減1。

8. 查看棧頂元素

   int peek(Stack* stack) {
       if (isEmpty(stack)) {
           printf("Stack is empty. Cannot peek element.\n");
           return -1;
       }
       return stack->data[stack->top];
   }

??peek函數(shù)用于查看棧頂元素的值，首先判斷棧是否為空，如果為空，則打印錯誤信息并返回-1；否則，返回棧頂元素的值。

9. 清空棧

   void clear(Stack* stack) {
       stack->top = -1;
   }

??clear函數(shù)用于清空棧，將棧頂索引top置為-1，表示棧為空。

10. 主函數(shù)

int main() {
    Stack stack;
    init(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Top element: %d\n", peek(&stack));

    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));

    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");

    clear(&stack);

    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");

    return 0;
}

• 聲明一個Stack類型的變量stack，然后調(diào)用init函數(shù)對棧進行初始化。

• 使用push函數(shù)將元素10、20和30依次入棧。

• 使用peek函數(shù)查看棧頂元素的值。

• 使用pop函數(shù)將棧頂?shù)膬蓚€元素出棧。

• 使用isEmpty函數(shù)判斷棧是否為空。

• 調(diào)用clear函數(shù)清空棧。

• 再次使用isEmpty函數(shù)判斷棧是否為空。

文章來源地址http://www.zghlxwxcb.cn/news/detail-722378.html

11. 代碼整合

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void init(Stack* stack) {
    stack->top = -1;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full. Cannot push element.\n");
        return;
    }
    stack->data[++stack->top] = value;
}

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty. Cannot pop element.\n");
        return -1;
    }
    return stack->data[stack->top--];
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty. Cannot peek element.\n");
        return -1;
    }
    return stack->data[stack->top];
}

void clear(Stack* stack) {
    stack->top = -1;
}

int main() {
    Stack stack;
    init(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Top element: %d\n", peek(&stack));

    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));

    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");

    clear(&stack);

    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");

    return 0;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】線性表（六）堆棧：順序棧及其基本操作（初始化、判空、判滿、入棧、出棧、存取棧頂元素、清空棧）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！