棧的操作實現

棧的概念

棧是一種後進先出（LIFO）的線性數據結構，只允許在一端（棧頂）進行插入和刪除操作。新元素總是添加到棧頂，而刪除也總是從棧頂移除最上面的元素。棧常用於函數調用、表達式求值、括號匹配等場景。

代碼實現---順序存儲（Array-based Stack）

#include <stdio.h>	// 標準輸入輸出庫，用於 printf 等函數
#include <stdbool.h>// 布爾類型庫，提供 bool、true、false
#include <stdlib.h> // 標準庫，提供 malloc/calloc/free 和 exit 等函數

// 定義棧元素的類型為 int
typedef int DataType_t; 

// 定義棧的元素結構體
typedef struct SequenceStack 
{
	DataType_t *Bottom;
	unsigned int Size;
	int 		 Top;
} SeqStack_t;

SeqStack_t* SeqStack_init(unsigned int size)
{
	//calloc 返回的是 void * 類型指針，可以隱式轉換為任何其他指針類型（如 int*、char*），所以強制類型轉換不是必須的
	SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));

	if(Manager == NULL){
		perror("calloc for Manager is failed!\n");
		exit(-1);
	}

	Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));
	
	if(Manager->Bottom == NULL){
		perror("calloc for stackEelement is failed\n");
		free(Manager);
		exit(-1);
	}

	Manager->Size = size; 
	Manager->Top = -1;//沒有元素，初始化為-1，新增一個元素後下標就可以等於0

	return Manager;
}
//判斷棧是不是滿
bool SeqStackIsfull(SeqStack_t *Manager)
{
	//假設stacksize是8，Top的值已經為7，則棧滿
	return (Manager->Top+1 == Manager->Size)?true:false;

}

//判斷棧是不是空
bool SeqStackIsEmpty(SeqStack_t *Manager)
{
	//Top初始值為-1，下次判斷依然是-1則棧是空
	return (Manager->Top == -1)?true:false;

}
//入棧
bool SeqStack_Push(SeqStack_t *Manager,DataType_t data)
{	
	//添加元素需要先判斷棧有沒有滿
	if(SeqStackIsfull(Manager)){
		printf("SeqStack is Full!\n");
		return false;
	}

	Manager->Bottom[++Manager->Top] = data;

	return true;

}
//出棧
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
	if (SeqStackIsEmpty(Manager)) {
    printf("SeqStack is Empty!\n");
    return; 
	}
	//棧頂元素出棧，Top-1
	DataType_t temp = Manager->Bottom[Manager->Top--];
	
	return temp; 

}
//遍歷棧
void SeqStack_Print(SeqStack_t *Manager)
{
	for(int i=0;i<= Manager->Top;i++){
		printf("Stack Element[%d] = %d\n",i,Manager->Bottom[i]);
	}
}


int main(int argc, char const *argv[])
{
    // 初始化大小為 4 的棧
    SeqStack_t *stack = SeqStack_init(4);

    // 測試空棧出棧
    printf("嘗試從空棧出棧:\n");
    SeqStack_Pop(stack);

    // 入棧測試
    printf("入棧: 10, 20, 30\n");
    SeqStack_Push(stack, 10);
    SeqStack_Push(stack, 20);
    SeqStack_Push(stack, 30);

    // 打印棧
    printf("當前棧內容:\n");
    SeqStack_Print(stack);

    // 測試棧滿
    printf("繼續入棧: 40, 50\n");
    SeqStack_Push(stack, 40);
    SeqStack_Push(stack, 50);  // 應提示棧滿

    // 出棧兩次
    printf("出棧兩次:\n");
    printf("出棧元素: %d\n", SeqStack_Pop(stack));
    printf("出棧元素: %d\n", SeqStack_Pop(stack));

    // 再打印棧
    printf("出棧後內容:\n");
    SeqStack_Print(stack);

    return 0;
}

運行結果

代碼實現---鏈式存儲（Linked Stack）

/**
 * @fire name:Linkedstack.c
 * @brief:/**
 * @fire name:SeqList.c
 * @brief:這個程序實現棧的入棧、出棧（鏈式存儲）
 * @author:13642563766@163.com
 * @date:2025/7/18
 * @version:1.0
 *  @note:None
 * Copyright (c)  2021-2022  13642563766@163.com  All right Reserved
 */

#include <stdio.h>
#include <stdlib.h>
// 定義棧中存儲的數據類型為 int
typedef int DataType;

// 鏈棧的節點結構體：每個節點包含數據和指向下一個節點的指針
typedef struct StackNode {
	DataType	data;
	struct StackNode *next;
}StackNode;

// 鏈棧管理結構體：用於管理整個棧的狀態
typedef struct{
	int size;
	StackNode *top;// 指向棧頂節點的指針（NULL 表示空棧）
}LinkedStack;

// 為 LinkedStack* 定義別名 Stack，表示一個棧的指針
typedef LinkedStack* Stack;

/**
 * 初始化棧
 * @param s 指向棧指針的指針（二級指針），用於返回棧的地址
 * @return 成功返回 1，失敗返回 0
 */
int InitStack(Stack *s)
{
	*s = (Stack)malloc(sizeof(LinkedStack));
	if(*s == NULL){
		return 0;
	}
	(*s)->top = NULL;
	(*s)->size = 0;
	return 1;
}

/**
 * 入棧操作：將一個新元素壓入棧頂
 * @param s 棧指針
 * @param data 要入棧的數據
 * @return 成功返回 1，失敗返回 0
 */
int Push(Stack s, DataType data) 
{
	if (s == NULL) {
        return 0; // 指針無效
    }

    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        return 0; // 指針無效
    }
    // 設置新節點的數據和指針
    newNode->next = s->top;/
    newNode->data = data;
    s->top = newNode;//更新top指向新結點
    s->size++;//每入棧一個元素size++
    return 1;
}

/**
 * 出棧操作：彈出棧頂元素，並通過指針返回其值
 * @param s 棧指針
 * @param data 用於接收出棧元素值的輸出參數
 * @return 成功返回 1，棧為空或指針無效返回 0
 */
int Pop(Stack s, DataType *data)
{
	if(s == NULL || s->top == NULL){
		return 0; // 棧為空或棧指針無效，無法出棧
	}
    // 保存當前棧頂節點，便於後續釋放
	StackNode *Temp = s->top;
    // 將棧頂指針移動到下一個節點
	s->top = s->top->next;
	*data = Temp->data;
	free(Temp);
	s->size--;
	return 1;
}

//獲得棧頂元素的值
int GetTop(Stack s, DataType *data)
{
	if(s == NULL || s->top == NULL){
		return 0; // 棧為空或棧指針無效
	}
	*data = s->top->data;
	return 1;
}

int IsEmpty(Stack s) 
{
	if(s == NULL){
		 return 1;
	}

	return(s->top == NULL);
}

/**
 * 銷燬整個棧，釋放所有內存
 * @param s 指向棧的指針的指針
 */
void DestroyStack(Stack *s) {
    if (s == NULL || *s == NULL) {
        return;
    }

    StackNode *current = (*s)->top;
    StackNode *next;
    // 逐個釋放節點
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    // 釋放棧結構本身
    free(*s);
    *s = NULL; // 防止野指針
}

int main() {
    Stack myStack;
    DataType value;

    // 1. 初始化棧
    if (!InitStack(&myStack)) {
        printf("初始化棧失敗！\n");
        return -1;
    }
    printf("棧初始化成功。\n");

    // 2. 入棧操作
    printf("入棧: 10, 20, 30\n");
    Push(myStack, 10);
    Push(myStack, 20);
    Push(myStack, 30);

    // 3. 查看棧頂元素
    if (GetTop(myStack, &value)) {
        printf("當前棧頂元素: %d\n", value);
    } else {
        printf("棧為空，無法獲取棧頂元素。\n");
    }

    // 4. 出棧操作
    printf("開始出棧:\n");
    while (!IsEmpty(myStack)) {
        if (Pop(myStack, &value)) {
            printf("彈出: %d\n", value);
        }
    }

    // 5. 再次嘗試出棧 (棧已空)
    if (Pop(myStack, &value)) {
        printf("彈出: %d\n", value);
    } else {
        printf("棧已空，無法彈出元素。\n");
    }

    // 6. 銷燬棧
    DestroyStack(&myStack);
    printf("棧已銷燬。\n");

    return 0;
}

運行結果