棧（Stack）的原理與代碼實現

来源:https://www.cnblogs.com/fly-home/p/18157683
-Advertisement-
Play Games

棧（stack） 原理說明： ​ 學習數據結構的目的是為了更好的處理和存儲數據，對於順序表而言改查比較容易，增刪比較麻煩，對於鏈式表而言，增刪比較簡單，改查比較麻煩，所以每種數據結構都有不同的特點，用戶需要選擇合適的數據結構。 ​ 棧記憶體自頂向下進行遞增，其實棧和順序表以及鏈式表都一樣，都屬於線性結 ...


棧（stack）

原理說明：

​ 學習數據結構的目的是為了更好的處理和存儲數據，對於順序表而言改查比較容易，增刪比較麻煩，對於鏈式表而言，增刪比較簡單，改查比較麻煩，所以每種數據結構都有不同的特點，用戶需要選擇合適的數據結構。

​ 棧記憶體自頂向下進行遞增，其實棧和順序表以及鏈式表都一樣，都屬於線性結構，****存儲的數據的邏輯關係也是一對一的。

image

​ 如上圖所示，棧的模型類似一一個瓶子。

​ 1）棧的一端是封閉的，數據的插入與刪除只能在棧的另一端進行，也就是棧遵循“*後進先出*”的原則。也被成為“LIFO”結構，意思是“last input first output”。

​ 2）棧（stack）,存儲貨物或供旅客住宿的地方,可引申為倉庫、中轉站，所以引入到電腦領域里，就是指數據暫時存儲的地方，所以才有進棧（PUSH）、出棧（POP）的說法。

棧原理舉例

image

​ 如圖所示，在三本書均放進“棧”中後，我們想要取得Blue書時，必須將前兩本書依次取出，即是棧“先進後出”特點的展示。

​ 閉合的一端被稱為棧底（Stack Bottom），允許數據的插入與刪除的一端被稱為棧頂（Stack Top），不包含任何元素的棧被稱為空棧。

  • 把數據插入到棧空間的動作被稱為入棧或者壓棧（push）

image

  • 從棧空間中刪除數據的動作被稱為出棧或者彈棧（pop）

image

代碼實現

​ 由於棧也是一種線性結構，所以可以以數組或者鏈表作為基礎，在此基礎上實現棧的操作。

順序棧：以數組作為基礎實現棧空間

​ 數組在記憶體中占用一塊連續的空間，也就是數組元素的記憶體地址是連續的。為了實現棧，一般是把數組頭作為棧底，數組頭部到數組尾部作為棧的增長方向，也就是用戶只在數組尾部對數據進行插入和刪除。這樣規定的原因其一是因為數組能夠進行隨機訪問，所以數組的尾插較為便利。

image

代碼實現：

​ 為了方便管理順序棧所以需要構造管理順序棧信息的結構體類型，用於記錄重要參數，如下：

//指的是順序棧中的元素的數據類型，用戶可以根據需要進行修改
typedef int  DataType_t;

//構造記錄順序棧SequenceStack各項參數(棧底地址+棧容量+棧頂元素的下標)的結構體
typedef struct SequenceStack
{
	DataType_t * Bottom;		//記錄棧底地址
	unsigned int Size;			//記錄棧容量
	int			 Top;      		//記錄棧頂元素的下標	

}SeqStack_t;

  1. 創建一個空的順序棧，併為記錄順序棧信息的結構體申請堆記憶體，併進行初始化即可

    /*********************************************************************
*
*	name	 :	SeqStack_Create
*	function :  創建一個空的順序棧，併為記錄順序棧信息的結構體
				申請堆記憶體，併進行初始化即可！
*	argument :  
*				@size  :棧的容量大小
*				
*	retval	 :  調用成功返回順序棧的地址
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
//創建順序表並對順序棧進行初始化
SeqStack_t * SeqStack_Create(unsigned int size)
{
	//1.利用calloc為順序棧的管理結構體申請一塊堆記憶體
	SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));

	if(NULL == Manager)
	{
		perror("calloc memory for manager is failed");
		exit(-1); //程式異常終止
	}

	//2.利用calloc為所有元素申請堆記憶體
	Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));

	if (NULL == Manager->Bottom)
	{
		perror("calloc memory for Stack is failed");
		free(Manager);
		exit(-1); //程式異常終止
	}

	//3.對管理順序棧的結構體進行初始化（元素容量 + 最後元素下標）
	Manager->Size = size;	//對順序棧中的容量進行初始化
	Manager->Top = -1;		//由於順序棧為空，則棧頂元素的下標初值為-1
	
	return Manager;
}

  2. 根據棧的特性，把新元素從棧頂入棧，也就是從數組的尾部進行元素插入，操作如下：

    /*********************************************************************
*
*	name	 :	SeqStack_IsFull
*	function : 判斷順序棧是否已滿
*	argument :  
*				@Manager  :順序棧的地址
*				
*	retval	 :  調用成功返回bool型，滿了則返回true，沒滿返回false
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
bool SeqStack_IsFull(SeqStack_t *Manager)
{
	return (Manager->Top + 1 == Manager->Size) ? true : false;
}
/*********************************************************************
*
*	name	 :	SeqStack_Push
*	function : 根據棧的特性，把新元素從棧頂入棧，也就是從數組的尾部進行元素插入
*	argument :  
*				@Manager  :順序棧的地址
				@Date  	  :要入棧的數據
*				
*	retval	 :  調用成功返回bool型，滿了則返回true，沒滿返回false
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
//入棧
bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data)
{
	//1.判斷順序棧是否已滿
	if ( SeqStack_IsFull(Manager) )
	{
		printf("SeqStack Full is Full!\n");
		return false;
	}

	//2.如果順序棧有空閑空間，則把新元素添加到順序棧的棧頂
	Manager->Bottom[++Manager->Top] = Data;

	return true;
}

  3. 根據棧的特性，把元素從棧頂出棧，也就是把元素從數組的尾部把元素刪除

    /*********************************************************************
*
*	name	 :	SeqStack_IsEmpty
*	function : 	判斷順序棧是否為空
*	argument :  
*				@Manager  :順序棧的地址
*				
*	retval	 :  調用成功返回bool型，空了則返回true，沒空返回false
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
bool SeqStack_IsEmpty(SeqStack_t *Manager)
{
	return (-1 == Manager->Top) ? true : false;
}
/*********************************************************************
*
*	name	 :	SeqStack_Pop
*	function : 根據棧的特性，把元素從棧頂出棧，也就是把元素從數組的尾部把元素刪除
*	argument :  
*				@Manager  :順序棧的地址
*				
*	retval	 :  調用成功返回新的棧地址
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
//出棧
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
	DataType_t temp = 0;  //用於存儲出棧元素的值

	//1.判斷順序棧是否為空
	if ( SeqStack_IsEmpty(Manager) )
	{
		printf("SeqStack is Empty!\n");
		return;
	}
	
	//2.由於刪除了一個元素，則需要讓順序棧的棧頂元素下標-1
	temp = Manager->Bottom[Manager->Top--];

	return temp;
}

  4. 對順序棧中的元素進行遍歷，只需要從順序棧的棧底開始向棧頂進行遍歷

    //遍歷順序表的元素
void SeqStack_Print(SeqStack_t *Manager)
{
	for (int i = 0; i <= Manager->Top; ++i)
	{
		printf(" Stack Element[%d] = %d\n",i,Manager->Bottom[i]);
	}
}

    代碼完整展示

    /*******************************************************************
*
*	file name:	SequenceStack.c
*	author	 :  [email protected]
*	date	 :  2024/04/25
*	function :  該案例是以數組作為基礎實現棧空間，並且把數組頭作為棧底，
				數據頭部到數據尾部作為棧的增長方向。
* 	note	 :  None
*
*	CopyRight (c)  2023-2024   [email protected]   All Right Reseverd 
*
* *****************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//指的是順序棧中的元素的數據類型，用戶可以根據需要進行修改
typedef int  DataType_t;

//構造記錄順序棧SequenceStack各項參數(棧底地址+棧容量+棧頂元素的下標)的結構體
typedef struct SequenceStack
{
	DataType_t * Bottom;		//記錄棧底地址
	unsigned int Size;			//記錄棧容量
	int			 Top;      		//記錄棧頂元素的下標	

}SeqStack_t;
/*********************************************************************
*
*	name	 :	SeqStack_Create
*	function :  創建一個空的順序棧，併為記錄順序棧信息的結構體
				申請堆記憶體，併進行初始化即可！
*	argument :  
*				@size  :棧的容量大小
*				
*	retval	 :  調用成功返回順序棧的地址
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
//創建順序表並對順序棧進行初始化
SeqStack_t * SeqStack_Create(unsigned int size)
{
	//1.利用calloc為順序棧的管理結構體申請一塊堆記憶體
	SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));

	if(NULL == Manager)
	{
		perror("calloc memory for manager is failed");
		exit(-1); //程式異常終止
	}

	//2.利用calloc為所有元素申請堆記憶體
	Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));

	if (NULL == Manager->Bottom)
	{
		perror("calloc memory for Stack is failed");
		free(Manager);
		exit(-1); //程式異常終止
	}

	//3.對管理順序棧的結構體進行初始化（元素容量 + 最後元素下標）
	Manager->Size = size;	//對順序棧中的容量進行初始化
	Manager->Top = -1;		//由於順序棧為空，則棧頂元素的下標初值為-1
	
	return Manager;
}
/*********************************************************************
*
*	name	 :	SeqStack_IsFull
*	function : 判斷順序棧是否已滿
*	argument :  
*				@Manager  :順序棧的地址
*				
*	retval	 :  調用成功返回bool型，滿了則返回true，沒滿返回false
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
bool SeqStack_IsFull(SeqStack_t *Manager)
{
	return (Manager->Top + 1 == Manager->Size) ? true : false;
}
/*********************************************************************
*
*	name	 :	SeqStack_Push
*	function : 根據棧的特性，把新元素從棧頂入棧，也就是從數組的尾部進行元素插入
*	argument :  
*				@Manager  :順序棧的地址
				@Date  	  :要入棧的數據
*				
*	retval	 :  調用成功返回bool型，滿了則返回true，沒滿返回false
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
//入棧
bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data)
{
	//1.判斷順序棧是否已滿
	if ( SeqStack_IsFull(Manager) )
	{
		printf("SeqStack Full is Full!\n");
		return false;
	}

	//2.如果順序棧有空閑空間，則把新元素添加到順序棧的棧頂
	Manager->Bottom[++Manager->Top] = Data;

	return true;
}

/*********************************************************************
*
*	name	 :	SeqStack_IsEmpty
*	function : 	判斷順序棧是否為空
*	argument :  
*				@Manager  :順序棧的地址
*				
*	retval	 :  調用成功返回bool型，空了則返回true，沒空返回false
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
bool SeqStack_IsEmpty(SeqStack_t *Manager)
{
	return (-1 == Manager->Top) ? true : false;
}
/*********************************************************************
*
*	name	 :	SeqStack_Pop
*	function : 根據棧的特性，把元素從棧頂出棧，也就是把元素從數組的尾部把元素刪除
*	argument :  
*				@Manager  :順序棧的地址
*				
*	retval	 :  調用成功返回新的棧地址
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
//出棧
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
	DataType_t temp = 0;  //用於存儲出棧元素的值

	//1.判斷順序棧是否為空
	if ( SeqStack_IsEmpty(Manager) )
	{
		printf("SeqStack is Empty!\n");
		return;
	}
	
	//2.由於刪除了一個元素，則需要讓順序棧的棧頂元素下標-1
	temp = Manager->Bottom[Manager->Top--];

	return temp;
}
/*********************************************************************
*
*	name	 :	SeqStack_Push
*	function : 對順序棧中的元素進行遍歷，只需要從順序棧的棧底開始向棧頂進行遍歷
*	argument :  
*				@Manager  :順序棧的地址
*				
*	retval	 :  調用成功返回bool型，滿了則返回true，沒滿返回false
*	author	 :  [email protected]
*	date	 :  2024/04/25
* 	note	 :  none
* 	
* *****************************************************************/
//遍歷順序表的元素
void SeqStack_Print(SeqStack_t *Manager)
{
	for (int i = 0; i <= Manager->Top; ++i)
	{
		printf(" Stack Element[%d] = %d\n",i,Manager->Bottom[i]);
	}
}



int main(int argc, char const *argv[])
{
	//創建一個容量大小為10的棧
	SeqStack_t *SequenceStack = SeqStack_Create(10);

	//入棧
	//1.沒滿時
	SeqStack_Push(SequenceStack, 10);
	SeqStack_Push(SequenceStack, 20);
	SeqStack_Push(SequenceStack, 30);
	SeqStack_Push(SequenceStack, 40);
	SeqStack_Push(SequenceStack, 50);
	SeqStack_Push(SequenceStack, 60);
	SeqStack_Push(SequenceStack, 70);
	SeqStack_Push(SequenceStack, 80);
	SeqStack_Push(SequenceStack, 90);
	SeqStack_Push(SequenceStack, 100);
	printf("\n");
	//遍歷顯示
	SeqStack_Print(SequenceStack);
	printf("\n");
	//2.滿時進棧
	SeqStack_Push(SequenceStack, 666);
	printf("\n");
	//遍歷顯示
	SeqStack_Print(SequenceStack);
	printf("\n");

	//出棧
	//1.有元素時出棧
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	printf("\n");
	//遍歷顯示
	SeqStack_Print(SequenceStack);
	printf("\n");
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	SeqStack_Pop(SequenceStack);
	printf("\n");
	//遍歷顯示
	SeqStack_Print(SequenceStack);
	printf("\n");

	//2.空時出棧
	SeqStack_Pop(SequenceStack);



	return 0;
}

    結果驗證：

image

鏈式棧：以鏈表作為基礎實現棧空間

如果打算實現鏈式棧，一般是以鏈表作為基礎，一般是把鏈表頭部作為棧頂，方便數據的插入和刪除（頭插+頭刪），鏈式棧相當於是一個單向不迴圈的鏈表。

image

為了方便管理鏈式棧，所以需要構造鏈式棧的結構體類型，如下：

//指的是鏈式棧中的元素的數據類型，用戶可以根據需要進行修改
typedef int  DataType_t;

//構造記錄鏈式棧各項參數(棧中存儲數據 + 棧頂元素的地址)的結構體
typedef struct ChainStack
{
	DataType_t              data;		//記錄棧中存儲數據
	struct ChainStack      *next;		//記錄當前節點直接後繼節點的地址

}ChaStack_t;

  1. 創建一個空的鏈式棧，併為記錄順序棧信息的結構體申請堆記憶體，併進行初始化即可！

    /********************************************************************
 *
 *	name	 :	ChainStack_Create
 *	function :  創建一個鏈式棧，棧頂應該連接有一個頭結點，對該頭結點進行初始化
 *	argument :
 *				none
 *
 *	retval	 :  調用成功返回已經完成初始化棧頂的頭結點,否則退出程式
 *	author	 :  [email protected]
 *	date	 :  2024/04/25
 * 	note	 :  none
 *
 * *****************************************************************/
ChaStack_t *ChainStack_Create(void)
{
	// 1.創建一個頭結點並對頭結點申請記憶體
	ChaStack_t *Head = (ChaStack_t *)calloc(1, sizeof(ChaStack_t));
	if (Head == NULL)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	// 2.對頭結點進行初始化，頭結點是不存儲數據域，指針域指向NULL
	Head->next = NULL;

	// 3.把頭結點的地址返回即可
	return Head;
}

  2. 根據棧的特性，把新元素從棧頂入棧，也就是從鏈表的首部進行元素插入，操作如下：

/********************************************************************
 *
 *	name	 :	ChainStack_NewNode
 *	function :  創建新的結點，並對新結點進行初始化（數據域 + 指針域）
 *	argument :
 *				@data 新節點需要存儲的數據
 *
 *	retval	 :  調用成功返回已經完成初始化的鏈式棧的新節點,否則返回NULL
 *	author	 :  [email protected]
 *	date	 :  2024/04/25
 * 	note	 :  none
 *
 * *****************************************************************/
ChaStack_t *ChainStack_NewNode(DataType_t data)
{
	// 1.創建一個新結點並對新結點申請記憶體
	ChaStack_t *New = (ChaStack_t *)calloc(1, sizeof(ChaStack_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	// 2.對新結點的數據域和指針域進行初始化
	New->data = data;
	New->next = NULL;

	return New;
}
/********************************************************************
 *
 *	name	 :	ChainStack_Push
 *	function :  入棧，將要存儲的數據，從棧頂入棧，即對鏈表進行頭插操作
 *	argument :
 *				@Head 棧頂連接頭結點
 *				@data 新節點的數據域需要存儲的數據
 *
 *	retval	 :  調用成功輸出"插入成功"，否則輸出"插入失敗"
 *	author	 :  [email protected]
 *	date	 :  2024/04/23
 * 	note	 :  none
 *
 * *****************************************************************/
void ChainStack_Push(ChaStack_t *Head, DataType_t data)
{
	// 定義一個迴圈指針變數Phead
	ChaStack_t *Phead = Head->next;
	// 調用函數創立一個新節點,並完成對應的錯誤處理
	ChaStack_t *New = ChainStack_NewNode(data);
	if (New == NULL)
	{
		printf("Push of %d is fail!\n", New->data);
		return;
	}

	// 進行判斷，排除空鏈表的情況
	if (Head->next == NULL)
	{
		Head->next = New;
		printf("Push of %d is success!\n", New->data);
		return;
	}

	//1. 將新節點的next連接至首節點
    New->next = Phead;
    //2. 將頭結點的next連接至新節點
    Head->next = New;

    printf("Push of %d is success!\n", New->data);

	return;
}

  1. 根據棧的特性，把元素從棧頂出棧，也就是把元素從鏈表的首部將元素刪除，操作如下：

    /********************************************************************
 *
 *	name	 :	CircLList_HeadDel
 *	function :  出棧，將鏈式棧的棧頂元素刪除，即鏈表的頭刪
 *	argument :
 *				@Head 棧頂連接的頭結點
 *
 *	retval	 :  調用成功後讓棧頂的元素出棧
 *	author	 :  [email protected]
 *	date	 :  2024/04/25
 * 	note	 :  none
 *
 * *****************************************************************/
void ChainStack_Pop(ChaStack_t *Head)
{
	// 對單向迴圈鏈表的頭結點的地址進行備份
	ChaStack_t *Phead = Head->next;

	// 判斷當前鏈表是否為空，為空則直接退出
	if (Head->next == NULL)
	{
		printf("current linkeflist is empty!\n");
		return;
	}

	//1. 將頭結點的next連接至首節點的直接後繼
    Head->next = Phead->next;
    //2. 將首節點的next指向NULL
    Phead->next = NULL;
    //3. 刪除掉首節點
    free(Phead);

    printf("Pop is success!\n");

	return;
}

  2. 對鏈式棧中的元素進行遍歷，只需要從鏈式棧的棧頂開始向棧底進行遍歷，操作如下：

/********************************************************************
 *
 *	name	 :	ChainStack_Printf
 *	function :  遍歷輸出棧中已經存儲的數據
 *	argument :
 *				@Head 棧頂連接的頭結點
 *
 *	retval	 :  調用成功輸出鏈表中所有節點的數據域的值
 *	author	 :  [email protected]
 *	date	 :  2024/04/23
 * 	note	 :  none
 *
 * *****************************************************************/
void ChainStack_Printf(ChaStack_t *Head)
{
	// 對單向迴圈鏈表的頭結點的地址進行備份
	ChaStack_t *Phead = Head;

	// 判斷當前鏈表是否為空，為空則直接退出
	if (Head->next == NULL)
	{
		printf("current linkeflist is empty!\n");
		return;
	}

    printf("Stack Top->");
	// 從首結點開始遍歷
	while (Phead->next)
	{
		// 把頭結點的直接後繼作為新的頭結點
		Phead = Phead->next;

        // 輸出頭結點的直接後繼的數據域
        printf("%d->", Phead->data);

		// 判斷是否到達尾結點，尾結點的next指針是指向首結點的地址
		if (Phead->next == Head->next)
		{
			break;
		}
	}

    printf("Stack Bottom\n");

    return;
}

代碼整體展示：

/*******************************************************************
*
*	file name:	ChainStack.c
*	author	 :  [email protected]
*	date	 :  2024/04/25
*	function :  該案例是掌握鏈式棧的創建原理與功能實現
* 	note	 :  None
*
*	CopyRight (c)  2023-2024   [email protected]   All Right Reseverd 
*
* *****************************************************************/
#include <stdio.h>
#include <stdlib.h>

//指的是鏈式棧中的元素的數據類型，用戶可以根據需要進行修改
typedef int  DataType_t;

//構造記錄鏈式棧各項參數(棧中存儲數據 + 棧頂元素的地址)的結構體
typedef struct ChainStack
{
	DataType_t              data;		//記錄棧中存儲數據
	struct ChainStack      *next;		//記錄當前節點直接後繼節點的地址

}ChaStack_t;
/********************************************************************
 *
 *	name	 :	ChainStack_Create
 *	function :  創建一個鏈式棧，棧頂應該連接有一個頭結點，對該頭結點進行初始化
 *	argument :
 *				none
 *
 *	retval	 :  調用成功返回已經完成初始化棧頂的頭結點,否則退出程式
 *	author	 :  [email protected]
 *	date	 :  2024/04/25
 * 	note	 :  none
 *
 * *****************************************************************/
ChaStack_t *ChainStack_Create(void)
{
	// 1.創建一個頭結點並對頭結點申請記憶體
	ChaStack_t *Head = (ChaStack_t *)calloc(1, sizeof(ChaStack_t));
	if (Head == NULL)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	// 2.對頭結點進行初始化，頭結點是不存儲數據域，指針域指向NULL
	Head->next = NULL;

	// 3.把頭結點的地址返回即可
	return Head;
}
/********************************************************************
 *
 *	name	 :	ChainStack_NewNode
 *	function :  創建新的結點，並對新結點進行初始化（數據域 + 指針域）
 *	argument :
 *				@data 新節點需要存儲的數據
 *
 *	retval	 :  調用成功返回已經完成初始化的鏈式棧的新節點,否則返回NULL
 *	author	 :  [email protected]
 *	date	 :  2024/04/25
 * 	note	 :  none
 *
 * *****************************************************************/
ChaStack_t *ChainStack_NewNode(DataType_t data)
{
	// 1.創建一個新結點並對新結點申請記憶體
	ChaStack_t *New = (ChaStack_t *)calloc(1, sizeof(ChaStack_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	// 2.對新結點的數據域和指針域進行初始化
	New->data = data;
	New->next = NULL;

	return New;
}
/********************************************************************
 *
 *	name	 :	ChainStack_Push
 *	function :  入棧，將要存儲的數據，從棧頂入棧，即對鏈表進行頭插操作
 *	argument :
 *				@Head 棧頂連接頭結點
 *				@data 新節點的數據域需要存儲的數據
 *
 *	retval	 :  調用成功輸出"插入成功"，否則輸出"插入失敗"
 *	author	 :  [email protected]
 *	date	 :  2024/04/23
 * 	note	 :  none
 *
 * *****************************************************************/
void ChainStack_Push(ChaStack_t *Head, DataType_t data)
{
	// 定義一個迴圈指針變數Phead
	ChaStack_t *Phead = Head->next;
	// 調用函數創立一個新節點,並完成對應的錯誤處理
	ChaStack_t *New = ChainStack_NewNode(data);
	if (New == NULL)
	{
		printf("Push of %d is fail!\n", New->data);
		return;
	}

	// 進行判斷，排除空鏈表的情況
	if (Head->next == NULL)
	{
		Head->next = New;
		printf("Push of %d is success!\n", New->data);
		return;
	}

	//1. 將新節點的next連接至首節點
    New->next = Phead;
    //2. 將頭結點的next連接至新節點
    Head->next = New;

    printf("Push of %d is success!\n", New->data);

	return;
}
/********************************************************************
 *
 *	name	 :	CircLList_HeadDel
 *	function :  出棧，將鏈式棧的棧頂元素刪除，即鏈表的頭刪
 *	argument :
 *				@Head 棧頂連接的頭結點
 *
 *	retval	 :  調用成功後讓棧頂的元素出棧
 *	author	 :  [email protected]
 *	date	 :  2024/04/25
 * 	note	 :  none
 *
 * *****************************************************************/
void ChainStack_Pop(ChaStack_t *Head)
{
	// 對單向迴圈鏈表的頭結點的地址進行備份
	ChaStack_t *Phead = Head->next;

	// 判斷當前鏈表是否為空，為空則直接退出
	if (Head->next == NULL)
	{
		printf("current linkeflist is empty!\n");
		return;
	}

	//1. 將頭結點的next連接至首節點的直接後繼
    Head->next = Phead->next;
    //2. 將首節點的next指向NULL
    Phead->next = NULL;
    //3. 刪除掉首節點
    free(Phead);

    printf("Pop is success!\n");

	return;
}
/********************************************************************
 *
 *	name	 :	ChainStack_Printf
 *	function :  遍歷輸出棧中已經存儲的數據
 *	argument :
 *				@Head 棧頂連接的頭結點
 *
 *	retval	 :  調用成功輸出鏈表中所有節點的數據域的值
 *	author	 :  [email protected]
 *	date	 :  2024/04/23
 * 	note	 :  none
 *
 * *****************************************************************/
void ChainStack_Printf(ChaStack_t *Head)
{
	// 對單向迴圈鏈表的頭結點的地址進行備份
	ChaStack_t *Phead = Head;

	// 判斷當前鏈表是否為空，為空則直接退出
	if (Head->next == NULL)
	{
		printf("current linkeflist is empty!\n");
		return;
	}

    printf("Stack Top->");
	// 從首結點開始遍歷
	while (Phead->next)
	{
		// 把頭結點的直接後繼作為新的頭結點
		Phead = Phead->next;

        // 輸出頭結點的直接後繼的數據域
        printf("%d->", Phead->data);

		// 判斷是否到達尾結點，尾結點的next指針是指向首結點的地址
		if (Phead->next == Head->next)
		{
			break;
		}
	}

    printf("Stack Bottom\n");

    return;
}

int main()
{
    //創立棧頂連接的頭結點
    ChaStack_t *Head = ChainStack_Create();

    //入棧
    ChainStack_Push(Head, 10);
    ChainStack_Push(Head, 20);
    ChainStack_Push(Head, 30);
    printf("\n");

    //遍歷
    ChainStack_Printf(Head);

    //出棧
    ChainStack_Pop(Head);
    ChainStack_Pop(Head);
    printf("\n");

    //遍歷
    ChainStack_Printf(Head);

    ChainStack_Pop(Head);
    ChainStack_Pop(Head);


    return 0;
}

結果驗證：

image


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • kube-state-metrics和cAdvisorc結合使用的好處
    kube-state-metrics是Kubernetes監控系統的重要組成部分，它提供了對集群中對象狀態的實時監控。具體來說，kube-state-metrics通過監聽API Server生成有關資源對象的狀態指標，比如Deployment、Node、Pod等。kube-state-metric ...
  • 習題---利用兩個棧實現隊列的“入隊”和“出隊”
    利用兩個棧進行實現隊列的入隊和出隊操作 題目： 解題分析： ​ 該題目需要藉助兩個棧來實現隊列的“入隊”和“出隊”，並封裝好了三個對應的函數。我們需要註意的是棧的特點是“先進後出",與隊列的”先進先出“的輸出並不一致。所以，我們要利用棧來輸出正常排序的序列，需要藉助類似取反的原理，例如 ！false ...
  • 能源管理系統EMS與IEC61850
    隊列 原理介紹： ​ 隊列（Queue）和棧類似，相同點是都屬於線性結構，不同點是棧遵循“後進先出”原則，而隊列遵循“*先進先出*”的原則，也被稱為“FIFO”結構，就是“First Input First Output” ​ 數據結構中的隊列的兩端都允許操作，只不過要求數據只能從隊列的一端插入，從 ...
  • 以鏈表為基礎實現鏈式隊列
    數據結構 鏈式隊列 以鏈表為基礎實現鏈式隊列 1.思路： 如果打算以鏈表作為基礎來實現隊列的操作，可以避免記憶體浪費以及避免記憶體成片移動，只需要確定隊頭和隊尾即可，一般把鏈表頭部作為隊頭，可以實現頭刪，把鏈表尾部作為隊尾，可以實現尾插。 2.圖示： 3.代碼： /******************* ...
  • Linux啟動過程以及7種運行級別
    題目： ​ 輸入一個包括 '(' 和 ')' 的字元串string ，判斷字元串是否有效。要求設計演算法實現檢查字元串是否有效，有效的字元串需滿足以下條件： A. 左括弧必須用相同類型的右括弧閉合。 B. 左括弧必須以正確的順序閉合。 C. 每個右括弧都有一個對應的相同類型的左括弧。 題目分析： ​ ...
  • Centos7使用Nginx配置HTTPS正向代理
    Nginx預設安裝只支持代理HTTP, 不支持代理 HTTPS, 如果需要支持HTTPS需要在Nginx編譯時加入 ngx_http_proxy_connect_module. ...
  • 雙向迴圈鏈表的增刪改查功能
    數據結構 雙向迴圈鏈表 雙向迴圈鏈表的增刪改查 /***************************************************************************************************************** * * file na ...
  • 順序棧習題
    題目： ​ 設計一個進位轉換程式，使用順序棧設計一個把十進位數轉換為十六進位數的介面，實現當通過鍵盤輸入一個非負的十進位數，可以在終端輸出對應的十六進位數。 例如： 100 --> 0x64 --> 100%16 = 4 --> 100/16 = 6 6%16 = 6 題目分析： ​ 該題需要對用戶 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類