数据结构笔记—栈和队列

定义

只能在表的一端(栈顶)进行插入和删除运算的线性表

逻辑结构

与线性表相同,仍为一对一关系

存储结构

用顺序栈或链栈存储均可,但以顺序栈更常见

运算规则

只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则

栈与一般线性表的区别

比较维度 一般线性表
逻辑结构 一对一 一对一
存储结构 顺序表、链表 顺序表、链表
运算规则 随机、顺序存取 ==后进先出==

实现方式

关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的不同而不同
基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等

定义一个栈

1
2
3
public struct Stack<T> {
fileprivate var stackData = [T]()
}

入栈

1
2
3
4
5
//struct 的实例方法中默认不能修改属性值 如果要修改 需要加上 mutating 关键字
// push
public mutating func push(_ element: T) {
stackData.append(element)
}

出栈

1
2
3
public mutating func pop() -> T? {
return stackData.popLast()// popLast() 删除并返回数组中的最后一个值
}

栈顶元素

1
2
3
4
//栈顶
public var top: T? {
return stackData.last //数组的最后一个值 及栈顶
}

栈判空

1
2
3
public var isEmpty: Bool {
return stackData.isEmpty
}

栈的应用举例:十进制转八进制

对于任意一个非负整数,打印出与其相等的对应八进制

1
2
3
4
5
6
7
public mutating func tenTransformEight(value:Int) {
var val = value
while val > 0 {
push(val % 8)
val = val / 8
}
}
1
2
3
4
5
6
7
var stack = Stack.init()

stack.tenTransformEight(value: 1348)

print(stack.popAll() ?? "")

//输出结果:2504

队列

定义

 队列是一种先进先出(FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素

未完待续。。。。

坚持原创,您的支持将鼓励我继续创作!