Skip to content

Latest commit

 

History

History
371 lines (317 loc) · 8.36 KB

栈和队列.md

File metadata and controls

371 lines (317 loc) · 8.36 KB
Raw

栈和队列

栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。

栈的特性：后进先出（Last In First Out），简写为LIFO

栈

栈的实现

我们主要实现栈的一下几个方法

  • getSize：栈的大小
  • isEmpty：栈是否为空
  • push：压栈
  • pop：出栈
  • peek：栈顶
  • toString：打印
class Stack: NSObject {
var stackArr = [Any]()

//栈的大小
func getSize() -> Int {
return stackArr.count
}
//栈是否为空
func isEmpty() -> Bool {
return stackArr.isEmpty
}
//压栈
func push(e:Any) {
stackArr.append(e)
}
//出栈
func pop() -> Any{
guard !stackArr.isEmpty else {
return (Any).self
}
let E = stackArr[stackArr.count - 1]
stackArr.removeLast()
return E
}
//栈顶
func peek() -> Any {
return stackArr[stackArr.count - 1]
}
//打印
func toString() ->String{
var res = "Stack: "
for (index,item) in stackArr.enumerated() {
if (index < stackArr.count - 1){
res.append("\(item),")
}
if (index == stackArr.count - 1){
res.append("\(item)")
}
}
return res
}


}

栈的使用：有效的括号

给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。

有效字符串需满足：

  • 1、左括号必须用相同类型的右括号闭合。
  • 2、左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

class Solution: NSObject {
let stack = Stack()
func isValid(_ s: String) -> Bool {
for c in s {
if (c == "(" || c == "[" || c == "{"){
stack.push(e: c)
}else{
//第一个如果不是上面的那三种情况直接return false
if stack.isEmpty() {
return false
}
//在出现第一个右括号的时候，一定有一个与之相对应的左括号，否则不符合规则；在出现第一个右括号，我们在栈中栈定元素，栈定元素应该是与右括号成对出现的，否则不符合规则
let topChar = stack.pop() as! Character
if (c == ")" && topChar != "("){
return false
}
if (c == "]" && topChar != "["){
return false
}
if (c == "}" && topChar != "{"){
return false
}
}

}
//在字符串遍历到最后，我们的栈应该是空的，因为左侧右侧成对出现便会被压出栈
return stack.isEmpty()
}
}

代码解析 上面这段逻辑代码我们就使用栈思想

  • 1、首先第一个字符必须是(、[、{中的一个，否则必定不符合规则，这也就是下面这段代码
if (c == "(" || c == "[" || c == "{"){
stack.push(e: c)
}else{
//第一个如果不是上面的那三种情况直接return false
if stack.isEmpty() {
return false
}
}
  • 2、在出现第一个右括号的时候，一定有一个与之相对应的左括号，否则不符合规则；在出现第一个右括号，我们在栈中栈定元素，栈定元素应该是与右括号成对出现的，否则不符合规则
let topChar = stack.pop() as! Character
if (c == ")" && topChar != "("){
return false
}
if (c == "]" && topChar != "["){
return false
}
if (c == "}" && topChar != "{"){
return false
}
  • 3、在字符串遍历到最后，我们的栈应该是空的，因为左侧右侧成对出现便会被压出栈

我们在写过代码以后可以在leetcode中进行验证，这一道题是leetcode的第20题。

队列

  • 队列，一种限定性的线性表。它只允许在表一端进行插入，而在表的另一端进行删除操作。
  • 队列是一种先进先出的数据结构
  • First In First Out(FIFO)
  • 只能从队尾添加元素，从队首取出元素

队列

队列的简单实现

class Queue: NSObject {
private var queueArr = [Any]()

//队列大小
func getSize() -> Int {
return queueArr.count
}
//入队
func enqueue(E:Any) {
queueArr.append(E)
}
//出队
func dequeue1() -> Any {
let res = queueArr[0]
queueArr.remove(at: 0)
return res
}
//打印
func toString() -> String {
var res = "Stack: "
for (index,item) in queueArr.enumerated() {
if (index < queueArr.count - 1){
res.append("\(item),")
}
if (index == queueArr.count - 1){
res.append("\(item)")
}
}

return res
}

}

对于添加队列，其实就是在队列的最后一位添加一个元素，算法复杂度为O(1) 但是删除队列，因为是删除的第一个元素其实就是走的一下这个算法，复杂度是O(n)

for index in 0..<queueArr.count-1 {
queueArr[index] = queueArr[index+1]
}

循环队列

将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

循环队列

来看看我们的具体实现吧

class LoopQueue: NSObject {
private var data = [String]()
private var front = 0,tail = 0;
private var size = 3 //初始的时候数组的长度空间

//队列中的元素
func getSize() -> Int {
// 注意此时getSize的逻辑:
// 如果tail >= front，非常简单，队列中的元素个数就是tail - front
// 如果tail < front，说明我们的循环队列"循环"起来了，此时，队列中的元素个数为：
// tail - front + data.count
//
// 也可以理解成，此时，data中没有元素的数目为front - tail,
// 整体元素个数就是 data.count - (front - tail) = data.count + tail - front
return tail >= front ? tail - front : tail - front + data.count;
}
//入队
func enqueue(E:String) {
//此时 队头 和 队尾 相同 我们需要对数组空间进行扩容，并且重新分配数组元素
if (tail + 1) % size == front {
//数组扩容
resize()
size = size * 2
}
//入队操作
if data.count <= tail {
data.append(E)
}else{
data[tail] = E
}

//队尾计算
tail = (tail + 1) % size

}
//出队
func dequeue() -> String {
let E = data[front]
//把出队的数据占位
data[front] = "nil"
front = (front + 1) % size
//数组缩容
if data.count <= size / 4
&& data.count > 0{
resize()
size = size / 2
}

return E
}

//数组调整
func resize() {
var newData = [String]()
for (index,_) in data.enumerated() {
let item = data[(index + front) % data.count]
if (item == "nil"){
continue
}
newData.append(item)
}
data = newData
front = 0
tail = newData.count
}


//打印
func toString() -> String {
var res = "LoopQueue: "
for (index,item) in data.enumerated() {
if (index < data.count - 1){
res.append("\(item),")
}
if (index == data.count - 1){
res.append("\(item)")
}
}
res.append(" ->tail")
return res
}
}

里面有三个注意点

  • 1、在出队的时候怎么处理
  • 2、在入队的时候怎么处理
  • 3、在数组重新调整的时候怎么处理
  • 4、在数组超级大的时候，在扩容数组的时候是否还是要全部重新调整顺序。这个时候应该是一部分一部分的调整数组的顺序，不要一次计算结束，不然太过于消耗性能

计算

我们说循环队列多好，还是要看实践的，我们来写两个简单的算法来计算两个时间差值，看看循环队列是否真的是节约了时间

import Foundation
extension Date {
/// 获取当前 毫秒级 时间戳 - 13位
var milliStamp : Int {
let timeInterval: TimeInterval = self.timeIntervalSince1970
let millisecond = CLongLong(round(timeInterval*1000))
return Int(millisecond)
}
}

//循环队列
let loopQuere = LoopQueue()
let startDate1 = Date().milliStamp
for index in 0..<100000{
loopQuere.enqueue(E: "\(index)")
if index % 2 == 1{
let _ = loopQuere.dequeue()
}

}
let endDate1 = Date().milliStamp
print("循环队列:\(endDate1 - startDate1)")


//线性队列
let quere = Queue()
let startDate2 = Date().milliStamp
for index in 0..<100000{
quere.enqueue(E: "\(index)")
if index % 2 == 1{
let _ = quere.dequeue()
}
}
let endDate2 = Date().milliStamp
print("线性队列:\(endDate2 - startDate1)")

在10万数量级的情况下，就相差的比较多了，如果更大的数量级，性能相差的更大

循环队列:118
线性队列:4318