＜棧＞的概念&結構&實現(xiàn)【C語言版】-創(chuàng)新互聯(lián)

成都創(chuàng)新互聯(lián)公司堅信：善待客戶，將會成為終身客戶。我們能堅持多年，是因為我們一直可值得信賴。我們從不忽悠初訪客戶，我們用心做好本職工作，不忘初心，方得始終。10余年網站建設經驗成都創(chuàng)新互聯(lián)公司是成都老牌網站營銷服務商,為您提供成都網站設計、做網站、成都外貿網站建設公司、網站設計、H5場景定制、網站制作、品牌網站建設、小程序設計服務,給眾多知名企業(yè)提供過好品質的建站服務。1.棧的概念及結構

棧存儲數(shù)據的方式跟數(shù)組一樣，都是將元素排成一行。只不過它還有以下 3 條約束。

● 只能在末尾插入數(shù)據。
● 只能讀取末尾的數(shù)據。
● 只能移除末尾的數(shù)據。

你可以將?？闯梢化B碟子：你只能看到最頂端那只碟子的碟面，其他都看不到。另外，要加碟子只能往上加，不能往中間塞，要拿碟子只能從上面拿，不能從中間拿（至少你不應該這么做）。絕大部分計算機科學家都把棧的末尾稱為棧頂，把棧的開頭稱為棧底。

盡管這些約束看上去令人很拘束，但很快你就會發(fā)現(xiàn)它們帶來的好處。

我們先從一個空棧開始演示。

往棧里插入數(shù)據，也叫作壓棧。你可以想象把一個碟子壓在其他碟子上的畫面。

首先，將 5 壓入棧中。

接著，將 3 壓入棧中。

再將 0 壓入棧中。

注意，每次壓棧都是把數(shù)據加到棧頂（也就是棧的末尾）。如果想把 0 插入到棧底或中間，那是不允許的，因為這就是棧的特性：只能在末尾插入數(shù)據。

從棧頂移除數(shù)據叫作出棧。這也是棧的限制：只能移除末尾的數(shù)據。

來把棧中的一些數(shù)據彈出。

首先，彈出 0。?

接著，彈出 3。

這就剩下 5了。?

總結：

棧是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據元素遵守后進先出LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據也在棧頂。?

2.棧的實現(xiàn)

棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結構實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據的代價比較小。

2.1棧的結構定義
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;  //動態(tài)開辟數(shù)組
	int capacity; //記錄棧的容量大小
	int top; //記錄棧頂?shù)奈恢?}Stack;
2.2函數(shù)接口的實現(xiàn)

首先是在Stack.h文件中進行函數(shù)聲明

Stack.h
#pragma once
#include#include#include
#includetypedef int STDataType;

typedef struct Stack
{
	STDataType* a;  //動態(tài)開辟數(shù)組
	int capacity; //記錄棧的容量大小
	int top; //記錄棧頂?shù)奈恢?}Stack;

//棧的初始化
void StackInit(Stack* ps);
//釋放動態(tài)開辟的內存
void StackDestroy(Stack* ps);
//壓棧
void StackPush(Stack* ps, STDataType data);
//出棧
void StackPop(Stack* ps);
//讀取棧頂?shù)脑?STDataType StackTop(Stack* ps);
//判斷棧是否為空
bool StackEmpty(Stack* ps);
//棧存儲的數(shù)據個數(shù)
int StackSize(Stack* ps);

在Stack.c文件中進行函數(shù)的定義

Stack.c
#define _CRT_SECURE_NO_DEPRECATE 1
#include"Stack.h"

void StackInit(Stack* ps)
{
	assert(ps);
	//初始化時，可附初值，也可置空
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	//若并未對ps->a申請內存，則無需釋放
	if (ps->capacity == 0)
		return;
	//釋放
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
	assert(ps);
	//若容量大小等于數(shù)據個數(shù)，則說明棧已滿，需擴容
	if (ps->capacity == ps->top)
	{
		//若為第一次擴容，則大小為4，否則每次擴大2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//壓棧
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//出棧
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//返回棧頂?shù)臄?shù)據
	return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	//返回top
	return ps->top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網頁標題：＜棧＞的概念&結構&實現(xiàn)【C語言版】-創(chuàng)新互聯(lián)
本文地址：http://bm7419.com/article8/igiip.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網站制作、響應式網站、關鍵詞優(yōu)化、外貿建站、做網站、App開發(fā)

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)

外貿網站制作