堆疊

堆疊的概念及結構

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，

壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂

出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂

堆疊的實作

堆疊的實作一般可以使用陣列或者鏈表實作，相對而言陣列的結構實作更優一些，因為陣列在尾上插入資料的代價比較小，

堆疊節點

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;       //堆疊頂
	int capacity;  //容量
}ST;

堆疊初始化函式StackInit

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

入堆疊函式StackPush

//入堆疊函式
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,newcapacity*sizeof(STDataType));
		if (!tmp)
		{
			printf("relloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//擴容擴好以后把資料給過去
	ps->a[ps->top] = x;
	ps->top++;
}

提前把堆疊銷毀函式寫好

堆疊銷毀函式StackDestroy

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

出堆疊函式StackPop

//出堆疊函式
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;		
}

判斷堆疊是否為空函式StackEmpty

//判斷堆疊是否為空函式
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

取堆疊頂元素函式StackTop

//取堆疊頂部函式
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

堆疊大小函式StackSize

//堆疊大小函式
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

遍歷堆疊

while (!StackEmpty(&stack))
	{
		printf("%d ", StackTop(&stack));
		StackPop(&stack);
	}

代碼

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;

//堆疊初始化函式
extern void StackInit(ST* ps);
//堆疊銷毀函式
extern void StackDestroy(ST* ps);
//入堆疊函式
extern void StackPush(ST* ps, STDataType x);
//出堆疊函式
extern void StackPop(ST* ps);
//取堆疊頂部函式
extern STDataType StackTop(ST* ps);
//堆疊大小函式
extern int StackSize(ST* ps);
//判斷堆疊是否為空函式
extern bool StackEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"


//堆疊初始化函式
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
//入堆疊函式
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,newcapacity*sizeof(STDataType));
		if (!tmp)
		{
			printf("relloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//擴容擴好以后把資料給過去
	ps->a[ps->top] = x;
	ps->top++;
}
//堆疊銷毀函式
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
//出堆疊函式
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;		
}
//取堆疊頂部函式
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
//堆疊大小函式
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
//判斷堆疊是否為空函式
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void Test1()
{
	ST stack = { 0 };
	StackInit(&stack);
	StackPush(&stack, 1);
	StackPush(&stack, 2);
	StackPush(&stack, 3);
	StackPush(&stack, 4);
	//遍歷堆疊
	while (!StackEmpty(&stack))
	{
		printf("%d ", StackTop(&stack));
		StackPop(&stack);
	}
	printf("\n");
	StackDestroy(&stack);
}

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

練習

例1有效的括號

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;       //堆疊頂
	int capacity;  //容量
}ST;


//堆疊初始化函式
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->capacity = ps->top = 0;
}
//入堆疊函式
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,newcapacity*sizeof(STDataType));
		if (!tmp)
		{
			printf("relloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//擴容擴好以后把資料給過去
	ps->a[ps->top] = x;
	ps->top++;
}
//判斷堆疊是否為空函式
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//取堆疊頂部函式
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
//出堆疊函式
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;		
}
bool isValid(char * s){
    ST st = {0};
    StackInit(&st);
    while(*s)
    {
        //如果是左括號就入堆疊
        if(*s == '(' 
        || *s == '{' 
        || *s == '[')
        {
            //入堆疊
            StackPush(&st,*s);
            s++;
        }
        else
        {     
           if(StackEmpty(&st))     
           {
                StackDestroy(&st);
                return false;
           }
           //出堆疊
           STDataType tmp = StackTop(&st);
           StackPop(&st);
           if(*s == '}' && tmp != '{'
           || *s == ']' && tmp != '['
           || *s == ')' && tmp != '(')
           {
               StackDestroy(&st);
               return false;
           }           
           else
           {
               s++;
           }           
        }
    }
    //如果堆疊不是空說明還有左括號
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/342266.html

標籤：其他

上一篇：《演算法競賽中的初等數論》（五）正文 0x50篩法（ACM / OI / MO）（十五萬字符數論書）

下一篇：常用字串函式

演算法開啟小碼農堆疊血脈

堆疊