棧（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
  • 如何基於surging跨網關跨語言進行緩存降級
    基於.NET Framework 4.8 開發的深度學習模型部署測試平臺，提供了YOLO框架的主流系列模型，包括YOLOv8~v9，以及其系列下的Det、Seg、Pose、Obb、Cls等應用場景，同時支持圖像與視頻檢測。模型部署引擎使用的是OpenVINO™、TensorRT、ONNX runti... ...
  • 十年沉澱，重啟開發之路
    十年沉澱，重啟開發之路 十年前，我沉浸在開發的海洋中，每日與代碼為伍，與演算法共舞。那時的我，滿懷激情，對技術的追求近乎狂熱。然而，隨著歲月的流逝，生活的忙碌逐漸占據了我的大部分時間，讓我無暇顧及技術的沉澱與積累。 十年間，我經歷了職業生涯的起伏和變遷。從初出茅廬的菜鳥到逐漸嶄露頭角的開發者，我見證了 ...
  • C#.NET體系圖文概述—2024最全總結
    C# 是一種簡單、現代、面向對象和類型安全的編程語言。.NET 是由 Microsoft 創建的開發平臺，平臺包含了語言規範、工具、運行，支持開發各種應用，如Web、移動、桌面等。.NET框架有多個實現，如.NET Framework、.NET Core（及後續的.NET 5+版本），以及社區版本M... ...
  • 班級擂臺（光榮）榜 - 極簡教育小工具
    前言 本文介紹瞭如何使用三菱提供的MX Component插件實現對三菱PLC軟元件數據的讀寫，記錄了使用電腦模擬，模擬PLC，直至完成測試的詳細流程，並重點介紹了在這個過程中的易錯點，供參考。 用到的軟體： 1. PLC開發編程環境GX Works2，GX Works2下載鏈接 https:// ...
  • web server apache tomcat11-31-websocket
    前言 整理這個官方翻譯的系列，原因是網上大部分的 tomcat 版本比較舊，此版本為 v11 最新的版本。 開源項目 從零手寫實現 tomcat minicat 別稱【嗅虎】心有猛虎，輕嗅薔薇。 系列文章 web server apache tomcat11-01-官方文檔入門介紹 web serv ...
  • day31-jQuery
    1、jQuery介紹 jQuery是什麼 jQuery是一個快速、簡潔的JavaScript框架，是繼Prototype之後又一個優秀的JavaScript代碼庫（或JavaScript框架）。jQuery設計的宗旨是“write Less，Do More”，即倡導寫更少的代碼，做更多的事情。它封裝 ...
  • aardio爬蟲) 實戰篇：逆向有道翻譯web介面
    前言 之前的文章把js引擎(aardio封裝庫) 微軟開源的js引擎(ChakraCore))寫好了，這篇文章整點js代碼來測一下bug。測試網站：https://fanyi.youdao.com/index.html#/ 逆向思路 逆向思路可以看有道翻譯js逆向（MD5加密，AES加密）附完整源碼 ...
  • 面試官：這就是你理解的Java多線程基礎？
    引言 現代的操作系統（Windows，Linux，Mac OS）等都可以同時打開多個軟體（任務），這些軟體在我們的感知上是同時運行的，例如我們可以一邊瀏覽網頁，一邊聽音樂。而CPU執行代碼同一時間只能執行一條，但即使我們的電腦是單核CPU也可以同時運行多個任務，如下圖所示，這是因為我們的 CPU 的 ...
  • Python文本統計與分析從基礎到進階
    掌握使用Python進行文本英文統計的基本方法，並瞭解如何進一步優化和擴展這些方法，以應對更複雜的文本分析任務。 ...
  • Redis多數據源，看這篇就夠了
    背景 Redis多數據源常見的場景： 分區數據處理：當數據量增長時，單個Redis實例可能無法處理所有的數據。通過使用多個Redis數據源，可以將數據分區存儲在不同的實例中，使得數據處理更加高效。 多租戶應用程式：對於多租戶應用程式，每個租戶可以擁有自己的Redis數據源，以確保數據隔離和安全性。 ...
所有分類