跟我一起学算法：数据结构和算法-栈-灵析社区

堆栈数据结构

什么是堆栈？

堆栈是一种线性数据结构，遵循特定的操作执行顺序。顺序可以是 LIFO（后进先出）或 FILO（先进后出）。LIFO 意味着最后插入的元素最先出现，而 FILO 意味着最先插入的元素最后出现。

现实生活中有很多堆栈的例子。考虑一个在食堂里盘子叠在一起的例子。位于顶部的盘子是第一个被移除的盘子，即放置在最底部位置的盘子在堆叠中保留最长的时间。因此，可以简单地看出遵循LIFO（后进先出）/FILO（先进后出）顺序。

为了实现栈，需要维护一个指向栈顶的指针，栈顶是最后插入的元素，因为我们只能访问栈顶的元素。

LIFO（后进先出）：

该策略规定最后插入的元素将首先出现。您可以将一堆相互叠放的盘子作为现实生活中的示例。我们最后放置的盘子位于顶部，并且由于我们移除了顶部的盘子，所以我们可以说最后放置的盘子最先出现。

堆栈的基本操作

为了在堆栈中进行操作，向我们提供了某些操作。

• push() 将一个元素插入栈中
• pop() 从堆栈中删除一个元素
• top() 返回栈顶元素。
• 如果堆栈为空，isEmpty()返回 true，否则返回 false。
• size() 返回堆栈的大小。

push

给栈里面添加一个元素, 如果栈满后, 则称为溢出条件

伪代码

 begin
  if stack is full
     return
  endif
 else  
  increment top
  stack[top] assign value
 end else
 end procedure

pop(弹出元素)

从栈中移除元素, 这些元素按照入栈的反方向一次出栈.

伪代码

 begin
  if stack is empty
     return
  endif
 else
  store value of stack[top]
  decrement top
  return value
 end else
 end procedure

Top (返回栈顶元素)

isEmpty:

判断栈是否为空,如果为空返回 true, 否则返回 false

实际理解堆栈

现实生活中有很多堆栈的例子。考虑一个简单的例子，在食堂里，盘子一个一个地叠在一起。位于顶部的盘子是第一个被移除的盘子，即放置在最底部位置的盘子在堆叠中保留最长的时间。因此，可以简单地看出遵循 LIFO/FILO 顺序。

复杂度

时间复杂度:

操作	复杂度
push()	O(1)
pop()	O(1)
isEmpty()	O(1)
size()	O(1)

堆栈类型：

• 固定大小堆栈：顾名思义，固定大小堆栈具有固定的大小，不能动态增长或收缩。如果堆栈已满并尝试向其中添加元素，则会发生溢出错误。如果堆栈为空并且尝试从中删除元素，则会发生下溢错误。
• 动态大小堆栈：动态大小堆栈可以动态增长或收缩。当堆栈已满时，它会自动增加其大小以容纳新元素，而当堆栈为空时，它会减少其大小。这种类型的堆栈是使用链表实现的，因为它允许轻松调整堆栈的大小。

除了这两种主要类型之外，堆栈还有其他几种变体，包括：

1. 中缀到后缀堆栈：这种类型的堆栈用于将中缀表达式转换为后缀表达式。
2. 表达式计算堆栈：这种类型的堆栈用于计算后缀表达式。
3. 递归堆栈：这种类型的堆栈用于跟踪计算机程序中的函数调用，并在函数返回时将控制权返回到正确的函数。
4. 内存管理堆栈：这种类型的堆栈用于存储计算机程序中程序计数器的值和寄存器的值，允许程序在函数返回时返回到先前的状态。
5. 平衡括号堆栈：这种类型的堆栈用于检查表达式中括号的平衡。
6. 撤消重做堆栈：这种类型的堆栈用于计算机程序中，允许用户撤消和重做操作。

栈的应用

• 中缀到后缀/前缀的转换
• 许多地方都有重做/撤消功能，例如编辑器、Photoshop。
• 网络浏览器中的前进和后退功能
• 用于许多算法，如 汉诺塔、股票跨度问题和直方图问题。
• 回溯是算法设计技术之一。回溯的一些例子包括骑士之旅问题、N-皇后问题、在迷宫中寻找出路以及所有这些问题中的类似国际象棋或西洋跳棋的问题，如果这种方式效率不高，我们会回到之前的问题状态并进入另一条道路。为了从当前状态返回，我们需要存储以前的状态，为此我们需要一个堆栈。
• 在内存管理中，任何现代计算机都使用堆栈作为运行目的的主要管理。计算机系统中运行的每个程序都有自己的内存分配
• 字符串反转也是栈的另一个应用。这里每个字符都被一一插入到堆栈中。因此，字符串的第一个字符位于堆栈底部，字符串的最后一个元素位于堆栈顶部。在堆栈上执行弹出操作后，我们得到一个相反顺序的字符串。
• 堆栈还有助于在计算机中实现函数调用。最后调用的函数总是最先完成。
• 堆栈还用于在文本编辑器中实现撤消/重做操作。

堆栈的实现

堆栈可以使用数组或链表来实现。

在基于数组的实现中，push 操作是通过递增顶部元素的索引并将新元素存储在该索引处来实现的。弹出操作是通过递减顶部元素的索引并返回存储在该索引处的值来实现的。

在基于链表的实现中，推送操作是通过使用新元素创建新节点并将当前顶节点的下一个指针设置为新节点来实现的。出栈操作是通过将当前顶节点的next指针设置为下一个节点并返回当前顶节点的值来实现的。

堆栈在计算机科学中通常用于各种应用，包括表达式求值、函数调用和内存管理。在表达式的计算中，堆栈可用于在处理操作数和运算符时存储它们。在函数调用中，堆栈可用于跟踪函数调用的顺序，并在函数返回时将控制权返回到正确的函数。在内存管理中，堆栈可用于存储计算机程序中的程序计数器的值和寄存器的值，从而允许程序在函数返回时返回到先前的状态。

总之，堆栈是一种按照 LIFO 原理运行的线性数据结构，可以使用数组或链表来实现。可以在堆栈上执行的基本操作包括入栈、出栈和查看，并且堆栈在计算机科学中常用于各种应用，包括表达式求值、函数调用和内存管理。有两种方法实现一个堆栈

• 使用数组
• 使用链表

使用数组实现堆栈

 from sys import maxsize
 ​
 def createStack():
   stack = []
   return stack
 ​
 def isEmpty(stack):
   return len(stack) == 0
 ​
 def push(stack, item):
   stack.append(item)
   print(item + " pushed to stack ")
   
 def pop(stack):
   if (isEmpty(stack)):
     return str(-maxsize -1) # 返回负无穷大
   
   return stack.pop()
 ​
 def peek(stack):
   if (isEmpty(stack)):
     return str(-maxsize -1) # 返回负无穷大
   return stack[len(stack) - 1]
 ​
 stack = createStack()
 push(stack, str(10))
 push(stack, str(20))
 push(stack, str(30))
 print(pop(stack) + " popped from stack")
 ​

数组实现的优点：

• 易于实施。
• 由于不涉及指针，因此节省了内存。

数组实现的缺点：

• 它不是动态的，即它不会根据运行时的需要而增长和收缩。[但是对于动态大小的数组，例如 C++ 中的向量、Python 中的列表、Java 中的 ArrayList，堆栈也可以随着数组实现而增长和收缩]。
• 堆栈的总大小必须事先定义。

使用链表实现堆栈

 class StackNode:
   
     # Constructor to initialize a node
     def __init__(self, data):
         self.data = data
         self.next = None
   
   
 class Stack:
   
     # Constructor to initialize the root of linked list
     def __init__(self):
         self.root = None
   
     def isEmpty(self):
         return True if self.root is None else False
   
     def push(self, data):
         newNode = StackNode(data)
         newNode.next = self.root
         self.root = newNode
         print ("% d pushed to stack" % (data))
   
     def pop(self):
         if (self.isEmpty()):
             return float("-inf")
         temp = self.root
         self.root = self.root.next
         popped = temp.data
         return popped
   
     def peek(self):
         if self.isEmpty():
             return float("-inf")
         return self.root.data
   
 stack = Stack()
 stack.push(10)
 stack.push(20)
 stack.push(30)
   
 print ("% d popped from stack" % (stack.pop()))
 print ("Top element is % d " % (stack.peek()))

堆栈的优点：

• 易于实现： 堆栈数据结构很容易使用数组或链表来实现，其操作易于理解和实现。
• 高效的内存利用率：堆栈使用连续的内存块，与其他数据结构相比，它的内存利用率更高。
• 快速访问时间：当从堆栈顶部添加和删除元素时，堆栈数据结构为添加和删除元素提供了快速访问时间。
• 有助于函数调用：堆栈数据结构用于存储函数调用及其状态，这有助于高效实现递归函数调用。
• 支持回溯：堆栈数据结构支持回溯算法，用于解决问题时通过存储先前的状态来探索所有可能的解决方案。
• 用于编译器设计：堆栈数据结构用于编译器设计中，用于编程语言的解析和语法分析。
• 启用撤消/重做操作：堆栈数据结构用于在文本编辑器、图形设计工具和软件开发环境等各种应用程序中启用撤消和重做操作。

堆栈的缺点：

• 容量有限：堆栈数据结构的容量有限，因为它只能容纳固定数量的元素。如果堆栈已满，添加新元素可能会导致堆栈溢出，从而导致数据丢失。
• 不允许随机访问：堆栈数据结构不允许随机访问其元素，它只允许从堆栈顶部添加和删除元素。要访问堆栈中间的元素，必须删除其上方的所有元素。
• 内存管理：堆栈数据结构使用连续的内存块，如果频繁添加和删除元素，可能会导致内存碎片。
• 不适合某些应用程序：堆栈数据结构不适合需要访问堆栈中间元素的应用程序，例如搜索或排序算法。
• 堆栈上溢和下溢：如果将太多元素压入堆栈，则堆栈数据结构可能会导致堆栈溢出；如果从堆栈中弹出太多元素，则可能会导致堆栈下溢。
• 递归函数调用限制：虽然堆栈数据结构支持递归函数调用，但过多的递归函数调用可能会导致堆栈溢出，从而导致程序终止。

使用栈实现LRU 缓存

如何实现LRU缓存方案？应该使用什么数据结构？

我们给出了可以引用的总可能页码。我们还给出了缓存（或内存）大小（缓存一次可以容纳的页帧数）。LRU 缓存方案是当缓存已满并且引用缓存中不存在的新页面时删除最近最少使用的帧。

使用队列和散列的 LRU 缓存实现：

要解决该问题，需要遵循以下想法：

我们使用两种数据结构来实现 LRU Cache。 队列是使用双向链表实现的。队列的最大大小将等于可用帧的总数（缓存大小）。最近使用的页面将靠近前端，最近最少使用的页面将靠近后端。 以页码为键、对应队列节点的地址为值的哈希。 当一个页面被引用时，所需的页面可能在内存中。如果它在内存中，我们需要分离列表的节点并将其带到队列的前面。 如果所需的页面不在内存中，我们会将其放入内存中。简单来说，我们将一个新节点添加到队列的前面，并更新哈希中相应的节点地址。如果队列已满，即所有帧都已满，我们从队列的后面删除一个节点，并将新节点添加到队列的前面。

示例 –： 考虑以下参考字符串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

下面是上述方法的图示：

注意： 最初内存中没有任何元素。

请按照以下步骤解决问题：

• 创建一个 LRUCache 类，声明一个 int 类型的列表、一个 <int, list> 类型的无序映射以及一个用于存储缓存最大大小的变量
• 在LRUCache的refer函数中
• 在显示函数print中，LRUCache使用从前面开始的队列

javascript 代码示例:

//使用 Set 和 LinkedList 实现 LRU 缓存的 JavaScript 程序
class LRUCache {
  constructor(capacity) {
    this.cache = new Set();
    this.capacity = capacity;
  }
  
 // 此函数如果缓存中不存在键，则返回false。否则，它会通过先移除再添加的方式将键移到前面，并返回true。
  get(key) {
    if (!this.cache.has(key)) {
      return false;
    }
    this.cache.delete(key);
    this.cache.add(key);
    return true;
  }
  
/* 在LRU缓存中引用键x */
  refer(key) {
    if (!this.get(key)) {
      this.put(key);
    }
  }
  
// 以相反的顺序显示缓存内容
  display() {
   const list = [...this.cache];
  
// Array类用于反转数组中的元素
  list.reverse();
  let ans="";
  for (const key of list) {
    ans = ans +key + " ";
  }
    console.log(ans);
  }
  
  put(key) {
    if (this.cache.size === this.capacity) {
      const firstKey = this.cache.values().next().value;
      this.cache.delete(firstKey);
    }
    this.cache.add(key);
  }
}
 

const ca = new LRUCache(4);
ca.refer(1);
ca.refer(2);
ca.refer(3);
ca.refer(1);
ca.refer(4);
ca.refer(5);
ca.display();

golang 代码示例:

package main

import (
	"fmt"
	"testing"
)

type LRUCache struct {
	list  []int
	csize int
	ma    map[int]int
}

func (lru *LRUCache) refer(x int) {
	if index, ok := lru.ma[x]; !ok {
		// 如果存在,比较当前的容量是否已达上限
		if len(lru.list) == lru.csize {
			// 如果已达上限,则删除栈顶元素
			lru.list = lru.list[:lru.csize-1]
		}
	} else {
		// 如果存在, 则删除对应 index 位置的值, 并将期追加到队尾
		lru.list = append(lru.list[:index-1], lru.list[index+1:]...)
	}
	lru.list = append(lru.list, x)
	lru.ma[x] = len(lru.list)
}

func (lru *LRUCache) Display() {
	for i := len(lru.list) - 1; i >= 0; i-- {
		fmt.Println(lru.list[i])
	}
}

func NewLRUCache(size int) *LRUCache {
	ma := make(map[int]int)
	return &LRUCache{
		list:  []int{},
		csize: size,
		ma:    ma,
	}
}

func Test_NewLRUCache(t *testing.T) {
	cache := NewLRUCache(4)
	cache.refer(1)
	cache.refer(2)
	cache.refer(3)
	cache.refer(1)
	cache.refer(4)
	cache.refer(5)

	cache.Display()
}

时间复杂度： O(1)，我们使用Linked HashSet数据结构来实现缓存。Linked HashSet 为添加元素和检索元素提供恒定的时间复杂度。
辅助空间： O(n)，我们需要在缓存中存储n个元素，所以空间复杂度为O(n)。

点赞 评论 收藏 目录

阅读量：186

点赞量：0

收藏量:0