【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列（棧篇）

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列（棧篇）。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

1.棧的概念及結(jié)構(gòu)

2.棧的實(shí)現(xiàn)

2.1棧的結(jié)構(gòu)體定義

2.2棧的常用接口函數(shù)

??棧的初始化

??插入數(shù)據(jù)

??刪除數(shù)據(jù)

??取棧頂元素

??判斷棧是否為空

??計(jì)算棧的大小

??棧的銷毀

2.3完整的代碼

?3.與棧有關(guān)的面試題

1.棧的概念及結(jié)構(gòu)

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

【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列（棧篇）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),開發(fā)語言

2.棧的實(shí)現(xiàn)

棧和順序表比較相似，學(xué)習(xí)了順序表后，你會發(fā)現(xiàn)棧其實(shí)非常簡單。下面就讓我們一起來學(xué)習(xí)吧！

2.1棧的結(jié)構(gòu)體定義

下面是定長的靜態(tài)棧的結(jié)構(gòu)，實(shí)際中一般不實(shí)用，所以我們主要實(shí)現(xiàn)下面的支持動態(tài)增長的棧

typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType a[N];
 int top; // 棧頂
}ST;

支持動態(tài)增長的棧

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

這里的top表示棧頂元素的位置，capacity表示棧的容量，a是一個(gè)指針，用于接收動態(tài)內(nèi)存開辟數(shù)組的地址。

2.2棧的常用接口函數(shù)

下面是棧常用到的一些接口函數(shù)的聲明。

//初始化
void StackInit(ST* ps);
//銷毀
void StackDestroy(ST* ps);
//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x);
//刪除數(shù)據(jù)
void StackPop(ST* ps);
//取棧頂元素
STDataType StackTop(ST* ps);
//判斷是否為空
bool StackEmpty(ST* ps);
//計(jì)算大小
int StackSize(ST* ps);

棧的初始化

使用斷言(assert)確認(rèn)傳入的指針不為空。，然后將數(shù)組指針(a)設(shè)置為NULL，棧頂元素位置(top)設(shè)置為0，棧的容量(capacity)設(shè)置為0，完成棧的初始化操作。

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

?在定義完SL型結(jié)構(gòu)體后，就要調(diào)用這個(gè)函數(shù)對棧進(jìn)行初始化。

插入數(shù)據(jù)

這里的插入數(shù)據(jù)指的是壓棧，如果棧已滿(即棧頂位置等于棧的容量)，則重新分配內(nèi)存空間來擴(kuò)大棧的容量。新容量的計(jì)算為原容量的兩倍，如果原容量為0則設(shè)置為4。

//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果棧已滿，則重新分配內(nèi)存空間，擴(kuò)大容量
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//將數(shù)據(jù)x插入到棧頂，并更新棧頂位置
	ps->a[ps->top] = x;
	ps->top++;
}

刪除數(shù)據(jù)

這步操作較為簡單，將棧頂位置(ps->top)減1即可，表示刪除棧頂元素。

//刪除數(shù)據(jù)
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;  // 將棧頂位置減1，表示刪除棧頂元素
}

取棧頂元素

注意棧頂元素?cái)?shù)組編號是 top-1,然后返回該數(shù)組元素即可。

//取棧頂元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}

判斷棧是否為空

如果top等于0，表示數(shù)組還沒有存元素，棧就是空的。

//判斷是否為空
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

計(jì)算棧的大小

因?yàn)閠op就是棧中元素的個(gè)數(shù)，所以直接返回top即可。

//計(jì)算大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

棧的銷毀

使用free函數(shù)釋放棧的數(shù)組內(nèi)存空間(ps->a)。然后，將數(shù)組指針(ps->a)置為NULL，表示不再指向有效的內(nèi)存空間。最后，將棧的頂部位置(ps->top)和容量(ps->capacity)都置為0，完成棧的銷毀操作。

//銷毀
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a); // 釋放棧的數(shù)組內(nèi)存空間
	ps->a = NULL; // 將數(shù)組指針置為NULL
	ps->top = ps->capacity = 0; // 將棧的頂部位置和容量都置為0
}

?在不再需要使用棧時(shí)，可以調(diào)用StackDestroy函數(shù)進(jìn)行棧的銷毀，以釋放棧所占用的內(nèi)存空間。

2.3完整的代碼

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void TestSatck()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPush(&st, 6);
	
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");

	StackDestroy(&st);
}

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

?Stack.h文件

#pragma once

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


typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化
void StackInit(ST* ps);
//銷毀
void StackDestroy(ST* ps);
//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x);
//刪除數(shù)據(jù)
void StackPop(ST* ps);
//取棧頂元素
STDataType StackTop(ST* ps);
//判斷是否為空
bool StackEmpty(ST* ps);
//計(jì)算大小
int StackSize(ST* ps);

Stack.c文件

#include"Stack.h"

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//銷毀
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a); // 釋放棧的數(shù)組內(nèi)存空間
	ps->a = NULL; // 將數(shù)組指針置為NULL
	ps->top = ps->capacity = 0; // 將棧的頂部位置和容量都置為0
}

//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	// // 如果棧已滿，則重新分配內(nèi)存空間，擴(kuò)大容量
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//將數(shù)據(jù)x插入到棧頂，并更新棧頂位置
	ps->a[ps->top] = x;
	ps->top++;
}

//刪除數(shù)據(jù)
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;  // 將棧頂位置減1，表示刪除棧頂元素
}

//取棧頂元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}

//判斷是否為空
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

//計(jì)算大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

?3.與棧有關(guān)的面試題

1.一個(gè)棧的初始狀態(tài)為空。現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是（）。

A. 12345ABCDE

B. EDCBA54321

C. ABCDE12345

D. 54321EDCBA

棧的特點(diǎn)是先進(jìn)后出，根據(jù)給定的操作，將元素依次入棧，然后再依次出棧，元素出棧的順序應(yīng)該是如下所示：

EDCBA54321

根據(jù)出棧的順序可知，最后入棧的元素E最先出棧，然后是D、C、B、A、5、4、3、2、1。因此，元素出棧的順序是EDCBA54321。選項(xiàng)B)符合題目描述的操作結(jié)果。

2.若進(jìn)棧序列為 1,2,3,4 ，進(jìn)棧過程中可以出棧，則下列不可能的一個(gè)出棧序列是（）

A. 1,4,3,2

B. 2,3,4,1

C. 3,1,4,2

D. 3,4,2,1

根據(jù)排除法可以發(fā)現(xiàn)C項(xiàng)是不可能的，要想3先出棧，則1，2，3必須都先入棧，然后將3進(jìn)行出棧，但是C項(xiàng)中第2個(gè)出棧的元素是1，而2必須在1之前出棧，因此C項(xiàng)錯(cuò)誤。

?括號匹配

原題鏈接：力扣

【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列（棧篇）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),開發(fā)語言

?思路：遍歷字符串s中的每個(gè)括號，如果是左括號就入棧，如果是右括號就出棧，并且互相比較。文章來源地址http://www.zghlxwxcb.cn/news/detail-519133.html

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化
void StackInit(ST* ps);
//銷毀
void StackDestroy(ST* ps);
//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x);
//刪除數(shù)據(jù)
void StackPop(ST* ps);
//取棧頂元素
STDataType StackTop(ST* ps);
//判斷是否為空
bool StackEmpty(ST* ps);
//計(jì)算大小

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//銷毀
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

//刪除數(shù)據(jù)
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//取棧頂元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}

//判斷是否為空
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

//計(jì)算大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            STDataType top =StackTop(&st);
            StackPop(&st);
            if((top=='{'&&*s=='}')
            ||(top=='['&&*s==']')
            ||(top=='('&&*s==')'))
            {
                ++s;
            }
            else
            { 
               
                StackDestroy(&st);
                return false;
            }
        }
    }
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列（棧篇）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！