前言

hello，大家好，今天我們來繼續更新資料結構方面的文章，這期主要用來介紹堆疊和佇列的知識，希望對大家有所幫助，也歡迎大家批評指正，

1. 堆疊的概念

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

2. 進出堆疊影片演示

入堆疊：
在這里插入圖片描述
出堆疊：

3. 通過幾道題目來理解LIFO

在這里插入圖片描述
這道題根據后進先出的理論，答案要選擇B，
2.

注意，題目中說進堆疊的程序中可以出堆疊，也就是說，我可以先入一個1，然后1出來，然后入2，2再出來，接下來入三，然后三再出來，再入4,4再出來，也就是說出堆疊的順序可以是1、2、3、4，所以這道題就需要我們去逐一分析一下選項，
首先，我們看A，對于A，我們可以先入1，然后1出堆疊，接下來依次入2、3、4，然后出堆疊是4、3、2.所以A可以，
對于B，我們可以先入1，然后入2，然后2出，然后入3，然后3出，然后入4，然后4出，最后1出，所以B也可以，
對于C，首先出的是3，所以這就要求我們此時已經將1,2，放入了，4還沒有放入，我們出3之后，如果可以實作，我們要出1，可是1之前還有2，所以是矛盾的，所以C這種情況是不可能的，
對于D，我們可以先入1,2，然后入3出3，入4出4，最后出2，和1,，所以D也可以，
通過以上分析，這道題目我們應該選C，

4. 堆疊的實作

堆疊的實作一般可以使用陣列或者鏈表實作，相對而言，陣列的結構實作更優一些，因為陣列在尾上插入資料的代價比較小，但是涉及到容量問題，所以在接下來，我們要實作的堆疊是通過陣列結構且可增容的堆疊，

堆疊的實作很簡單，下面是完整的代碼，堆疊只能從堆疊頂進行資料的增加或者洗掉，所以對于堆疊的增加和洗掉操作，就相當于順序表中的尾插和尾刪，所以堆疊的實作就簡便很多，因為我們只需要順著線性表中尾插和尾刪的思路在尾巴上搞一點事情就好啦，

4.1 Stack.h檔案

#include<stdio.h>
#include<stdbool.h>
#include<malloc.h>
#include<assert.h>


typedef int SDataType;
typedef struct Stack
{
	SDataType *a;
	int top;//堆疊頂
	int capacity;//容量，方便增容
}Stack;


//初始化
void StackInit(Stack *pst);
//銷毀
void StackDestory(Stack *pst);
//入堆疊
void StackPush(Stack *pst,SDataType x);
//出堆疊
void StackPop(Stack *pst);
//取堆疊頂資料
SDataType StackTop(Stack *pst);
//判斷空堆疊
bool StackEmpty(Stack *pst);
//取堆疊的資料個數
int StackSize(Stack *pst);

4.2 Stack.c檔案

#include"Stack.h"

//初始化
void StackInit(Stack *pst)
{
	assert(pst);
	pst->a = (SDataType*)malloc(sizeof(SDataType)* 4);
	pst->top = 0;
	pst->capacity = 4;
}
//銷毀
void StackDestory(Stack *pst)
{
	assert(pst);
	free(pst->a);
	pst->a =NULL;
	pst->capacity = 0;
	pst->top = 0;
}
//入堆疊
void StackPush(Stack *pst, SDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		SDataType*tmp = (SDataType *)realloc(pst->a,sizeof(SDataType)*pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
//出堆疊
void StackPop(Stack *pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->top--;
}
//取堆疊頂資料
SDataType StackTop(Stack *pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}
//判斷空堆疊
bool StackEmpty(Stack *pst)
{
	assert(pst);
	return pst->top==0;
}
//取堆疊的資料個數
int StackSize(Stack *pst)
{
	assert(pst);
	return pst->top;
}

4.3 test.c檔案

#include"Stack.h"

void TestOne()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d  ", StackTop(&st));
		StackPop(&st);
	}
	StackDestory(&st);
}

int main()
{
	TestOne();
	return 0;
}

4.4 測驗運行

在這里插入圖片描述

后記

好的，這期文章我們就分享到這里了，感謝大家的支持，我們下一期文章再見，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300469.html

標籤：其他

上一篇：Leetcode刷題100天—3. 無重復字符的最長子串(滑動視窗+集合+雙指標)—day21

下一篇：【LeetCode】用佇列實作堆疊（225. 題）| 動圖演示，超詳細哦~

資料結構：堆疊——在“尾巴”上搞事情

目錄

前言