数据结构与算法(二) 栈与队列（代码示例）

雨点打透心脏的1/2处 2022-09-11 04:21 208阅读 0赞

### 数据结构与算法 栈与队列 ###

*   *  1. 数组和链表实现栈
     *  2. 用O(1)的时间复杂度求栈中的最小元素
     *  3. 链表和数组实现队列
     *  4. 用两个栈模拟队列操作

## 1. 数组和链表实现栈 ##

链表的方式：

/** * 描述：栈的链表实现 * * @author Ye * @version 1.0 * @date 2021/8/20 13:44 */
    public class Stack<E> { 
        Node1<E> top = null;
        public boolean isEmpty(){ 
            return top == null;
        }
    
        public void push(E data){ 
            Node1<E> newLen = new Node1<>(data);
            newLen.next = top;
            top = newLen;
        }
    
        public E pop(){ 
            if (this.isEmpty()){ 
                return null;
            }
            E data = top.data;
            top = top.next;
            return data;
        }
    
        public E peek(){ 
            if (isEmpty()){ 
                return null;
            }
            return top.data;
        }
    
    }
    
    class Node1<E>{ 
        Node1<E> next = null;
        E data;
        public Node1(E data){ 
            this.data = data;
        }
    }

数组的方式：

import java.util.Arrays;
    
    /** * 描述：栈的数组实现 * * @author Ye * @version 1.0 * @date 2021/8/20 13:07 */
    public class MyStack<E> { 
        private Object[] stack;
    
        /** * 数组中存储元素个数 */
        private int size;
    
        public MyStack(){ 
            /** * 初始长度为10 */
            stack = new Object[10];
    }
    
        /** * 判断堆栈是否为空 */
        public boolean isEmpty(){ 
            return size == 0;
        }
    
        public E peek(){ 
            if (isEmpty()){ 
                return null;
            }
            return (E)stack[size - 1];
        }
    
        public E pop(){ 
            E e = peek();
            stack[size - 1] = null;
            size --;
            return e;
        }
    
        public E push(E item){ 
            /** * 检查容量 */
            ensureCapacity(size + 1);
            stack[size++] = item;
            return item;
        }
    
        /** * 判断数组器是否已满，若已满，则扩充数组空间 */
        private void ensureCapacity(int size){ 
            int len = stack.length;
            /** * 数组已满 */
            if (size > len){ 
                /** * 每次数组扩充的容量 */
                int newLen = 10;
                stack = Arrays.copyOf(stack,newLen);
            }
        }
    
        public static void main(String[] args) { 
            MyStack<Integer> s = new MyStack<>();
            s.push(1);
            s.push(6);
            s.push(10);
            System.out.println("栈中的元素个数： " + s.size);
            System.out.println("栈顶元素为： " + s.pop());
            System.out.println("栈顶元素为： " + s.pop());
        }
    }

运行截图：  
![在这里插入图片描述][9291487689aa4328ad3572f0f246d339.png]

## 2. 用O(1)的时间复杂度求栈中的最小元素 ##

只用O(1)就找出最小值，说明不能遍历栈；而只用O(1)那么短的时间，一般是牺牲了空间来换取的。  
所以设计的思路就是，用另一个栈来记录最小值。具体实现如下  
代码如下：

package com.example.demo;
    
    /** * 描述：用O(1)的时间复杂度求栈中的最小元素 * * @author Ye * @version 1.0 * @date 2021/8/20 14:23 */
    public class MyStack1 { 
        MyStack<Integer> elem;
        MyStack<Integer> min;
        public MyStack1(){ 
            elem = new MyStack<>();
            min = new MyStack<>();
        }
    
        public void push(int data){ 
            elem.push(data);
            if (min.isEmpty()){ 
                min.push(data);
            }else { 
                if (data < min.peek()){ 
                    min.push(data);
                }
            }
        }
    
        public int pop(){ 
            int topData = elem.peek();
            elem.pop();
            if (topData == this.min()){ 
                elem.pop();
            }
            return topData;
        }
    
        public int min(){ 
            if (min.isEmpty()){ 
                return Integer.MIN_VALUE;
            }else { 
                return min.peek();
            }
        }
    }

## 3. 链表和数组实现队列 ##

链表的实现：

/** * 描述：链表实现队列 * * @author Ye * @version 1.0 * @date 2021/8/20 14:51 */
    
    public class MyQueue<E>{ 
    
        private Node2<E> head = null;
            private Node2<E> tail = null;
            public boolean isEmpty(){ 
                return head == tail;
            }
            public void put(E data){ 
                Node2<E> newNode = new Node2<>(data);
                // 队列为空
                if (head == null && tail == null){ 
                    head = tail = newNode;
                }else { 
                    tail.next = newNode;
                    tail = newNode;
                }
    
            }
    
            public E pop(){ 
                if (this.isEmpty()){ 
                    return null;
                }
                E data = head.data;
                head = head.next;
                return data;
            }
    
            public int size(){ 
                Node2<E> temp = head;
                int n = 0;
                while (temp != null){ 
                    n++;
                    temp = temp.next;
                }
                return n;
            }
    
            public static void main(String[] args) { 
                MyQueue<Integer> queue = new MyQueue<Integer>();
                queue.put(56);
                queue.put(6);
                queue.put(163);
                System.out.println("队列长队为： " + queue.size());
                System.out.println("队列首元素： " + queue.pop());
                System.out.println("队列首元素： " + queue.pop());
            }
    }
    
    
    class Node2<E> { 
        Node2<E> next = null;
        E data;
    
        public Node2(E data) { 
            this.data = data;
        }
    }

运行截图：  
![在这里插入图片描述][9e118eeb2ecc4ad0afcc140874d107c6.png]  
数组的实现：  
为了实现多线程的安全，增加了对队列操作的同步

import java.util.LinkedList;
    
    /** * 描述：数组实现队列 * * @author Ye * @version 1.0 * @date 2021/8/27 19:49 */
    public class MyQueue1<E> { 
        private LinkedList<E> list = new LinkedList<>();
        private int size = 0;
        public synchronized void put(E e){ 
            list.addLast(e);
            size++;
        }
    
        public synchronized E pop(){ 
            size--;
            return list.removeFirst();
        }
    
        public synchronized boolean empty(){ 
            return size == 0;
        }
    
        public synchronized int size(){ 
            return size;
        }
    }

## 4. 用两个栈模拟队列操作 ##

使用栈A与栈B模拟队列Q，s1为插入栈，s2为弹出栈。  
具体实现如下，使用Java内置的Stack来实现：

import java.util.Stack;
    
    /** * 描述：两个栈实现队列 * * @author Ye * @version 1.0 * @date 2021/9/12 20:16 */
    public class MyQueue2<E> { 
        private Stack<E> s1 = new Stack<>();
        private Stack<E> s2 = new Stack<>();
        public synchronized void put(E e){ 
            s1.push(e);
        }
        public synchronized E pop(){ 
            if (s2.isEmpty()){ 
                while (!s1.isEmpty()){ 
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }
        public synchronized boolean empty(){ 
            return s1.isEmpty() && s2.isEmpty();
        }
        public static void main(String[] args){ 
            MyQueue<Integer> q = new MyQueue<>();
            q.put(1);
            q.put(5);
            q.put(53);
            System.out.println("队列首元素：" + q.pop());
            System.out.println("队列首元素：" + q.pop());
        }
    }

运行截图：  
![在这里插入图片描述][f8b5fb8a57dd44949e37fff7d896f15c.png]

参考：《Java程序员面试笔试宝典》 何昊、薛鹏、叶向阳 编著

[9291487689aa4328ad3572f0f246d339.png]: /images/20220828/36c60000672049199c55269f86fcddb5.png
[9e118eeb2ecc4ad0afcc140874d107c6.png]: /images/20220828/a9f17583f2af48889b4cf2dbe4d673b9.png
[f8b5fb8a57dd44949e37fff7d896f15c.png]: /images/20220828/7bd6047c8fd74016812ed5a989e8da26.png