数据结构（java实现） ——栈和队列

怼烎@ 2023-09-27 13:52 116阅读 0赞

## 1. 栈(Stack) ##

### 1.1 概念 ###

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。  
压栈（push）：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。  
出栈（pop）：栈的删除操作叫做出栈。出数据在栈顶

![9bc8f67d6159465a8edea2156182e36b.png][]

### 1.2 栈的方法和功能 ###

<table> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>功能</td> 
  </tr> 
  <tr> 
   <td>Stack()</td> 
   <td>构造一个空的栈</td> 
  </tr> 
  <tr> 
   <td>E push(E e)</td> 
   <td>将e入栈，并返回e</td> 
  </tr> 
  <tr> 
   <td>E pop()</td> 
   <td>将栈顶元素出栈并返回</td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取栈顶元素</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取栈中有效元素个数</td> 
  </tr> 
  <tr> 
   <td>boolean empty()</td> 
   <td>检测栈是否为空</td> 
  </tr> 
 </tbody> 
</table>

### 1.3 栈的模拟实现 ###

![b66edc1bf7bf407abec1101bed07f7af.png][]

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

public class MyStrack {
        int[] array;
        int size;
    
        public MyStrack() {
            this.array = new int[3];
        }
    
        /*
        入栈
         */
        public int push(int e) {
            //判断是否队满，如果队满需要扩容
            if (isFull()) {
                ensureCapacity();
            }
            //入栈
            array[size++] = e;
            return e;
        }
     /*
       出栈
        */
        public int pop() {
            if (isEmpty()) {
                System.out.println("栈是空的！");//此处可以抛出异常
            }
            return array[--size];
        }
     /*
       获取栈顶元素
        */
        public int peek() {
            if (isEmpty()) {
                System.out.println("栈是空的！");//此处可以抛出异常
            }
            return array[size - 1];//数组下标从0开始，所以栈顶元素是size-1
        }
     //判断栈满
        private boolean isFull() {
            return size == array.length;
        }
    
        //栈空
        public boolean isEmpty() {
            return 0 == size;
        }
    
        //扩容
        private void ensureCapacity() {
            if (size == array.length) {
                array = Arrays.copyOf(array, size * 2);
            }
        }

## 2.队列(Queue) ##

### 2.1 概念 ###

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头（Head/Front）  
![9246104538f14b72ad8d7d8cf7c60574.png][]

### 2.2 队列的功能和方法 ###

<table> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>功能</td> 
  </tr> 
  <tr> 
   <td>boolean offer(E e)</td> 
   <td>入队列</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>出队列</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>获取队头元素</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取队列中有效元素个数</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>检测队列是否为空</td> 
  </tr> 
 </tbody> 
</table>

### 2.3队列的使用 ###

在Java中，Queue是个接口，底层是通过链表实现的。

![1abfcca0873046c69e01ca4644c74e3f.png][]

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

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

/*
    用单链表实现队列
    */
    public class MyQueue {
        static class Node {
            public int val;   //值域
            public Node next;  //指针域
    
            public Node(int val) {
                this.val = val;
            }
        }
        public Node head;
        public Node last;
        public int usedSize;
    
        //入队，用尾插法
        public void offer(int val) {
            Node node = new Node(val);
            if(head == null) {
                head = node;
                last = node;
            }else {
                last.next = node;
                last = node;
            }
            usedSize++;
        }
    
        public int poll() {
            if(empty()) {
                throw new EmptyException("队列为空");//抛出异常，也可以输出异常
            }
            int ret = head.val;
            head = head.next;
            if(head == null) {
                last = null;//只有一个节点 那么last也要置空
            }
            usedSize--;
            return ret;
        }
    
        public boolean empty() {
            return usedSize == 0;
        }
    
        public int peek() {
            if(empty()) {
                throw new EmptyException("队列为空");
            }
            return head.val;
        }
    
        public int getUsedSize() {
            return usedSize;
        }
    }

### 2.5 循环队列 ###

![119cac10484740789414eb497fe13761.png][]

**循环队列通常用数组实现，循环队列的引入是为了克服 假溢出。**

### **2.6 循环队列的重要计算** ###

*  队头指针：rear
 *  队尾指针：front
 *  队列元素个数：m
 *  判断队满：rear + 1 = front
 *  入队： rear = (rear + 1) % m
 *  出队： front = (front + 1) % m
 *  队空： front = rear
 *  队满： front = (rear + 1) % m
 *  当前队列中的元素数目： n = (rear - front + m) % m

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

class MyCircularQueue {
    
        private int[] elem;
        private int front;//表示队列的头
        private int rear;//表示队列的尾
    
        public MyCircularQueue(int k) {
            //如果是浪费空间 这里必须处理多加一个1
            this.elem = new int[k+1];
        }
    
        /**
         * 入队列
         * @param value
         * @return
         */
        public boolean enQueue(int value) {
            //1、检查是否队列是满的
            if(isFull()){
                return false;
            }
            //2、
            elem[rear] = value;
            //rear++;
            rear = (rear+1) % elem.length;
            return true;
        }
    
        /**
         * 出队列
         * @return
         */
        public boolean deQueue() {
            if(isEmpty()) {
                return false;
            }
            //front++;
            front = (front+1) % elem.length;
            return true;
        }
    
        /**
         * 得到队头元素
       
         */
        public int Front() {
            if(isEmpty()) {
                return -1;
            }
            return elem[front];
        }
    
        /**
         * 得到队尾元素
         * @return
         */
        public int Rear() {
            if(isEmpty()) {
                return -1;
            }
            int index = (rear == 0) ? elem.length-1 : rear-1;
            return elem[index];
        }
        
        public boolean isEmpty() {
            return front == rear;
        }
    
        /**
         * 队列是否为满
         * @return
         */
        public boolean isFull() {
           /* if( (rear+1) % elem.length == front) {
                return true;
            }
            return false;*/
            return (rear+1) % elem.length == front;
        }
    }

### 2.8 双端队列 (Deque) ###

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

![19517541682641d9aecbacddc721d9ca.png][]

![0dc05e46cda241b1845edfd56bf79efb.png][] Deque是一个接口，使用时必须创建LinkedList的对象。栈和队列都可以使用Deque接口。

> Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现  
> Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

### 练习题： ###

#### 1.用队列实现栈 ####

思路：1.创建两个空队列

2.入栈：入不为空的队列

3.出栈：不为空的队列出 size - 1 个元素到另外一个队列中去

![252196c63f6b4906a02b2943c26d2a7c.jpeg][]

public class MyStrack2 {
        private Queue<Integer> qu1;
        private Queue<Integer> qu2;
    
        public MyStack2() {
            qu1 = new LinkedList<>();
            qu2 = new LinkedList<>();
        }
        //往不空的队列放，都空就放第一个栈
        public void push(int x) {
            if(!qu1.isEmpty()) {
                qu1.offer(x);
            } else if (!qu2.isEmpty()) {
                qu2.offer(x);
            }else {
                qu1.offer(x);
            }
        }
        
        public int pop() {
            if(empty()) {
                return -1;//两个队列都为空，意味着当前的栈为空
            }
            if(!qu1.isEmpty()) {
                int size = qu1.size();
                for (int i = 0; i < size-1; i++) {
                    //for (int i = 0; i < qu1.size()-1; i++) {
                    int val = qu1.poll();
                    qu2.offer(val);
                }
                return qu1.poll();
            }else {
                int size = qu2.size();
                for (int i = 0; i < size-1; i++) {
                    int val = qu2.poll();
                    qu1.offer(val);
                }
                return qu2.poll();
            }
        }
        //peek
        public int top() {
            if(empty()) {
                return -1;//两个队列都为空，意味着当前的栈为空
            }
            if(!qu1.isEmpty()) {
                int size = qu1.size();
                int val = -1;
                for (int i = 0; i < size; i++) {
                    val = qu1.poll();
                    qu2.offer(val);
                }
                return val;
            }else {
                int size = qu2.size();
                int val = -1;
                for (int i = 0; i < size; i++) {
                    val = qu2.poll();
                    qu1.offer(val);
                }
                return val;
            }
        }
        
        public boolean empty() {
            return qu1.isEmpty() && qu2.isEmpty();
        }
    }

#### 2.用栈实现队列 ####

思路：用两个栈，先进一个栈，再出来放到另一个栈里，再出来

push：全部放到第一个栈里

pull：判断为空时，把第一个栈的所有元素拿出来放到第二个栈里

![603dc2ee81a746e7a7ec4d46d67dd8f7.png][]

class MyQueue {
    private Stack<Integer>stack1;
            private Stack<Integer>stack2;
            public MyQueue() {
                stack1 = new Stack<>();
                stack2 = new Stack<>();
            }
    
    //push
            public void push(int x) {
                stack1 . push(x);
            }
    
    
            public int pop() {
                if (isempty()){
                    return  -1;
                }
                if (stack2 == null){
                    while (stack1.isempty()){
                        stack2.push(stack1.pop());
    
                    }
                }
                return stack2.pop();
    
            }
    
            public int peek() {
                if (isempty()){
                    return  -1;
                }
                if (stack2 == null){
                    while (stack1.isempty()){
                        stack2.push(stack1.pop());
    
                    }
                }
                return stack2.peek();
            }
    
            public boolean isempty() {   // 第一个栈和第二个栈都是空的说明这个队列是空的
    return stack1.empty()&& stack2.empty();
            }
        }
    
    }

[9bc8f67d6159465a8edea2156182e36b.png]: https://img-blog.csdnimg.cn/9bc8f67d6159465a8edea2156182e36b.png
[b66edc1bf7bf407abec1101bed07f7af.png]: https://img-blog.csdnimg.cn/b66edc1bf7bf407abec1101bed07f7af.png
[9246104538f14b72ad8d7d8cf7c60574.png]: https://img-blog.csdnimg.cn/9246104538f14b72ad8d7d8cf7c60574.png
[1abfcca0873046c69e01ca4644c74e3f.png]: https://img-blog.csdnimg.cn/1abfcca0873046c69e01ca4644c74e3f.png
[119cac10484740789414eb497fe13761.png]: https://img-blog.csdnimg.cn/119cac10484740789414eb497fe13761.png
[19517541682641d9aecbacddc721d9ca.png]: https://img-blog.csdnimg.cn/19517541682641d9aecbacddc721d9ca.png
[0dc05e46cda241b1845edfd56bf79efb.png]: https://img-blog.csdnimg.cn/0dc05e46cda241b1845edfd56bf79efb.png
[252196c63f6b4906a02b2943c26d2a7c.jpeg]: https://img-blog.csdnimg.cn/252196c63f6b4906a02b2943c26d2a7c.jpeg
[603dc2ee81a746e7a7ec4d46d67dd8f7.png]: https://img-blog.csdnimg.cn/603dc2ee81a746e7a7ec4d46d67dd8f7.png