模拟实现栈和队列中的常用方法

电玩女神 2022-11-11 14:59 164阅读 0赞

### 模拟实现栈和队列中的常用方法 ###

*  栈
 *   *  概念
     *  方法
     *  模拟实现栈
 *  队列
 *   *  概念
     *  方法
     *  模拟实现队列

# 栈 #

## 概念 ##

栈：是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行插入和删除的叫做栈顶，另一端叫做栈底。栈遵循先进后出（FILO）、后进先出（LIFO） 原则。

## 方法 ##

在Java中，对于栈提供了如下方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

<table> 
 <thead> 
  <tr> 
   <th>返回值类型</th> 
   <th>方法名</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean</td> 
   <td>empty()</td> 
   <td>判断栈是否为空</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>peek()</td> 
   <td>查看栈顶元素</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>pop()</td> 
   <td>出栈，并返回出栈元素</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>push(E)</td> 
   <td>入栈</td> 
  </tr> 
 </tbody> 
</table>

## 模拟实现栈 ##

可以用ArraysList使用尾插\\尾删的方式实现模拟实现栈  
也可以用LinkedList使用头插\\头删或者尾插\\尾删的方式实现

我们就使用数组来模拟实现栈：

public class MyStack { 
        //暂时先不考虑扩容问题
        private int[] array = new int[100];
        private int size = 0;
    
        public void push(int v) { 
            array[size] = v;
            size++;
        }
    
        public int pop() { 
            int ret = array[size - 1];
            size--;
            return ret;
        }
    
        public int peek() { 
            return array[size - 1];
        }
    
        public boolean isEmpty() { 
            return size == 0;
        }
    
        public int size() { 
            return size;
        }
    }

# 队列 #

## 概念 ##

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出（FIFO） 的原则。

## 方法 ##

在Java中，对于队列提供了如下方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

<table> 
 <thead> 
  <tr> 
   <th>返回值类型</th> 
   <th>方法名</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean</td> 
   <td>add()\offer()</td> 
   <td>入队列</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>remove()\poll()</td> 
   <td>出队列</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>element()\peek()</td> 
   <td>队首元素</td> 
  </tr> 
 </tbody> 
</table>

## 模拟实现队列 ##

队列也可以用数组和链表来实现，但是链表的话结构更优一些。如果是数组，那么每次出队列或者入队列，在数组头部，效率比较低。

使用链表模拟实现队列。  
尾插，头删

//结点类
    class Node { 
        int val;
        Node next;
    
        public Node(int val, Node next) { 
            this.val = val;
            this.next = next;
        }
    
        public Node(int val) { 
            this(val, null);
        }
    }
    
    public class MyQueue { 
        private Node head = null;
        private Node tail = null;
        private int size = 0;
    
        public void add(int v) { 
            Node node = new Node(v);
            if (tail == null) { 
                head = node;
            } else { 
                tail.next = node;
            }
            tail = node;
            size++;
        }
    
        public int poll() { 
            if (size() == 0) { 
                throw new RuntimeException("队列为空");
            }
            int ret = head.val;
            head = head.next;
            if (head == null) { 
                tail = null;
            }
            size--;
            return ret;
        }
    
        public int peek() { 
            if (size() == 0) { 
                throw new RuntimeException("队列为空");
            }
            return head.val;
        }
    
        public boolean isEmpty() { 
            return size == 0;
        }
    
        public int size() { 
            return size;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/e199f7584a90499b8672184d5f38038b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210321154444108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70