破解面试难题：栈与队列核心题库深度解析

引言

在软件工程师的面试中，数据结构是必考的内容之一。栈与队列作为两种基本的数据结构，经常出现在面试题库中。本文将深入解析栈与队列的核心题目，帮助读者更好地理解和应对面试中的挑战。

栈（Stack）

1. 栈的定义与特性

栈是一种后进先出（Last In First Out, LIFO）的数据结构。它只允许在表的一端进行插入和删除操作。

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

2. 栈的常见面试题

题目1：实现一个栈

# 如上代码所示，实现了一个简单的栈

题目2：用两个队列实现一个栈

from collections import deque

class QueueStack:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, item):
        self.queue1.append(item)

    def pop(self):
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.popleft())
        item = self.queue1.popleft()
        self.queue1, self.queue2 = self.queue2, self.queue1
        return item

    def peek(self):
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.popleft())
        item = self.queue1[0]
        self.queue1, self.queue2 = self.queue2, self.queue1
        return item

队列（Queue）

1. 队列的定义与特性

队列是一种先进先出（First In First Out, FIFO）的数据结构。它只允许在表的一端进行插入操作，在另一端进行删除操作。

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        return None

2. 队列的常见面试题

题目1：实现一个队列

# 如上代码所示，实现了一个简单的队列

题目2：用两个栈实现一个队列

class StackQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def enqueue(self, item):
        self.stack1.append(item)

    def dequeue(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop() if self.stack2 else None

    def peek(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1] if self.stack2 else None

总结

通过本文的深度解析，相信读者对栈与队列的核心题目有了更深入的理解。在面试中，熟练掌握这些题目，将有助于你顺利通过面试。