github代碼下載

github代碼：
https://github.com/Kyrie-leon/Data_Structures/tree/main/stack_queue

一、 堆疊的概念及結構

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，
壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂，

二、堆疊的實作

堆疊的實作一般可以使用陣列或者鏈表實作，相對而言陣列的結構實作更優一些，因為陣列在尾上插入資料的代價比較小，如下圖所示，

而如果采用如下結構實作堆疊，尾插需要挪動資料，造成大量的計算開銷，

2.1 堆疊的存盤定義

靜態存盤的堆疊
使用一個靜態一維陣列a[N]實作，但這樣做會造成太多的空間浪費或者空間不足

#define N 10
typedef int STDataType;
typedef struct Stack Stack;
struct Stack
{
	STDataType a[N];
	int _top;	//堆疊頂
};

支持動態增長的堆疊
使用一個指標_a動態開辟記憶體實作堆疊的存盤

typedef int STDataType;
typedef struct Stack Stack;
//支持動態增長的堆疊
struct Stack
{
	STDataType * _a;
	int _top;			//堆疊頂
	int _capacity;		//容量
};

2.2 堆疊的初始化

初始化：默認為堆疊開辟四個STDataType大小的空間

• capacity：堆疊的容量大小,默認4
• _top: 表示堆疊頂，我們約定_top=0表示堆疊為空，之后每入堆疊一個元素_top加1，即_top所指向陣列的下表總是比實際堆疊頂元素下標大1

//堆疊的初始化
void StackInit(Stack * ps)
{
	assert(ps);
	ps->_a = (STDataType *)malloc(sizeof(Stack) * 4);	//默認陣列大小為4
	ps->_top = 0;		//堆疊為空，則堆疊頂為0
	ps->_capacity = 4;	//默認堆疊的容量為4
}

2.3 入堆疊

前面已經約定過_top所指向陣列的下表總是比實際堆疊頂元素下標大1
入堆疊只需要將資料存放到_top下標的陣列中,然后_top加1即可

//入堆疊
void StackPush(Stack * ps, STDataType data)
{
	assert(ps);
	//判斷堆疊是否滿了，滿了則增容
	if (ps->_top == ps->_capacity)
	{
		ps->_capacity *= 2;	//每次擴容2倍
		STDataType * tmp = (STDataType *)realloc(ps->_a, sizeof(Stack)*ps->_capacity);
		//判斷記憶體是否申請成功
		if (NULL == tmp)
		{
			printf("擴容失敗\n");
			exit(-1);
		}
		ps->_a = tmp;
	}
	//入堆疊
	ps->_a[ps->_top] = data;	
	ps->_top++;
}

2.4 出堆疊

_top所指向陣列的下表總是比實際堆疊頂元素下標大1
因此出堆疊只需將_top減1即可

//出堆疊
void StackPop(Stack * ps)
{
	assert(ps);
	assert(ps->_top>0);
	ps->_top--;
}

2.5 獲取堆疊頂元素

_top所指向陣列的下表總是比實際堆疊頂元素下標大1
所以堆疊頂元素的下標是_top-1

//獲取堆疊頂元素
STDataType StackTop(Stack *ps)
{
	assert(ps);
	assert(ps->_top>0);

	return ps->_a[ps->_top-1];	
}

2.6 獲取堆疊中有效元素個數

因為陣列元素下標從0開始，因此_top就表示堆疊中有效元素個數

//獲取堆疊中有效元素個數
int StackSize(Stack * ps)
{
	assert(ps);
	return ps->_top;
}

2.7 檢測堆疊是否為空

通過_top的值就可以判斷堆疊是否為空
若_top為0，表示為空，取反則回傳非0
若_top為1，表示不為空，取反則回傳0

//檢測堆疊是否為空，如果為慷訓傳非0，不為慷訓傳0
int StackEmpty(Stack* ps)
{
	assert(ps);
	return !(ps->_top);
}

2.8 銷毀堆疊

//銷毀堆疊
void StackDestory(Stack * ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

三、堆疊的測驗

#include "stack.h"

void TestStack()
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	while (!StackEmpty(&ps))
	{

		printf("%d, %d\n", StackTop(&ps),StackSize(&ps));
		StackPop(&ps);
	}

	
}

int main()
{
	TestStack();
	system("pause");
	return 0;
}

四、代碼清單

4.1 stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<windows.h>

#define N 10
typedef int STDataType;
typedef struct Stack Stack;
//struct Stack
//{
//	STDataType a[N];
//	int _top;	//堆疊頂
//};

//支持動態增長的堆疊
struct Stack
{
	STDataType * _a;
	int _top;			//堆疊頂
	int _capacity;		//容量
};

//初始化堆疊
void StackInit(Stack * ps);

//入堆疊
void StackPush(Stack * ps, STDataType data);

//出堆疊
void StackPop(Stack * ps);

//獲取堆疊頂元素
STDataType StackTop(Stack *ps);

//獲取堆疊頂中有效元素個數
int StackSize(Stack * ps);

//檢測堆疊是否為空，如果為慷訓傳非0，不為慷訓傳0
int StackEmpty(Stack* ps);

//銷毀堆疊
void StackDestory(Stack * ps);

4.2 stack.c

#include "stack.h"

//堆疊的初始化
void StackInit(Stack * ps)
{
	assert(ps);
	ps->_a = (STDataType *)malloc(sizeof(Stack) * 4);	//默認陣列大小為4
	ps->_top = 0;		//堆疊為空，則堆疊頂為0
	ps->_capacity = 4;	//默認堆疊的容量為4
}

//入堆疊
void StackPush(Stack * ps, STDataType data)
{
	assert(ps);
	//判斷堆疊是否滿了，滿了則增容
	if (ps->_top == ps->_capacity)
	{
		ps->_capacity *= 2;	//每次擴容2倍
		STDataType * tmp = (STDataType *)realloc(ps->_a, sizeof(Stack)*ps->_capacity);
		//判斷記憶體是否申請成功
		if (NULL == tmp)
		{
			printf("擴容失敗\n");
			exit(-1);
		}
		ps->_a = tmp;
	}
	//入堆疊
	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);
	assert(ps->_top>0);

	return ps->_a[ps->_top-1];	
}

//獲取堆疊中有效元素個數
int StackSize(Stack * ps)
{
	assert(ps);
	return ps->_top;
}

//檢測堆疊是否為空，如果為慷訓傳非0，不為慷訓傳0
int StackEmpty(Stack* ps)
{
	assert(ps);
	return !(ps->_top);
}

//銷毀堆疊
void StackDestory(Stack * ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

4.3 test.c

#include "stack.h"

void TestStack()
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	while (!StackEmpty(&ps))
	{

		printf("%d, %d\n", StackTop(&ps),StackSize(&ps));
		StackPop(&ps);
	}

	
}

int main()
{
	TestStack();
	system("pause");
	return 0;
}