目錄
一.棧的概念及結(jié)構(gòu)
二.棧的實(shí)現(xiàn)（c語言版）
2.1靜態(tài)增長的棧
2.2動(dòng)態(tài)增長的棧
2.3動(dòng)態(tài)棧的模擬實(shí)現(xiàn)
? ?1.棧的初始化
? 2.入棧
?3.出棧
4.獲取棧頂元素
5.獲取棧中有效數(shù)據(jù)個(gè)數(shù)
6.檢查棧是否為空
7.棧的銷毀
三.C++ 版本模擬實(shí)現(xiàn)棧
?1.C++版本的源代碼
四.c語言版本的源代碼
? 4.1? 頭文件.h源碼
? 4.2?功能實(shí)現(xiàn)的.c文件
4.3測試代碼test.c文件
一.棧的概念及結(jié)構(gòu)
棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂
二.棧的實(shí)現(xiàn)（c語言版）
棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小
2.1靜態(tài)增長的棧
下面是定長的靜態(tài)棧的結(jié)構(gòu)，棧的內(nèi)存空間是固定的，當(dāng)我們棧中的數(shù)據(jù)很少時(shí)，可能會(huì)浪費(fèi)空間，而數(shù)據(jù)量很大的時(shí)候，棧有可能占不下大量的數(shù)據(jù)，所以，在實(shí)際中一般不實(shí)用。
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 棧頂
}Stack;2.2動(dòng)態(tài)增長的棧
下面是動(dòng)態(tài)增長的棧，初始化的時(shí)候可以先給_a一個(gè)固定的小值，如何根據(jù)用戶輸入的數(shù)據(jù)自我進(jìn)行擴(kuò)容
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 棧頂
int _capacity; // 容量
}Stack;2.3動(dòng)態(tài)棧的模擬實(shí)現(xiàn)
? ?1.棧的初始化
? 在這里我對(duì)“?！钡娜萘拷o予5，然后用malloc去堆上創(chuàng)建5個(gè)int字節(jié)大小的空間付給我們的數(shù)組，因?yàn)閙alloc有可能申請(qǐng)失敗，所以我們用if去進(jìn)行判斷。
? top棧頂初始化為0，代表沒有數(shù)據(jù)。
void StackInit(Stack* ps)
{
?? ?ps->capacity = 5;
?? ?ps->a = (Stack*)malloc(ps->capacity * sizeof(STDataType));
?? ?if (ps->a == NULL)
?? ?{
?? ??? ?perror("malloc");
?? ??? ?exit(-1);
?? ?}
?? ?ps->top = 0;
}? 2.入棧
入棧，棧里面插入數(shù)據(jù)，相當(dāng)于數(shù)組進(jìn)行尾插
首先，進(jìn)行判斷，top棧頂?shù)扔赾apacity容量的時(shí)候，代表我們棧里的內(nèi)存滿了，這里我們需要擴(kuò)容，用realloc對(duì)數(shù)組進(jìn)行擴(kuò)容，現(xiàn)在我進(jìn)行的二倍擴(kuò)容
判斷完成后 進(jìn)行插入數(shù)據(jù)，在數(shù)組棧頂插入傳入的數(shù)據(jù) data
void StackPush(Stack* ps, STDataType data)
{
//擴(kuò)容
if (ps->top == ps->capacity)
{
Stack * da = (Stack*)realloc( ps->a ,ps->capacity * 2 * sizeof(STDataType));
if (da == NULL)
{
perror("realloc");
exit(-1);
}
else
{
ps->a = da;
}
ps->capacity *= 2;
}
ps->a[ps->top] = data;
ps->top++;
}?3.出棧
出棧,直接棧頂元素減一就好了，以后插入的數(shù)據(jù)會(huì)直接替換原先的數(shù)據(jù)，而top--后自己也訪問不到top以后的數(shù)據(jù)
void StackPop(Stack* ps)
{
ps->top--;
}4.獲取棧頂元素
獲取棧頂元素，因?yàn)閿?shù)組下標(biāo)是從0開始的，所以返回的是棧頂元素-1；
STDataType StackTop(Stack* ps)
{
return ps->a[ps->top-1];
}5.獲取棧中有效數(shù)據(jù)個(gè)數(shù)
有效的數(shù)據(jù)個(gè)數(shù)就是 棧頂，直接返回棧頂就好了
int StackSize(Stack* ps)
{
return ps->top;
}
6.檢查棧是否為空
c語言并不支持bool，需要我們引用頭文件#include<stdbool.h>
判斷棧頂是否為0，來判斷棧里是否有數(shù)據(jù)
有返回true
無返回false
bool StackEmpty(Stack* ps)
{
if (ps->top == 0)
return true;
else
return false;
}7.棧的銷毀
棧的銷毀，對(duì)容量和棧頂進(jìn)行請(qǐng)0，然后用free函數(shù)釋放我們使用malloc/realloc在堆上開辟的空間
void StackDestroy(Stack* ps)
{
ps->capacity = 0;
ps->top = 0;
free(ps->a);
ps->a = NULL;
}
以上就是c語言版本的棧的模擬實(shí)現(xiàn)文章來源：http://www.zghlxwxcb.cn/news/detail-719289.html
三.C++ 版本模擬實(shí)現(xiàn)棧
考慮到學(xué)校有好多老師上課，雖然說得是用c語言實(shí)現(xiàn)，卻用cpp進(jìn)行操作，現(xiàn)在給大家更新cpp版本的棧的模擬實(shí)現(xiàn)，cpp版本的擴(kuò)容使用的new，函數(shù)參數(shù)使用的&，可能有同學(xué)對(duì)指針使用不太熟悉，所以我們同意用&（引用）來實(shí)現(xiàn)，方便大家的理解，就不再詳細(xì)的進(jìn)行說明了，思路跟c語言實(shí)現(xiàn)的一樣，只是c和cpp的語言差距有所不同。文章來源地址http://www.zghlxwxcb.cn/news/detail-719289.html
?1.C++版本的源代碼
#include<iostream>
using namespace std;
// 支持動(dòng)態(tài)增長的棧
typedef int STDataType;
typedef struct Stack1
{
STDataType* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack& ps)
{
ps.capacity = 5;
ps.a = new STDataType[ps.capacity * sizeof(STDataType)];
ps.top = 0;
}
// 入棧
void StackPush(Stack& ps, STDataType data)
{
//擴(kuò)容
if (ps.top == ps.capacity)
{
STDataType* da = new STDataType[ps.capacity * 2 * sizeof(STDataType)];
ps.a = da;
ps.capacity *= 2;
}
ps.a[ps.top] = data;
ps.top++;
}
// 出棧
void StackPop(Stack& ps)
{
ps.top--;
}
// 獲取棧頂元素
STDataType StackTop(const Stack& ps)
{
return ps.a[ps.top - 1];
}
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(const Stack& ps)
{
return ps.top;
}
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool StackEmpty( const Stack& ps)
{
if (ps.top == 0)
return true;
else
return false;
}
// 銷毀棧
void StackDestroy(Stack& ps)
{
ps.capacity = 0;
ps.top = 0;
delete ps.a;
ps.a = NULL;
}
int main()
{
Stack s;
StackInit(s);
StackPush(s, 1);
StackPush(s, 2);
StackPush(s, 3);
StackPush(s, 4);
for (int i = 0;i < 4;i++)
{
cout << StackTop(s) << endl;
StackPop(s);
}
printf("棧中有效元素個(gè)數(shù)為 %d \n", StackSize(s));
if (StackEmpty(s))
{
printf("為空\n");
}
else
{
printf("不為空\n");
}
StackDestroy(s);
}四.c語言版本的源代碼
? 4.1? 頭文件.h源碼
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
// 支持動(dòng)態(tài)增長的棧
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 棧頂
int 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);
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);
? 4.2?功能實(shí)現(xiàn)的.c文件
#include"Stack.h"
// 初始化棧
void StackInit(Stack* ps)
{
assert(ps);
ps->capacity = 5;
ps->a = (Stack*)malloc(ps->capacity * sizeof(STDataType));
if (ps->a == NULL)
{
perror("malloc");
exit(-1);
}
ps->top = 0;
}
// 入棧
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//擴(kuò)容
if (ps->top == ps->capacity)
{
Stack * da = (Stack*)realloc( ps->a ,ps->capacity * 2 * sizeof(STDataType));
if (da == NULL)
{
perror("realloc");
exit(-1);
}
else
{
ps->a = da;
}
ps->capacity *= 2;
}
ps->a[ps->top] = data;
ps->top++;
}
// 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
// 獲取棧頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->a[ps->top-1];
}
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(Stack* ps)
{
return ps->top;
}
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool StackEmpty(Stack* ps)
{
if (ps->top == 0)
return true;
else
return false;
}
// 銷毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
ps->capacity = 0;
ps->top = 0;
free(ps->a);
ps->a = NULL;
}
4.3測試代碼test.c文件
#include"Stack.h"
int main()
{
Stack s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
StackPop(&s);
printf("棧頂元素為%d \n", StackTop(&s));
printf("棧中有效元素個(gè)數(shù)為 %d \n", StackSize(&s));
if (StackEmpty(&s))
{
printf("為空\n");
}
else
{
printf("不為空\n");
}
StackDestroy(&s);
}到了這里，關(guān)于帶你深入理解“?！保╟語言 c++和stl Stack三個(gè)版本的模擬實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
