Golang實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)Stack(堆棧)的示例詳解

更新時(shí)間：2023年04月13日 09:51:03 作者：陪我去看海

在計(jì)算機(jī)科學(xué)中，stack（棧）是一種基本的數(shù)據(jù)結(jié)構(gòu)，它是一種線性結(jié)構(gòu),具有后進(jìn)先出（Last In First Out）的特點(diǎn)。本文將通過(guò)Golang實(shí)現(xiàn)堆棧，需要的可以參考一下

前言

始于此篇，為了學(xué)習(xí) Golang 基礎(chǔ)，采用了使用 Golang 實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)，以此來(lái)和 Golang 交朋友，今天的主題就是把Stack介紹給Golang認(rèn)識(shí)

源碼：Stack

介紹Stack

在計(jì)算機(jī)科學(xué)中，stack（棧）是一種基本的數(shù)據(jù)結(jié)構(gòu)，它是一種線性結(jié)構(gòu),具有后進(jìn)先出（Last In First Out）的特點(diǎn)。

上述是通過(guò)對(duì) ChatGPT 提問：數(shù)據(jù)結(jié)構(gòu)stack。所得到的答案，我們這里拿出這句話的關(guān)鍵詞：線性結(jié)構(gòu),后進(jìn)先出。了解之后它的特性之后，應(yīng)該如何實(shí)現(xiàn)呢，它應(yīng)該包含哪些操作才叫stack呢？

通過(guò)ChatGPT的回答，我們可以知道我們需要實(shí)現(xiàn)的stack包含以下方法：

Push
Pop
Peek
Len
Cap
Clear

那就開始吧！

Stack

在 Golang 中，使用 struct結(jié)構(gòu)體可以模擬出棧的結(jié)構(gòu)，分別有存儲(chǔ)元素的空間，棧的長(zhǎng)度，棧的容量

type Element interface{}

type Stack struct {
	elements []Element
	top   int // 棧頂指針
	cap      int // 容量
}

Push

作用：Push 方法就是往stack的存儲(chǔ)區(qū)域壓入新的元素

// Push
func (stack *Stack) Push(element Element) (err error) {
	// top == cap時(shí)，棧滿
	if stack.top >= stack.cap {
		return errors.New("the stack is full")
	}
	stack.elements[stack.top] = element
	stack.top++
	return nil
}

Pop

作用：Pop 方法是取出棧頂元素，并且在存儲(chǔ)區(qū)域內(nèi)刪除

// Pop
func (stack *Stack) Pop() (ele Element, err error){
	// top == 0時(shí)，?？?
	if stack.top <= 0 {
		return nil, errors.New("the stack is empty")
	}
	ele = stack.elements[stack.top]
	// 在棧中清除當(dāng)前元素
	stack.elements = append(stack.elements, stack.elements[:stack.top], stack.elements[stack.top+1:])
	stack.top--
	return ele, nil
}

Peek

作用：Peek 方法就是返回棧頂?shù)闹?，但是不刪除存儲(chǔ)區(qū)域的元素

// Peek
func (stack *Stack) Peek() (ele Element, err error){
	if stack.top <= 0 {
		return nil, errors.New("the stack is empty")
	}
	ele = stack.elements[stack.top]
	return ele, nil
}

Len & Cap & Clear

Len：返回棧的存儲(chǔ)的元素個(gè)數(shù)
Cap：當(dāng)前棧的容量
Clear：將棧清空

// Len
func (stack *Stack) Len() int{
	return stack.top
}

// Cap
func (stack *Stack) Cap() int{
	return stack.cap
}

// Clear
func (stack *Stack) Clear() {
	if stack.top <= 0 {
		return
	}
	// 重新分配一個(gè)空切片
	stack.elements = stack.elements[:0]
	stack.top = 0
}

為了方便使用，還可以提供一個(gè)創(chuàng)建棧的方法：NewStack

NewStack

// 初始化棧
func NewStack(cap int) *Stack {
	elements := make([]Element, cap)
	return &Stack{
		elements: elements,
		top:   0,
		cap:      cap,
	}
}

使用

package main

import "fmt"

func main() {
	stack := NewStack(5)
	for i := 0; i < 4; i++ {
		var ele Element = i
		stack.Push(ele)
	}

	element, _ := stack.Pop()
	fmt.Println(element)

	peekEle, _ := stack.Peek()
	fmt.Println(peekEle)

	fmt.Println(stack.Len())
	fmt.Println(stack.Cap())

	stack.Clear()
}

以上就是Golang實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)Stack(堆棧)的示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Golang數(shù)據(jù)結(jié)構(gòu)Stack的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: