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

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

栈（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;

    }



    // ... 其他方法

}

栈和队列的应用

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

总结

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

建议：

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

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

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

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

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

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