算法与数据结构之栈(Stack)和队列(Queue)

栈（Stack）

1. 定义: 栈是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构。这意味着最后添加到栈中的元素会是第一个被移除的。
2. 基本操作:
   • push: 向栈顶添加一个元素。
   • pop: 移除并返回栈顶元素。
   • peek/top: 返回栈顶元素而不移除它。
   • isEmpty: 检查栈是否为空。
   • size: 返回栈中元素的数量。
3. 应用:
   • 函数调用和递归。
   • 撤销操作（如文本编辑器中的撤销）。
   • 括号匹配等。
4. 实现:
   • 可以使用数组或链表实现。
   • 在数组实现中，栈的大小可能是固定的或动态扩展的。
   • 在链表实现中，栈可以动态地增长，并且不存在大小的限制。

队列（Queue）

1. 定义: 队列是一种遵循先进先出（FIFO, First In First Out）原则的数据结构。这意味着最先添加到队列的元素会是第一个被移除的。
2. 基本操作:
   • enqueue: 在队列的尾部添加一个元素。
   • dequeue: 移除并返回队列头部的元素。
   • front: 返回队列头部的元素但不移除它。
   • isEmpty: 检查队列是否为空。
   • size: 返回队列中元素的数量。
3. 应用:
   • 数据缓冲（如打印任务队列）。
   • 任务调度。
   • 在宽度优先搜索算法中使用。
4. 实现:
   • 可以使用数组或链表实现。
   • 链表实现更为常见，因为它可以轻松地在两端添加和删除元素。
   • 在数组实现中，通常使用循环队列来避免空间浪费。

对比

• 主要区别: 栈是LIFO，而队列是FIFO。
• 使用场景: 栈通常用于解决涉及递归、回溯等问题，而队列适合于处理按顺序处理的任务。

在JS/Python/Go中的应用

• JavaScript:

  • 栈可以用数组实现（使用 push 和 pop 方法）。
  • 队列同样可以用数组实现（使用 push 和 shift 方法）。
  • 示例代码
    • 栈(Stack)

      class Stack {
          constructor() {
              this.items = [];
          }
          push(element) {
              this.items.push(element);
          }
          pop() {
              if (this.items.length === 0) return "Underflow";
              return this.items.pop();
          }
          peek() {
              return this.items[this.items.length - 1];
          }
          isEmpty() {
              return this.items.length === 0;
          }
          size() {
              return this.items.length;
          }
      }
      
      // 使用栈
      let stack = new Stack();
      stack.push(10);
      stack.push(20);
      console.log(stack.peek()); // 输出: 20
      stack.pop();
      console.log(stack.peek()); // 输出: 10

    • 队列(Queue)

      class Queue {
          constructor() {
              this.items = [];
          }
          enqueue(element) {
              this.items.push(element);
          }
          dequeue() {
              if(this.isEmpty()) return "Underflow";
              return this.items.shift();
          }
          front() {
              if(this.isEmpty()) return "No elements in Queue";
              return this.items[0];
          }
          isEmpty() {
              return this.items.length === 0;
          }
          size() {
              return this.items.length;
          }
      }
      
      // 使用队列
      let queue = new Queue();
      queue.enqueue(10);
      queue.enqueue(20);
      console.log(queue.front()); // 输出: 10
      queue.dequeue();
      console.log(queue.front()); // 输出: 20

• Python:

  • 栈可以用列表实现（使用 append 和 pop 方法）。
  • 队列可以用 collections.deque 实现，以支持高效的元素添加和删除。
  • 示例代码
    • 栈(Stack)

      class Stack:
          def __init__(self):
              self.items = []
      
          def push(self, item):
              self.items.append(item)
      
          def pop(self):
              if not self.is_empty():
                  return self.items.pop()
              return "Underflow"
      
          def peek(self):
              if not self.is_empty():
                  return self.items[-1]
              return "Empty Stack"
      
          def is_empty(self):
              return len(self.items) == 0
      
          def size(self):
              return len(self.items)
      # 使用栈
      stack = Stack()
      stack.push(10)
      stack.push(20)
      print(stack.peek())  # 输出: 20
      stack.pop()
      print(stack.peek())  # 输出: 10

    • 队列(Queue)

      from collections import deque
      
      class Queue:
          def __init__(self):
              self.items = deque()
      
          def enqueue(self, item):
              self.items.append(item)
      
          def dequeue(self):
              if not self.is_empty():
                  return self.items.popleft()
              return "Underflow"
      
          def front(self):
              if not self.is_empty():
                  return self.items[0]
              return "Empty Queue"     
      
          def is_empty(self):
              return len(self.items) == 0
      
          def size(self):
              return len(self.items)
      
      # 使用队列
      queue = Queue()
      queue.enqueue(10)
      queue.enqueue(20)
      print(queue.front())  # 输出: 10
      queue.dequeue()
      print(queue.front())  # 输出: 20

• Go:

  • 栈和队列通常需要自己实现，可以使用切片（slice）来实现栈，而队列则可以使用切片或链表实现。
  • 示例代码
    • 栈(Stack)

      package main
      
      import "fmt"
      
      type Stack []int
      
      func (s *Stack) Push(v int) {
          *s = append(*s, v)
      }
      
      func (s *Stack) Pop() int {
          if len(*s) == 0 {
              return -1 // 表示栈空
          }
          index := len(*s) - 1
          element := (*s)[index]
          *s = (*s)[:index]
          return element
      }
      
      func main() {
          var stack Stack
          stack.Push(10)
          stack.Push(20)
          fmt.Println(stack.Pop()) // 输出: 20
          fmt.Println(stack.Pop()) // 输出: 10
      }

    • 队列(Queue)

      package main
      
      import "fmt"
      
      type Queue []int
      
      func (q *Queue) Enqueue(v int) {
          *q = append(*q, v)
      }
      
      func (q *Queue) Dequeue() int {
          if len(*q) == 0 {
              return -1 // 表示队列空
          }
          element := (*q)[0]
          *q = (*q)[1:]
          return element
      }
      
      func main() {
          var queue Queue
          queue.Enqueue(10)
          queue.Enqueue(20)
          fmt.Println(queue.Dequeue()) // 输出: 10
          fmt.Println(queue.Dequeue()) // 输出: 20
      }