棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據元素遵守后進先出LIFO（Last In First Out）的原則。有點類似于手槍彈夾，后壓進去的子彈總是最先打出，除非槍壞了。
壓棧：棧的插入操作叫做進棧/壓棧/入棧。（入數(shù)據在棧頂）
出棧：棧的刪除操作叫做出棧。（出數(shù)據也在棧頂）

注意：

1、函數(shù)調用也有棧，這兩個棧有區(qū)別嗎？

當然有區(qū)別。函數(shù)調用會調用棧幀，內存里頭也有一個棧，程序運行起來時要執(zhí)行函數(shù)，函數(shù)里頭的局部變量、參數(shù)、返回值等等都要存在函數(shù)棧幀里頭。

這兩個棧沒有任何關聯(lián)，一個是數(shù)據結構中的棧。另一個是操作系統(tǒng)中內存劃分的一個區(qū)域，叫做棧，用來函數(shù)調用時，建立棧幀。雖然本質上沒有任何關聯(lián)，但都符合后進先出的規(guī)則。

2、假設入棧順序為：1 2 3 4，那么出棧順序一定為：4 3 2 1 嗎？

當然不是。雖說規(guī)則上明確后進先出，可這是相對而言的，如果說它每進一個再出一個，然后再繼續(xù)壓棧，那不同樣符合后進先出的規(guī)則嗎。就如同上例，你說它出棧順序為1 2 3 4 都不足為奇，每進一個出一個再進，同樣符合規(guī)則。類似的入棧兩個再出再進再出也是可以的，好比如2 1 4 3。

棧的結構

棧的實現(xiàn)

創(chuàng)建棧結構

Stack.h 文件：

//創(chuàng)建棧結構
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //存儲數(shù)據
	int top; //棧頂?shù)奈恢?
	int capacity; //容量
}ST;

初始化棧

思想：

初始化還是相對比較簡單的，學了之前的順序表，初始化棧就很輕松了

Stack.h 文件：

//初始化棧
void StackInit(ST* ps);

Stack.c 文件：

//初始化棧
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

注意：

???這里初始化的時候將top置為0是有意圖的。首先，由上文創(chuàng)建棧結構時已經標注了，top是用來記錄棧頂?shù)奈恢?，既然是棧頂?shù)奈恢茫钱攖op初始化為0時，我們可以直接將數(shù)據放入棧中，隨后top++，但是當top初始化為-1時，top首先要++才能放入數(shù)據，因為數(shù)據不可能在負數(shù)不屬于棧的位置上放入。下圖演示過程：

本文以 top = 0 示例

銷毀棧

思想：

動態(tài)開辟的內存空間一定要釋放，free置空即可，并把其余數(shù)據置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;
}

入棧

思路：

前文已經強調了top初始化為0，那么理應直接壓入數(shù)據，并把top++，不過在這之前，得判斷空間是否夠，當top=capacity的時候，棧就滿了，那么就需要realloc擴容。

Stack.h 文件：

//壓棧
void StackPush(ST* ps, STDataType x);

Stack.c 文件：

//壓棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果棧滿了，考慮擴容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測容量
		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ù)據壓進去
	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的位置才是棧頂元素，因為在前文初始化的時候已經明確指出top為0，當時壓棧時直接放入數(shù)據的，此時第一個數(shù)據下標為0，隨后++top再壓入其它數(shù)據，由此可見，棧頂元素即下標top-1的位置。

Stack.h 文件：

//訪問棧頂數(shù)據
STDataType StackTop(ST* ps);

Stack.c 文件：

//訪問棧頂數(shù)據
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}

獲取棧中有效元素個數(shù)

思想：

上文講到下標top-1才是棧頂元素，那么是不是說總共就是top-1個元素呢？當然不是，這里跟數(shù)組下標一樣的思想，元素個數(shù)應該就是top個，直接返回即可。

Stack.h 文件：

//有效元素個數(shù)
int StackSize(ST* ps);

Stack.c 文件：

//有效元素個數(shù)
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

檢測棧是否為空

思路：

當top的值為0時即為空，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)建棧結構
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //存儲數(shù)據
	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ù)據
STDataType StackTop(ST* ps);
 
//有效元素個數(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);
	//如果棧滿了，考慮擴容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測容量
		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ù)據壓進去
	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ù)據
STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}
 
//有效元素個數(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;
}

到此這篇關于C語言超詳細講解棧的實現(xiàn)及代碼的文章就介紹到這了,更多相關C語言棧的實現(xiàn)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: