詳解C語言之堆棧

更新時間：2021年11月17日 15:24:04 作者：ぃ咔哇依°ヽ

這篇文章主要為大家介紹了C語言的堆棧，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助

一、何為堆棧？

a.堆棧是一種特殊的線性表

b.堆棧的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其不同點是：線性表允許在任意位置插入和刪除數(shù)據(jù)元素，但堆棧只允許在固定一端進行插入和刪除數(shù)據(jù)元素，所以棧又稱為“先進后出”（FILO)或“后進先出”（LIFO）的線性表

c.堆棧中允許進行插入和刪除數(shù)據(jù)元素的一端稱為棧頂，另一端稱為棧底

d.堆棧的插入操作通常稱為進棧或入棧；堆棧的刪除操作通常稱為出棧或退棧

二、思維導圖

三、代碼

1、順序堆棧

#include <stdio.h>
typedef int DataType;
#define MaxStackSize 64
typedef struct
{
	DataType stack[MaxStackSize];
	int top;
}SeqStack;
//初始化
void StackInit(SeqStack *S)
{
	S->top = 0;
}
//判斷是否棧空
int StackIsEmpty(SeqStack S)
{
	if (S.top <= 0)
		return 0;
	else
		return 1;
}
//入棧
int StackPush(SeqStack *S, DataType x)
{
	if (S->top >= MaxStackSize)
	{
		printf("棧滿，無法進棧！??！\n");
		return 0;
	}
	else
	{
		S->stack[S->top] = x;
		S->top++;
		return 1;
	}
}
//出棧
int StackPop(SeqStack *S, DataType *x)
{
	if (S->top <= 0)
	{
		printf("堆棧已空，無法出棧?。?！\n");
		return 0;
	}
	else
	{
		S->top--;
		*x = S->stack[S->top];
		return 1;
	}
}
//獲取棧頂元素
int StackGetTop(SeqStack S, DataType *x)
{
	if (S.top <= 0)
	{
		printf("堆棧已空?。。n");
			return 0;
	}
	else
	{
		*x = S.stack[S.top - 1];
		return 1;
	}
}
int main()
{
	SeqStack myStack;
	int i, x;
	StackInit(&myStack);
	for (i = 0; i < 10; i++)
		StackPush(&myStack, i + 1);
	StackGetTop(myStack, &x);
	printf("當前棧頂元素為：%d\n", x);
	printf("依次出棧：");
	while (StackIsEmpty(myStack))
	{
		StackPop(&myStack, &x);
		printf("%d ", x);
	}
	system("pause");
	return 0;
}

2、鏈式堆棧

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct snode
{
	DataType data;
	struct snode *next;
}LSNode;
//初始化
void StackInit(LSNode **top)
{
	*top = (LSNode *)malloc(sizeof(LSNode));
	(*top)->next = NULL;
}
//判斷堆棧是否非空
int StackIsEmpty(LSNode *top)
{
	if (top->next == NULL)
		return 0;
	else
		return 1;
}
//入棧
void StackPush(LSNode *top, DataType x)
{
	LSNode *p;
	p = (LSNode *)malloc(sizeof(LSNode));
	p->data = x;
	p->next = top->next;
	top->next = p;
}
//出棧
int StackPop(LSNode *top, DataType *x)
{
	LSNode *p = top->next;
	if (p == NULL)
	{
		printf("堆棧已空，刪除錯誤?。?！\n");
		return 0;
	}
	top->next = p->next;
	*x = p->data;
	free(p);
	return 1;
}
//獲取棧頂元素
int StackGetTop(LSNode *top, DataType *x)
{
	LSNode *p = top->next;
	if (p == NULL)
	{
		printf("堆棧已空，取出錯誤！??！\n");
		return 0;
	}
	*x = p->data;
	return 1;
}
//釋放內(nèi)存空間
void StackDestroy(LSNode **top)
{
	LSNode *p, *q;
	p = *top;
	while (p != NULL)
	{
		q = p;
		p = p->next;
		free(q);
	}
	*top = NULL;
}
int main()
{
	int i, x;
	LSNode *top;
	StackInit(&top);
	for (i = 0; i < 10; i++)
		StackPush(top, i + 1);
	StackGetTop(top, &x);
	printf("當前棧頂元素為%d\n", x);
	printf("依次出棧：");
	while (StackIsEmpty(top))
	{
		StackPop(top, &x);
		printf("%4d", x);
	}
	StackDestroy(&top);
	system("pause");
	return 0;
}