当前位置：首页 > article >正文

Go数据机构----栈与队列

article 2024/11/10 11:19:45

一、栈Stack和队列Queue

我们日常生活中，都需要将物品排列，或者安排事情的先后顺序。更通俗地讲，我们买东西时，人太多的情况下，我们要排队，排队也有先后顺序，有些人早了点来，排完队就离开了，有些人晚一点，才刚刚进去人群排队。

数据是有顺序的，从数据 1 到数据 2，再到数据 3，和日常生活一样，我们需要放数据，也需要排列数据。

在计算机的世界里，会经常听见两种结构，栈（stack） 和 队列 (queue)。它们是一种收集数据的有序集合（Collection），只不过删除和访问数据的顺序不同。

栈：先进后出，先进队的数据最后才出来。在英文的意思里，stack 可以作为一叠的意思，这个排列是垂直的，你将一张纸放在另外一张纸上面，先放的纸肯定是最后才会被拿走，因为上面有一张纸挡住了它。
队列：先进先出，先进队的数据先出来。在英文的意思里，queue 和现实世界的排队意思一样，这个排列是水平的，先排先得。

现在我们尝试使用链表：（可连续和不连续的将数据与数据进行关联起来的结构），数组（连续的，可以按索引取值）来实现栈（Stack）和队列（Queue）

数组实现：能快速随机访问存储的元素，通过下标 index 访问，支持随机访问，查询速度快，但存在元素在数组空间中大量移动的操作，增删效率低。

链表实现：只支持顺序访问，在某些遍历操作中查询速度慢，但增删元素快。

二、实现数组栈ArrayStack

一种数组形式的下压栈：先进后出

主要实现采用可变长数组来实现：

//数组栈，先进后出
type ArrayStack struct{
	array []string //
}

因此对其进行对应的操作的实现：

package main

import "sync"

// 数组形式的下压栈
type ArrayStack struct {
	array []string   //底层切片
	size  int        //栈的元素数量
	lock  sync.Mutex //为了并发安全使用的锁
}


// 入栈
func (stack *ArrayStack) Push(v string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	//然后将元素放入数组最后面
	stack.array = append(stack.array, v)

	//此时栈中元素数量+1
	stack.size += 1
}


// 出栈操作
func (stack *ArrayStack) Pop() string {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	//首先必须进行对应的判断，栈空！！！
	if stack.size == 0 {
		panic("empty!!")
	}
	//栈顶元素
	v := stack.array[stack.size-1]
	//切片收缩，但可能占用的空间越来越大
	//stack.array=stack.array[0:stack.size-1]
	//创建新的数组，空间占用不会越来越大，但可能移动元素次数过多
	newArray := make([]string, stack.size-1, stack.size-1)
	for i := 0; i < stack.size-1; i++ {
		newArray[i] = stack.array[i]
	}
	stack.array = newArray
	//栈中元素数量-1
	stack.size = stack.size - 1
	return v
}

/*
元素出栈，会先加锁实现并发安全。
如果栈大小为0，那么不允许出栈，否则从数组的最后面拿出元素。
元素取出后:
如果切片偏移量向前移动 stack.array[0 : stack.size-1]，表明最后的元素已经不属于该数组了，数组变相的缩容了。此时，切片被缩容的部分并不会被回收，仍然占用着空间，所以空间复杂度较高，但操作的时间复杂度为：O(1)。
如果我们创建新的数组 newArray，然后把老数组的元素复制到新数组，就不会占用多余的空间，但移动次数过多，时间复杂度为：O(n)。
最后元素数量减一，并返回值。
*/
//获取栈顶元素
func (stack *ArrayStack) Peek() string {
	//栈中元素已空
	if stack.size == 0 {
		panic("empty!!")
	}
	//栈顶元素值
	v := stack.array[stack.size-1]
	return v
}

// 获取栈大小和判断是否为空
// 栈大小
func (stack *ArrayStack) Size() int {
	return stack.size
}

// 栈是都为空
func (stack *ArrayStack) IsEmpty() int {
	return stack.size
}

最后进行测试的实现

func main() {
	arrayStack := new(ArrayStack)
	arrayStack.Push("1")
	arrayStack.Push("2")
	arrayStack.Push("3")
	fmt.Println("size:", arrayStack.Size()) //获取大小
	fmt.Println("Pop操作：", arrayStack.Pop()) //输出出栈的元素
	fmt.Println("size:", arrayStack.Size())
	arrayStack.Push("4")
}