Skip to main content

堆栈 Stack & 队列 Queue

堆栈 Stack​

后进先出 (Last In First Out)

堆栈支持的操作​

  • Push
  • Pop
  • Peek
  • isEmpty

堆栈实现​

数组栈实现​

public class Stack {
    static final int CAPACITY = 1000;
    int top;
    int[] stack;

    pubolic Stack() {
        top = -1;
        stack = new int[CAPACITY];
    }

    public boolean push(int val) {
        if (top >= (CAPACITY - 1)) {
            System.out.println("Stack Overflow");
            return false;
        }
        stack[++top] = val;
        return true;
    }

    public int pop() {
        if(top < 0) {
            System.out.println("Stack UnderFlow.");
            return 0;
        }
        int element = stack[top--];
        return element;
    }

    public int peek() {
        if(top < 0) {
            System.out.println("Stack UnderFlow.");
            return 0;
        }
        int element = stack[top];
        return element;
    }

    public boolean isEmpty() {
        return top < 0;
    }
}

链式栈实现​

public class ListStack {
    static class StackNode {
        int val;
        StackNode next;
        StackNode(int val) {
            this.val = val;
        }
    }
    StackNode top;
    public ListStack() {
        top = null;
    }

    public void push(int val) {
        StackNode newNode = new StackNode(val);
        if (top == null) {
            top = newNode;
        } else {
            StackNode temp = top;
            top = newNode;
            newNode.next = temp;
        }
    }

    public int pop() {
        if (top == null) {
            Sytem.out.println("Stack is Empty.");
            return Integer.MIN_VALUE;
        } else {
            int popped = top.val;
            top = top.next;
            return popped;
        }
    }

    public void peek() {
        if (top == null) {
            Sytem.out.println("Stack is Empty.");
            return Integer.MIN_VALUE;
        }
        return top.val;
    }

    public void isEmpty() {
        reutrn top == null;
    }
}

队列 Queue​

队列支持的操作​

  • 主要操作
    • 入队(enqueue): 增加一个新元素
    • 出队(dequeue): 删除一个元素
  • 辅助操作
    • peek - 查看队列最前端的元素
    • isFull - 查看队列是否满了
    • isEmpty - 查看队列是否为空

队列实现​

数组队列的实现​

public class ArrayQueue {
    int front, rear, size;
    int capacity;
    int[] array;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        front = rear = size = 0;
        array = new int[capacity];
    }

    public void enquque(int item) {
        if (isFull()) return;
        array[rear] = item;
        rear = (rear + 1) % capacity;
        size++;
        System.out.println(item + "is enqueued.");
    }

    public int dequeue() {
        if(isEmpty()) return Integer.MIN_VALUE;
        int item = array[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    public int peek() {
        if(isEmpty()) return Integer.MIN_VALUE;
        return array[front];
    }

    public boolean isFull() {
        return size == capacity;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

链式队列的实现​

public calss ListQueue {
    QueueNode front;
    QueueNode rear;

    static class QueueNode {
        int value;
        QueueNode next;
        public QueueNode(int value) {
            this.value = value;
        }
    }

    public void enqueue(int value) {
        QueueNode newNode = new QueueNoe(value);
        if(this.rear == null) { // Queue is empty
            this.front = this.rear = newNode;
            return;
        }
        this.rear.next = newNode;
        this.rear = newNode
    }

    public int dequeue() {
        if(this.front == null) {
            System.out.println("The queue is empty.");
            return Integer.MIN_VALUE;
        }

        QueueNode frontNode = this.front;
        this.front = this.front.next;
        if (this.front == null) {
            this.rear = null;
        }
        return frontNode.value;
    }

    public int peek() {
        if (this.front == null) {
            return Integer.MIN_VALUE;
        }
        return this.front.value
    }

    public boolean isEmpty() {
        return this.front == null;
    }

    // public boolean isFull() {} // with capacity field
}

来源​