【算法】-- 【栈与队列的实现】

1.如何实现栈

1.数组实现栈

import java.util.Arrays; 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]; } /** * 出栈 * @return */ public E pop(){ E e = peek(); stack[size - 1] =null; size--; return e; } /** * 入栈 * @param item * @return */ 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(2); s.push(3); System.out.println("栈中元素个数为："+s.size); System.out.println("栈顶元素为："+s.pop()); System.out.println(s.peek()); System.out.println("栈顶元素为："+s.pop()); System.out.println(s.peek()); } }

2.链表实现栈 链表类

public class Node<E>{ Node<E> next =null; E data; public Node(E data){ this.data = data; } } public class Stack<E> { Node<E> top = null; public boolean isEmpty(){ return top == null; } public void push(E data){ Node<E> newNode = new Node<>(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)的时间复杂度求栈中的最小元素

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()){ min.pop(); } return topData; } private int min() { if (min.isEmpty()) return Integer.MAX_VALUE; else return min.peek(); } }

3.如何实现队列

链表实现队列

public class MyQueue<E> { private Node<E> head =null; private Node<E> tail =null; public boolean isEmpty(){ return head==tail; } public void put(E data){ Node<E> newNode = new Node<E>(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(){ Node<E> tmp =head; int n=0; while (tmp!=null){ n++; tmp=tmp.next; } return n; } public static void main(String[] args) { MyQueue<Integer> q = new MyQueue<>(); q.put(1); q.put(2); q.put(3); System.out.println("队列的长度为："+q.size()); System.out.println("队列的首元素为："+q.pop()); System.out.println("队列的首元素为："+q.pop()); } }

数组实现队列

import java.util.LinkedList; 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 isEmpty(){ return size==0; } public synchronized int size(){ return size; } }

4.如何用两个栈模拟队列

public class MyQueue2<E> { private Stack<E> s1 =new Stack<>(); private Stack<E> s2 =new Stack<>(); private 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 isEmpty(){ return s1.isEmpty()&&s2.isEmpty(); } public static void main(String[] args) { MyQueue2<Integer> q = new MyQueue2<>(); q.put(1); q.put(2); q.put(3); System.out.println("队列的首元素为："+q.pop()); System.out.println("队列的首元素为："+q.pop()); System.out.println("队列的首元素为："+q.pop()); } }