栈和队列

古城微笑少年丶 2021-11-11 21:58 473阅读 0赞

### 文章目录 ###

*   *  一、栈
     *   *  1.实现栈
         *   *  1.1用数组实现栈：
             *  1.2用链表实现栈
         *  2.用O(1)的时间复杂度求栈中最小元素
     *  二、队列
     *   *  1.实现队列
         *   *  1.1链表实现队列
             *  1.2动态数组实现队列（线程安全）
         *  2.用两个栈模拟队列操作

## 一、栈 ##

### 1.实现栈 ###

#### 1.1用数组实现栈： ####

public class MyStack <E>{ 
         private Object[] stack;
         private int size;
         public MyStack(){ 
             stack = new Object[10];//初始长度为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 element){ 
             ensureCapacity(size);
             stack[size++] = element;
             return element;
        }
        //扩容
        public void ensureCapacity(int size){ 
             int len = stack.length;
             if (size>=len){ 
                 int newlen = 10;
                 stack = Arrays.copyOf(stack,len+newlen);
             }
        }
    
        public static void main(String[] args) { 
            MyStack<Integer> myStack = new MyStack<>();
            myStack.push(1);
            myStack.push(3);
            myStack.push(4);
            myStack.push(8);
            myStack.push(6);
            myStack.push(3);
            myStack.push(7);
            myStack.push(0);
            myStack.push(4);
            myStack.push(3);
            myStack.push(9);
            System.out.println("栈中元素"+myStack.size);
            System.out.println("栈顶元素"+myStack.pop());
            System.out.println("栈顶元素"+myStack.pop());
        }
    }

#### 1.2用链表实现栈 ####

class StackNode<E>{ 
        StackNode<E> next = null;
        E data;
        public StackNode(E data) { 
            this.data = data;
        }
    }
    
    public class Stack<E> { 
        StackNode<E> top = null;
        public boolean isEmpty(){ 
            return top==null;
        }
        public void push(E data){ 
            StackNode<E> newNode = new StackNode<>(data);
            newNode.next = top;
            top = newNode;
        }
        public E pop(){ 
            if (isEmpty())
                return null;
            E data = top.data;
            top = top.next;
            return data;
        }
        public E peek(){ 
            if (isEmpty())
                return  null;
            return top.data;
        }
    }

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

class MyStack1{ 
        Stack<Integer> elem;
        Stack<Integer> min;
        public MyStack1(Stack<Integer> elem, Stack<Integer> min) { 
            this.elem = elem;
            this.min = min;
        }
        public void push(int data){ 
            if (min.isEmpty()){ 
                min.push(data);
            }
            if (data<min.peek())
                min.push(data);
            elem.push(data);
        }
        public void pop(){ 
            int topData = elem.peek();
            elem.pop();
            if (topData < min.peek()){ 
                min.push(topData);
            }
        }
    }

## 二、队列 ##

### 1.实现队列 ###

#### 1.1链表实现队列 ####

class qNode<E>{ 
        qNode<E> next = null;
        E data;
        public qNode(E data) { 
            this.data = data;
        }
    }
    
    public class MyQueue<E> { 
        private qNode head = null;
        private qNode tail = null;
        public boolean isEmpty(){ 
            return head == tail;
        }
        public void put(E data){ 
            qNode newNode = new qNode(data);
            if (head == null&& tail==null){ 
                head = tail = newNode;
            }else { 
                tail.next = newNode;
                tail = newNode;
            }
        }
        public void pop(){ 
            if (this.isEmpty()){ 
                return ;
            }
            head = head.next;
        }
        public E peek(){ 
            if (head!=null)
                return (E)head.data;
            return null;
        }
        public int size(){ 
            qNode temp = head;
            int size = 0;
            while (temp!=null){ 
                size++;
                temp = temp.next;
            }
            return size;
        }
    
        public static void main(String[] args) { 
            MyQueue<Integer> queue = new MyQueue<>();
            queue.put(1);
            queue.put(4);
            queue.put(6);
            System.out.println("队列长度为："+queue.size());
            System.out.println("队列头元素为:"+queue.peek());
            queue.pop();
            System.out.println("出队列一个后队列头元素为:"+queue.peek());
        }
    }

#### 1.2动态数组实现队列（线程安全） ####

public class MyQueue<E> { 
    
        private LinkedList<E> list = new LinkedList<>();
        int size = 0;
        public synchronized void put(E data){ 
            list.addLast(data);
            size++;
        }
        public synchronized void pop(){ 
            list.removeFirst();
            size--;
        }
        public synchronized boolean isEmpty(){ 
            return list.isEmpty();
        }
        public synchronized int size(){ 
            return size;
        }
        public synchronized E peek(){ 
            return list.peek();
        }
    
        public static void main(String[] args) { 
            MyQueue<Integer> queue = new MyQueue<>();
            queue.put(1);
            queue.put(6);
            queue.put(4);
            queue.put(6);
            System.out.println("队列长度为："+queue.size());
            System.out.println("队列头元素为:"+queue.peek());
            queue.pop();
            System.out.println("出队列一个后队列头元素为:"+queue.peek());
        }
    }

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

假设使用栈A与栈B模拟队列Q，A为插入列，B为弹出列，以实现队列Q。  
要入队列，入栈A即可，而出队列则需要分两种情况考虑：  
1.栈B不为空，则直接弹出栈B的数据；  
2.栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。

public class MyQueue<E> { 
        private Stack<E> stack1 = new Stack<>();
        private Stack<E> stack2 = new Stack<>();
        public synchronized void put(E data){ 
            stack1.push(data);
        }
        public synchronized E pop(){ 
            if (stack2.isEmpty()){ 
                while (!stack1.isEmpty()){ 
                    stack2.push(stack1.pop());
                }
            }
             return stack2.pop();
        }
        public synchronized boolean isEempty(){ 
            return stack1.isEmpty()&&stack2.isEmpty();
        }
        public synchronized E peek(){ 
            if (stack2.isEmpty()){ 
                while (!stack1.isEmpty()){ 
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }
        public synchronized int size(){ 
            return stack2.size()+stack1.size();
        }
        public static void main(String[] args) { 
            MyQueue<Integer> queue = new MyQueue<>();
            System.out.println("队列长度为："+queue.size());
            queue.put(3);
            queue.put(5);
            queue.put(7);
            queue.put(6);
            System.out.println("队列长度为："+queue.size());
            queue.pop();
            System.out.println("队列头为："+queue.peek());
        }
    }

引申： 使用两个队列实现栈  
假设使用队列q1与队列q2模拟栈，q1为入队列，q2为出队列。  
要压栈，入队列q1即可，当弹栈时，出队列要分两种情况：  
1.q1中只有一个元素，q1中的元素出队列；  
2.q1中不只有一个元素，q1中的所有元素出队列，入队列q2，最后一个元素不入q2，输出该元素，再将q2中的所有元素入q1.