Java的栈与队列以及代码实现

如烟花般绚烂却又稍纵即逝

发布于 2024-11-26 08:40:11

11900

代码可运行

文章被收录于专栏：javajava

运行总次数：0

代码可运行

栈的概念（Stack）

栈是常见的线性数据结构，栈的特点是以先进后出的形式，后进先出，先进后出，分为栈底和栈顶栈应用于内存的分配，表达式求值，存储临时的数据和方法的调用等。例如这把枪，第一发子弹是最后发射的，第一发子弹在栈底，而最新安装上去的子弹在栈的顶部，只有将上面的子弹打完（栈顶的数据走完），最后一发子弹才会射出

栈的实现

栈的实现是基于简单的数组形成的，我们可以将它想象成连续的数组，而栈的顺序是由后放到前放

模拟实现栈的方法:push（放入一个元素到栈中) pop(提取栈顶的一个元素，并将在其栈中消除) peek(查看栈顶的元素) size(查看栈中的大小) empty(栈中是否为空) full(栈是否满了)

代码

import java.util.Arrays;

public class MyStack implements IStack {
    private int[] elem;
    private int top;//数组的栈顶,以及数组栈中存放元素的数量
    private static final int DEFAULT_CAPACITY = 10;//这里是初始容量
    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
        top = -1;//数组下标从0开始
    }
    @Override
    public void push(int item) {
        if (full()) {
            //如果满了就扩容
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[++top] = item;
    }
    @Override
    public int pop() throws RuntimeException {
        try {
            if (empty()) {
                throw new RuntimeException("栈为空");
            }
        } catch (RuntimeException e) {
            e.printStackTrace();
        }
        return elem[top--];//return返回后删除栈顶的元素
    }
    @Override
    public int peek() {
        if (empty()) {
            throw new RuntimeException("栈为空");
        }
        return elem[top];//返回栈顶元素
    }
    @Override
    public int size() {
        return top+1;//去除数组0
    }
    @Override
    public boolean empty() {
        return top == -1;
    }
    @Override
    public boolean full() {
        return top == elem.length;//count==当前的elem的总长度为true
    }
}

队列（Queue）

队列是由先进先出的线性数据结构，采用的是先进先出，后进后出，如果要插入元素的话就是从入队尾巴方向插入，而删除作为出队要在头尾删除。

队列的方法

模拟实现队列(双链表实现)

public class MyQueue implements IQueue{
    static class Queue{
        public int elem;
        public Queue next;
        public Queue prev;
        public Queue(int elem) {
            this.elem = elem;
        }
    }
    public Queue head;
    public Queue last;
    public int size=0;
    @Override
    public void offer(int val) {
        Queue queue = new Queue(val);
        if (this.head == null) {
            this.head = queue;
            this.last = queue;
            ++size;
            return;
        }
        this.last.next=queue;
        this.last.prev=this.head;
        this.last=last.next;
        ++size;
    }

    @Override
    public int poll() {
        if(this.head==null){
            throw new RuntimeException("没有要丢掉的队列");
        }
        Queue cur =this.head;
        if(this.head.next==null){
            return -1;
        }
            this.head=this.head.next;
            this.head.prev=null;
            size--;
        return cur.elem;
    }

    @Override
    public int peek() {
        if(this.head!=null){
            return this.head.elem;
        }
        return 0;
    }

    @Override
    public int size() {
        return size;
    }
}

循环队列（循环数组实现）

数组实现队列的循环需要引入一个公式（目前的下标值+1）%当前数组的长度 (index+1)%array.length,下标值从0开始少一个数，当index+1就是当前的总长度时，公式后的值一定为下标0。

    private int[] array;
    private int front;
    private int rear;

    public MyCircularQueue(int k) {
        array=new int[k+1];
        front=0;//初始位置
        rear=0;
    }
    
    public boolean enQueue(int value) {
        //入列
        if(isFull()){
        //这里如果容量已经满了，需要先删除后在进行插入
            return false;
        }
        array[rear]=value;//rear下标获取元素
        rear=(rear+1)%array.length;//rear最终循环为0下标
        return true;
    }
    
    public boolean deQueue() {
        //出列
        if(isEmpty()){
        //为空返回false
            return false;
        }
        front=(front+1)%array.length;//front只需要往后走
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        //这里三木操作符判断是否为0如果为0，将rear回退到最后一个位置，不为0则-1
        int temp =  (rear==0)?array.length-1:rear-1;
        return array[temp];
    }
    
    public boolean isEmpty() {
        return front==rear;
    }
    
    public boolean isFull() {
        return (rear+1)%array.length==front;
    }
}

用队列实现栈

因为队列是先进先出的，而我们的栈是先进后出的，两种线性结构的关系是颠倒的，一个队列是不能完成的，我们需要两个队列互相工作来完成辅助队列先获取数值，保证辅助队列是最后一个拿到值的，然后将主队列的值给到辅助队列，在交换两个队列的数值，因为队列关系先进先出，每一次最后一个值就是队列先出的数值主队列不为空，将主队列的元素都poll出放到辅助栈中，使用一个tmp来将主队列（这里主队列已经遍历完）和辅助队列交换

    Queue<Integer> q1;//主队列
    Queue<Integer> q2;//辅助队列
    public MyStack() {
        q1=new LinkedList<>();//构造方法
        q2=new LinkedList<>();
    }
    public void push(int x) {
            q2.offer(x);
        while(!q1.isEmpty()){//主队列不为空，则将主队列出列给到辅助队列
            q2.offer(q1.poll());
        }
        //走到这里主队列是为空
        Queue tmp=q1;
        q1=q2;
        q2=tmp;
        //将两个队列交换
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

用栈来实现队列

栈来实现队列，栈是先进后出的顺序，而队列是先进先出的顺序将push都放到a栈中当我们peek或者是要删除的时候，我们都将a栈的元素pop给b栈，这样b栈已经有了我们的元素

但是我们还需要考虑的是丢掉元素后如果在一起添加元素到a栈呢，这里我们给一个条件，如果b的栈不为空时，我们仍然用b栈的队列如果a为空，这两个栈都是空的说明没有元素直接返回-1，如果a不为空的话且b没有新的元素b继续捕获新的a栈中所有的元素

class MyQueue {
    Stack<Integer> A;
    Stack<Integer> B;
    public MyQueue() {
        A=new Stack<>();
        B=new Stack<>();
    }
    
    public void push(int x) {
        A.push(x);
    }
    
    public int pop() {
        int check=peek();
        B.pop();
        return check;
    }
    
    public int peek() {
    //先判断b是否是空的，如果不是空的直接返回，是空才可以往下走
               if(!B.isEmpty())return B.peek();
               //因为b还不是空的，所以不需要将a栈放到b中
        if(A.isEmpty())return -1;
        while(!A.isEmpty()){
            B.push(A.pop());//将所有的a放到b中
        }
        return B.peek();
    }
    
    public boolean empty() {
        return A.isEmpty()&&B.isEmpty();
        //a和b都为空才为空
    }
}