logo头像

待到风起时,扬帆济沧海

栈和队列

本文于453天之前发表,文中内容可能已经过时。

栈概念

 栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。

 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。

 由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表。

 这里以羽毛球筒为例,羽毛球筒就是一个栈,刚开始羽毛球筒是空的,也就是空栈,然后我们一个一个放入羽毛球,也就是一个一个push进栈,当我们需要使用羽毛球的时候,从筒里面拿,也就是pop出栈,但是第一个拿到的羽毛球是我们最后放进去的。

操作流程示意图

1120165-20171129201940386-674535319.png

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
type Stack struct {
Array []interface{} //栈切片存储
}

func (stack *Stack) Push(value ...interface{}) {
stack.Array = append(stack.Array, value...)
}

//返回下一个元素
func (stack *Stack) Top() (value interface{}) {
if stack.Size() > 0 {
return stack.Array[stack.Size()-1]
}
return nil //read empty stack
}

//返回下一个元素,并从Stack移除元素
func (stack *Stack) Pop() interface{} {
if stack.Size() > 0 {
value := stack.Array[stack.Size()-1]
stack.Array = stack.Array[:stack.Size()-1]
return value
}
panic("Stack为空.") //read empty stack
}

//交换值
func (stack *Stack) Swap(other *Stack) {
switch {
case stack.Size() == 0 && other.Size() == 0:
return
case other.Size() == 0:
other.Array = stack.Array[:stack.Size()]
stack.Array = nil
case stack.Size() == 0:
stack.Array = other.Array
other.Array = nil
default:
stack.Array, other.Array = other.Array, stack.Array
}
return
}

//返回指定索引的元素
func (stack *Stack) Get(idx int) (value interface{}) {
if idx >= 0 && stack.Size() > 0 && stack.Size() > idx {
return stack.Array[idx]
}
return nil
}

//Stack的size
func (stack *Stack) Size() int {
return len(stack.Array)
}

栈-反转字符串

1
2
3
4
5
6
7
8
str := "hello,word"
ss := &stack.Stack{}
for _, v := range str {
ss.Push(string(v))
}
for ss.Size() > 0 {
fmt.Print(ss.Pop())
}

队列实现

队列其实和栈一样,只是队列是先进先出,那么只需要每次弹出第一个元素即可

1
2
3
4
5
6
7
8
9
//返回下一个元素,并从Stack移除元素
func (stack *Stack) Pop() interface{} {
if stack.Size() > 0 {
value := stack.Array[0]
stack.Array = stack.Array[1:]
return value
}
panic("Stack为空.") //read empty stack
}

总结

  1. 栈、队列(单向队列)、优先级队列通常是用来简化某些程序操作的数据结构,而不是主要作为存储数据的。
  2. 在这些数据结构中,只有一个数据项可以被访问。
  3. 栈允许在栈顶压入(插入)数据,在栈顶弹出(移除)数据,但是只能访问最后一个插入的数据项,也就是栈顶元素。
  4. 队列(单向队列)只能在队尾插入数据,对头删除数据,并且只能访问对头的数据。而且队列还可以实现循环队列,它基于数组,数组下标可以从数组末端绕回到数组的开始位置。
  5. 优先级队列是有序的插入数据,并且只能访问当前元素中优先级别最大(或最小)的元素。
  6. 这些数据结构都能由数组实现,但是可以用别的机制(链表、堆等数据结构)实现。

评论系统未开启,无法评论!