C語言超詳細(xì)講解棧的實(shí)現(xiàn)及代碼
前言
棧的概念
- 棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。有點(diǎn)類似于手槍彈夾，后壓進(jìn)去的子彈總是最先打出，除非槍壞了。
- 壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧。（入數(shù)據(jù)在棧頂）
- 出棧：棧的刪除操作叫做出棧。（出數(shù)據(jù)也在棧頂）
注意：
1、函數(shù)調(diào)用也有棧，這兩個(gè)棧有區(qū)別嗎？
當(dāng)然有區(qū)別。函數(shù)調(diào)用會(huì)調(diào)用棧幀，內(nèi)存里頭也有一個(gè)棧，程序運(yùn)行起來時(shí)要執(zhí)行函數(shù)，函數(shù)里頭的局部變量、參數(shù)、返回值等等都要存在函數(shù)棧幀里頭。
這兩個(gè)棧沒有任何關(guān)聯(lián)，一個(gè)是數(shù)據(jù)結(jié)構(gòu)中的棧。另一個(gè)是操作系統(tǒng)中內(nèi)存劃分的一個(gè)區(qū)域，叫做棧，用來函數(shù)調(diào)用時(shí)，建立棧幀。雖然本質(zhì)上沒有任何關(guān)聯(lián)，但都符合后進(jìn)先出的規(guī)則。
2、假設(shè)入棧順序?yàn)椋? 2 3 4，那么出棧順序一定為：4 3 2 1 嗎？
當(dāng)然不是。雖說規(guī)則上明確后進(jìn)先出，可這是相對(duì)而言的，如果說它每進(jìn)一個(gè)再出一個(gè)，然后再繼續(xù)壓棧，那不同樣符合后進(jìn)先出的規(guī)則嗎。就如同上例，你說它出棧順序?yàn)? 2 3 4 都不足為奇，每進(jìn)一個(gè)出一個(gè)再進(jìn)，同樣符合規(guī)則。類似的入棧兩個(gè)再出再進(jìn)再出也是可以的，好比如2 1 4 3。
棧的結(jié)構(gòu)
棧的實(shí)現(xiàn)
創(chuàng)建棧結(jié)構(gòu)
Stack.h 文件：
//創(chuàng)建棧結(jié)構(gòu)
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存儲(chǔ)數(shù)據(jù)
int top; //棧頂?shù)奈恢?
int capacity; //容量
}ST;初始化棧
思想：
初始化還是相對(duì)比較簡(jiǎn)單的，學(xué)了之前的順序表，初始化棧就很輕松了
Stack.h 文件：
//初始化棧 void StackInit(ST* ps);
Stack.c 文件：
//初始化棧
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}注意：
???這里初始化的時(shí)候?qū)op置為0是有意圖的。首先，由上文創(chuàng)建棧結(jié)構(gòu)時(shí)已經(jīng)標(biāo)注了，top是用來記錄棧頂?shù)奈恢?，既然是棧頂?shù)奈恢?，那?dāng)top初始化為0時(shí)，我們可以直接將數(shù)據(jù)放入棧中，隨后top++，但是當(dāng)top初始化為-1時(shí)，top首先要++才能放入數(shù)據(jù)，因?yàn)閿?shù)據(jù)不可能在負(fù)數(shù)不屬于棧的位置上放入。下圖演示過程：
本文以 top = 0 示例
銷毀棧
思想：
動(dòng)態(tài)開辟的內(nèi)存空間一定要釋放，free置空即可，并把其余數(shù)據(jù)置0。
Stack.h 文件：
//銷毀棧 void StackDestory(ST* ps);
Stack.c 文件：
//銷毀棧
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}入棧
思路：
前文已經(jīng)強(qiáng)調(diào)了top初始化為0，那么理應(yīng)直接壓入數(shù)據(jù)，并把top++，不過在這之前，得判斷空間是否夠，當(dāng)top=capacity的時(shí)候，棧就滿了，那么就需要realloc擴(kuò)容。
Stack.h 文件：
//壓棧 void StackPush(ST* ps, STDataType x);
Stack.c 文件：
//壓棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果棧滿了，考慮擴(kuò)容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測(cè)容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將數(shù)據(jù)壓進(jìn)去
ps->top++;//棧頂上移
}出棧
思路：
在你出棧之前，要確保top不為空，而top不為空的條件就是top>0，所以還要斷言top>0，隨后，直接將棧頂位置下移--即可。跟順序表的思想大同小異。
Stack.h 文件：
//出棧 void StackPop(ST* ps);
Stack.c 文件：
//出棧
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}獲取棧頂元素
思路：
首先要搞清楚誰才是棧頂元素，是top位置還是top-1位置？很顯然是top-1的位置才是棧頂元素，因?yàn)樵谇拔某跏蓟臅r(shí)候已經(jīng)明確指出top為0，當(dāng)時(shí)壓棧時(shí)直接放入數(shù)據(jù)的，此時(shí)第一個(gè)數(shù)據(jù)下標(biāo)為0，隨后++top再壓入其它數(shù)據(jù)，由此可見，棧頂元素即下標(biāo)top-1的位置。
Stack.h 文件：
//訪問棧頂數(shù)據(jù) STDataType StackTop(ST* ps);
Stack.c 文件：
//訪問棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}獲取棧中有效元素個(gè)數(shù)
思想：
上文講到下標(biāo)top-1才是棧頂元素，那么是不是說總共就是top-1個(gè)元素呢？當(dāng)然不是，這里跟數(shù)組下標(biāo)一樣的思想，元素個(gè)數(shù)應(yīng)該就是top個(gè)，直接返回即可。
Stack.h 文件：
//有效元素個(gè)數(shù) int StackSize(ST* ps);
Stack.c 文件：
//有效元素個(gè)數(shù)
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}檢測(cè)棧是否為空
思路：
當(dāng)top的值為0時(shí)即為空，return直接返回即可
Stack.h 文件：
//判空 bool StackEmpty(ST* ps);
Stack.c 文件：
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top為0，那么就為真，即返回
}Test.c 文件：
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}效果如下：
總代碼
Stack.h 文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//創(chuàng)建棧結(jié)構(gòu)
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存儲(chǔ)數(shù)據(jù)
int top; //棧頂?shù)奈恢?
int capacity; //容量
}ST;
//初始化棧
void StackInit(ST* ps);
//銷毀棧
void StackDestory(ST* ps);
//壓棧
void StackPush(ST* ps, STDataType x);
//出棧
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//訪問棧頂數(shù)據(jù)
STDataType StackTop(ST* ps);
//有效元素個(gè)數(shù)
int StackSize(ST* ps);Stack.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化棧
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//銷毀棧
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//壓棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果棧滿了，考慮擴(kuò)容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測(cè)容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將數(shù)據(jù)壓進(jìn)去
ps->top++;//棧頂上移
}
//出棧
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top為0，那么就為真，即返回
}
//訪問棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}
//有效元素個(gè)數(shù)
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}
int main()
{
TestStack();
return 0;
}到此這篇關(guān)于C語言超詳細(xì)講解棧的實(shí)現(xiàn)及代碼的文章就介紹到這了,更多相關(guān)C語言 棧的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在編程的過程中,使用已經(jīng)封裝好的庫函數(shù)是十分方便的,也是十分高效的,這篇文章主要給大家介紹了關(guān)于C語言庫的封裝和使用的相關(guān)資料,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)密碼框，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
C++位運(yùn)算符詳解(異或運(yùn)算符和移位運(yùn)算符)
下面小編就為大家?guī)硪黄狢++位運(yùn)算符詳解(異或運(yùn)算符和移位運(yùn)算符)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-05-05
這篇文章主要介紹了12個(gè)關(guān)于C語言的有趣問答,有助于讀者加深對(duì)C語言程序設(shè)計(jì)的理解,需要的朋友可以參考下2014-07-07
C++中POCO庫的安裝與基礎(chǔ)知識(shí)介紹(Windwos和Linux)
這篇文章主要為大家介紹了C++ POCO庫的簡(jiǎn)單介紹、下載以及安裝方式、簡(jiǎn)單代碼示例，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-05-05
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)航班管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
C++實(shí)現(xiàn)LeetCode(86.劃分鏈表)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(86.劃分鏈表),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
Pipes實(shí)現(xiàn)LeetCode(194.轉(zhuǎn)置文件)
這篇文章主要介紹了Pipes實(shí)現(xiàn)LeetCode(194.轉(zhuǎn)置文件),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了C語言編程中預(yù)處理器的用法,包括介紹了C和C++混合編程的情況,需要的朋友可以參考下2016-02-02
C++ 數(shù)據(jù)結(jié)構(gòu)之對(duì)稱矩陣及稀疏矩陣的壓縮存儲(chǔ)
這篇文章主要介紹了C++ 數(shù)據(jù)結(jié)構(gòu)之對(duì)稱矩陣及稀疏矩陣的壓縮存儲(chǔ)的相關(guān)資料,這里實(shí)現(xiàn)稀疏矩陣和對(duì)稱矩陣的壓縮存儲(chǔ)的實(shí)例，需要的朋友可以參考下2017-08-08