快捷導(dǎo)航

C語言實現(xiàn)數(shù)組棧的代碼示例

更新時間：2024年07月28日 09:59:34 作者：池央

棧是一種特殊的線性表,其只允許在固定的一端進(jìn)行插入和刪除元素操作,進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂,另一端稱為棧底,本文給大家介紹了C語言實現(xiàn)數(shù)組棧的代碼示例,需要的朋友可以參考下

棧的概念及結(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; // 棧頂,類似順序表中的_size
	int _capacity; // 容量
}Stack;

對棧的操作

棧初始化

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

_top也可以初始化為1，此時棧頂元素就是_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);
	//擴容
	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;
}

棧的長度

_top初始化為0，此時的_top的大小剛好就是棧的長度

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>
// 支持動態(tài)增長的棧
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;//數(shù)組
	int _top; // 棧頂,類似順序表中的_size
	int _capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結(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);
	//擴容
	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];
}
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
// 檢測棧是否為空，如果為空返回非零結(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;
}

測試

#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;
}

到此這篇關(guān)于C語言實現(xiàn)數(shù)組棧的代碼示例的文章就介紹到這了,更多相關(guān)C語言數(shù)組棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: