数据结构与算法 栈与队列
1. 数组和链表实现栈2. 用O(1)的时间复杂度求栈中的最小元素3. 链表和数组实现队列4. 用两个栈模拟队列操作1. 数组和链表实现栈
链表的方式：
/*** 描述：栈的链表实现** @author Ye* @version 1.0* @date /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 /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());}}
运行截图：
2. 用O(1)的时间复杂度求栈中的最小元素
只用O(1)就找出最小值，说明不能遍历栈；而只用O(1)那么短的时间，一般是牺牲了空间来换取的。
所以设计的思路就是，用另一个栈来记录最小值。具体实现如下
代码如下：
package com.example.demo;/*** 描述：用O(1)的时间复杂度求栈中的最小元素** @author Ye* @version 1.0* @date /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 /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;}}
运行截图：
数组的实现：
为了实现多线程的安全，增加了对队列操作的同步
import java.util.LinkedList;/*** 描述：数组实现队列** @author Ye* @version 1.0* @date /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 /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());}}
运行截图：
参考：《Java程序员面试笔试宝典》 何昊、薛鹏、叶向阳 编著
