【数据结构】模拟实现栈和队列

古城微笑少年丶 2024-02-20 09:29 55阅读 0赞

#### 文章目录 ####

*  栈（Stack）
 *   *  栈的概念
     *  栈的常用方法
     *  模拟实现栈
 *  队列（Queue）
 *   *  队列的概念
     *  队列的常用方法
     *  队列的模拟实现
     *  循环队列模拟实现

## 栈（Stack） ##

### 栈的概念 ###

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作，进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈的数据遵循后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做压栈/进栈/入栈，入的数据在栈顶。

出栈：栈的删除操作叫做出栈，出的数据在栈顶。  
![在这里插入图片描述][bf16e42c3d594cf8898968e399cab002.png]

### 栈的常用方法 ###

//入栈
    public void push(int val)
        
    //将栈顶元素出栈并返回
    public int pop()
        
    //获取栈顶元素
    public int peek()
        
    //检测栈是否为空
    public boolean isEmpty()

### 模拟实现栈 ###

构造一个空栈

public class MyStack {
        
        private int[] elem;
        private int usedSize;//栈的实际元素个数
        private static final int DEFAULT_CAPACITY = 10;
    
        //初始化栈的大小为DEFAULT_CAPACITY
        public MyStack() {
        
            this.elem = new int[DEFAULT_CAPACITY];
        }
    }

实现push方法（入栈）

public void push(int val) {
        
    	//判断栈是否已满 满就扩容
    	if (this.elem.length == usedSize) {
        
    		this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
    	}
    	this.elem[usedSize] = val;
    	usedSize++;
    }

实现pop方法（将栈顶元素出栈并返回）

如果栈为空，返回栈顶元素就会报错，我们可以自定义一个异常用来解决报错问题

public class emptyException extends RuntimeException {
        
        public emptyException() {
        
        }
    
        public emptyException(String message) {
        
            super(message);
        }
    }

public int pop() {
        
        //如果为空栈就抛出一个异常
    	if (usedSize==0){
        
    		throw new emptyException();
    	}
    	int oldVal = this.elem[usedSize-1];
    	usedSize--;
    	return oldVal;
    }

实现peek方法（获取栈顶元素）

public int peek() {
        
        //如果为空栈就抛出一个异常
    	if (usedSize==0){
        
    		throw new emptyException();
    	}
    	return this.elem[usedSize-1];
    }

实现isEmpty方法（检测栈是否为空）

public boolean isEmpty() {
        
        //判断栈是否为空 只需要判断栈的实际元素个数是否为0即可
    	return usedSize==0;
    }

## 队列（Queue） ##

### 队列的概念 ###

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循先进先出FIFO（First in First Out）的原则。在Java里面Queue 是一个接口，底层是通过链表实现的。

入队列：进行插入的一端称为队尾。

出队列：进行删除的一端称为队头。  
![在这里插入图片描述][d03f8f1d4fe0440cbed922d79bbc656b.png]

### 队列的常用方法 ###

//入队
    public void offer(int x)
        
    //出队
    public int poll()
    
    //获取队头元素x
    public int peek()
    
    //获取队列中有效元素的个数
    public int size()
        
    //检测队列是否为空
    public boolean isEmpty()

### 队列的模拟实现 ###

双链表模拟实现队列

public class MyQueue {
        
        static class ListNode {
        
            public int val;
            public ListNode next;
            public ListNode prev;
    
            public ListNode(int val) {
        
                this.val = val;
            }
        }
    
        public ListNode front;//队头
        public ListNode rear;//队尾
        public int usedSize = 0;//队列实际元素个数
        
    }

实现offer方法（入队）

public void offer(int x) {
        
    	ListNode node = new ListNode(x);
        //队列为空
    	if (front==null){
        
    		front=rear=node;
    	}else {
        
    		node.next=front;
    		front.prev=node;
    		front=node;
    	}
    	usedSize++;
    }

实现poll方法（出队）

public int poll(){
        
        //队列为空
    	if (front==null){
        
    		return -1;
    	}
    	int ret = rear.val;
        //队列中只有一个元素
    	if (front==rear){
        
    		front=null;
    		rear=null;
    		usedSize--;
    		return ret;
    	}
    	//删除尾节点
    	rear=rear.prev;
    	rear.next=null;
    	usedSize--;
    }

实现peek方法（获取队头元素）

public int peek(){
        
    	if (front==null){
        
    		return -1;
    	}
    	return front.val;
    }

实现size方法（获取队列中有效元素的个数）

public int size(){
        
    	return usedSize;
    }

实现isEmpty方法（检测队列是否为空）

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

### 循环队列模拟实现 ###

![在这里插入图片描述][64fed5dcb35549daa6f5a9e02034728e.png]

![在这里插入图片描述][7eee22d2bea84c48b8933a983e52a551.png]

public class MyCircularQueue {
        
        public int[] elem;
        public int front;//队头
        public int rear;//队尾
    
        //构造循化队列
        public MyCircularQueue(int len) {
        
            this.elem = new int[len+1];
        }
    
        //入队
        public boolean enQueue(int val){
        
            //判断队列是否装满
            if (isFull()){
        
                return false;
            }
            elem[rear] = val;
            rear = (rear+1)%elem.length;
            return true;
        }
    
        //检测队列是否装满
        private boolean isFull() {
        
            return (rear+1)%elem.length==front;
        }
    
        //出队
        public boolean deQueue(){
        
            if (isFull()){
        
                return false;
            }
            front = (front+1)%elem.length;
            return true;
        }
    
        //获取队头元素
        public int getFront(){
        
            if (isEmpty()){
        
                return -1;
            }
            return elem[front];
        }
    
        //检测队列是否为空
        public boolean isEmpty(){
        
            return front==rear;
        }
    }

[bf16e42c3d594cf8898968e399cab002.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c352383499ed4c86bad59243f7d3d791.png
[d03f8f1d4fe0440cbed922d79bbc656b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c1bfef67d4e441bda48a8de26e8b8fd0.png
[64fed5dcb35549daa6f5a9e02034728e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/5db38cfaaf4745d59b69271514936036.png
[7eee22d2bea84c48b8933a983e52a551.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/cb144fd047fb466db4d0ddf48f763407.png