棧的概念及結(jié)構(gòu)

棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端
稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

棧的定義

typedef int STDataType;
typedef struct Stack
{STDataType* _a;//數(shù)組int _top; // 棧頂,類似順序表中的_sizeint _capacity; // 容量
}Stack;

對(duì)棧的操作

棧初始化

_top可以初始化為0，此時(shí)棧頂元素是_top-1的位置

_top也可以初始化為1，此時(shí)棧頂元素就是_top的位置

初始化為0

? ? ??初始化為1

// 初始化棧
void StackInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_capacity = 0;ps->_top = 0;
}

壓棧（入棧）

// 入棧
void StackPush(Stack* ps, STDataType data)
{assert(ps);//擴(kuò)容if (ps->_capacity == ps->_top){int newcapacity = ps->_capacity == 0 ? 4 : 2 * (ps->_capacity);STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}ps->_a = tmp;ps->_capacity = newcapacity;}ps->_a[ps->_top++] = data;
}

出棧

void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->_top--;
}

取棧頂元素

STDataType StackTop(Stack* ps)
{assert(ps);return ps->_a[ps->_top-1];
}

判斷棧是否為空

bool StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;
}

棧的長(zhǎng)度

_top初始化為0，此時(shí)的_top的大小剛好就是棧的長(zhǎng)度

int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}

棧銷毀

void StackDestroy(Stack* ps)
{assert(ps);ps->_capacity = ps->_top = 0;free(ps->_a);ps->_a = NULL;
}

完整總代碼

頭文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
// 支持動(dòng)態(tài)增長(zhǎng)的棧
typedef int STDataType;
typedef struct Stack
{STDataType* _a;//數(shù)組int _top; // 棧頂,類似順序表中的_sizeint _capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(Stack* ps);
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);

函數(shù)定義

#include"Stack.h"
// 初始化棧
void StackInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_capacity = 0;ps->_top = 0;
}
// 入棧
void StackPush(Stack* ps, STDataType data)
{assert(ps);//擴(kuò)容if (ps->_capacity == ps->_top){int newcapacity = ps->_capacity == 0 ? 4 : 2 * (ps->_capacity);STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}ps->_a = tmp;ps->_capacity = newcapacity;}ps->_a[ps->_top++] = data;
}
// 出棧
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->_top--;
}
// 獲取棧頂元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps->_a[ps->_top-1];
}
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;
}
// 銷毀棧
void StackDestroy(Stack* ps)
{assert(ps);ps->_capacity = ps->_top = 0;free(ps->_a);ps->_a = NULL;
}

測(cè)試

#include"Stack.h"
void test()
{Stack s;StackInit(&s);StackPush(&s, 1);StackPush(&s, 2);StackPush(&s, 3);StackPush(&s, 4);while (StackSize(&s)>0){printf("%d ", StackTop(&s));StackPop(&s);}StackDestroy(&s);
}
int main()
{test();return 0;
}

歡迎各位一起學(xué)習(xí)交流~