手撕数据结构---栈和队列的概念以及实现

手撕数据结构：栈和队列的概念与实现

栈（Stack）

概念：

• 栈是一种线性数据结构，遵循后进先出（LIFO）的原则。
• 可以想象成一叠盘子，新放的盘子总是在最上面，取盘子时也总是取最上面的。
• 常用操作：
  • push：入栈，将元素添加到栈顶。
  • pop：出栈，删除栈顶元素并返回。
  • peek：获取栈顶元素，但不删除。
  • isEmpty：判断栈是否为空。

实现：

• 数组实现：
  • 使用数组存储元素。
  • top指针指向栈顶元素。
  • 入栈时，将元素添加到top指针的下一个位置。
  • 出栈时，将top指针减一。
• 链表实现：
  • 使用链表存储元素。
  • top指针指向栈顶节点。
  • 入栈时，在链表头部插入新节点。
  • 出栈时，删除链表头部节点。

Java代码示例（数组实现）：

public class ArrayStack {
    private int[] data;
    private int top = -1;

    public ArrayStack(int capacity) {
        data = new int[capacity];
    }

    public void push(int element) {
        if (isFull()) {
            throw new RuntimeException("Stack overflow");
        }
        data[++top] = element;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        return data[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return data[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isF   ull() {
        return top    == data.length - 1;
    }
}

队列（Queue）

概念：

• 队列是一种线性数据结构，遵循先进先出（FIFO）的原则。
• 可以想象成一条队伍，先排队的人先出队。
• 常用操作：
  • enqueue：入队，将元素添加到队尾。
  • dequeue：出队，删除队头元素并返回。
  • peek：获取队头元素，但不删除。
  • isEmpty：判断队列是否为空。

实现：

• 数组实现：
  • 使用数组存储元素。
  • front指针指向队头，rear指针指向队尾。
  • 入队时，将元素添加到rear指针的下一个位置。
  • 出队时，将front指针加一。
• 链表实现：
  • 使用链表存储元素。
  • front指针指向队头节点，rear指针指向队尾节点。
  • 入队时，在链表尾部插入新节点。
  • 出队时，删除链表头部节点。

Java代码示例（数组实现）：

public class ArrayQueue {
    private int[] data;
    private int front, rear;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.data = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.capacity = capacity;
    }

    // ... 其他方法
}

栈和队列的应用

• 栈： 函数调用、表达式求值、浏览器历史记录、回溯算法
• 队列： 广度优先搜索、生产者消费者模型、任务调度

总结

栈和队列是两种基础的数据结构，在编程中应用广泛。掌握它们的实现原理和应用场景，对于深入理解算法和数据结构有很大的帮助。

建议：

• 动手实现： 尝试自己动手实现栈和队列，加深对它们的理解。
• 对比分析： 比较数组实现和链表实现的优缺点。
• 扩展练习： 尝试实现循环队列、双端队列等变种。

希望这个回答对你有帮助！

如果你还有其他问题，欢迎随时提问。

想深入了解哪些方面呢？ 比如：

• 栈和队列的应用场景
• 栈和队列的优化
• 栈和队列与其他数据结构的关系

请告诉我你的需求，我将为你提供更详细的解答。