快捷導航

C++詳解鏈棧的實現(xiàn)

更新時間：2022年06月25日 08:54:03 作者：肩上風騁

今天我們學習的是鏈棧，也就是說棧的鏈式結(jié)構(gòu)，我們運用順序鏈的方式來實現(xiàn)。首先呢，鏈棧是不存在存儲空間滿的情況的，所以可以說它是個無底洞，然而我們之前學的順序棧是有額定空間的

鏈棧簡述

鏈棧從概念上看是鏈表和棧的結(jié)合，含有棧先進后出的特性，也具有鏈表的動態(tài)增加節(jié)點的特性，這里相當于在鏈表的基礎(chǔ)上增加只能從一端操作，且保持先進后出的特性。將頭節(jié)點所在的那端看作棧頂，頭節(jié)點后緊接著的節(jié)點所在的位置，即第一個存儲數(shù)據(jù)的節(jié)點所在的位置為出棧入棧的位置。

示例代碼

直接上代碼：

LinkStack.h

#pragma once
typedef struct LINKNODE {
	struct LINKNODE *pNext;
}LinkNode;
class LinkStack
{
public:
	LinkStack();
	~LinkStack();
	void pushLinkStack(LinkNode *data);
	void popLinkStack();
	LinkNode *getTopLinkStack();
	int getSizeLinkStack();
	void clearStack();
private:
	//這里可以不定義該類類型的指針,該類類型變量定義后只能使用單獨的初始化函數(shù)初始化，
	//不能用構(gòu)造函數(shù)，會造成循環(huán)調(diào)用構(gòu)造函數(shù)的死循環(huán)中
//	LinkStack *m_LinkStack;
	LinkNode m_head;
	int m_size;
};

LinkStack.cpp

#include "LinkStack.h"
LinkStack::LinkStack()
{
	m_size = 0;
}
LinkStack::~LinkStack()
{
}
void LinkStack::pushLinkStack(LinkNode * data)
{
	if (data == nullptr)
	{
		return;
	}
	data->pNext = m_head.pNext;
	m_head.pNext = data;
	m_size++;
}
void LinkStack::popLinkStack()
{
	LinkNode *pDel = m_head.pNext;
	m_head.pNext = pDel->pNext;
	m_size--;
}
LinkNode * LinkStack::getTopLinkStack()
{
	return m_head.pNext;
}
int LinkStack::getSizeLinkStack()
{
	return m_size;
}
void LinkStack::clearStack()
{
	m_head.pNext = nullptr;
	m_size = 0;
}

main.cpp

#include <iostream>
#include "LinkStack.h"
using namespace std;
typedef struct PERSON 
{
	LinkNode  node;
	char name[64];
	int age;
}Person;
void test() 
{
	LinkStack *pLinkStack = new LinkStack;
	Person p1, p2, p3,p4,p5;
	strcpy_s(p1.name,"hudh");
	strcpy_s(p2.name,"呼呼");
	strcpy_s(p3.name,"jidi");
	strcpy_s(p4.name, "hus");
	strcpy_s(p5.name, "akios");
	p1.age = 34;
	p2.age = 45;
	p3.age = 67;
	p4.age = 67;
	p5.age = 78;
	pLinkStack->pushLinkStack((LinkNode*)&p1);
	pLinkStack->pushLinkStack((LinkNode*)&p2);
	pLinkStack->pushLinkStack((LinkNode*)&p3);
	pLinkStack->pushLinkStack((LinkNode*)&p4);
	pLinkStack->pushLinkStack((LinkNode*)&p5);
	while (pLinkStack->getSizeLinkStack() > 0) 
	{
		Person *pData = (Person*)pLinkStack->getTopLinkStack();
		cout << "name: " << pData->name << " age:" << pData->age << endl;
		pLinkStack->popLinkStack();
	}
	delete pLinkStack;
	pLinkStack = nullptr;
} 
int main()
{
	test();
	return 0;
}
// 運行程序: Ctrl + F5 或調(diào)試 >“開始執(zhí)行(不調(diào)試)”菜單
// 調(diào)試程序: F5 或調(diào)試 >“開始調(diào)試”菜單
// 入門使用技巧: 
//   1. 使用解決方案資源管理器窗口添加/管理文件
//   2. 使用團隊資源管理器窗口連接到源代碼管理
//   3. 使用輸出窗口查看生成輸出和其他消息
//   4. 使用錯誤列表窗口查看錯誤
//   5. 轉(zhuǎn)到“項目”>“添加新項”以創(chuàng)建新的代碼文件，或轉(zhuǎn)到“項目”>“添加現(xiàn)有項”以將現(xiàn)有代碼文件添加到項目
//   6. 將來，若要再次打開此項目，請轉(zhuǎn)到“文件”>“打開”>“項目”并選擇 .sln 文件