linkedList可以用作双向链表，队列，栈
用作双向链表
用作队列
用作栈
如何用队列模拟一个栈
如何用栈模拟一个队列
利用栈实现的一个运算器
用作双向链表
操作主要在头head和尾rear上，在头和尾上都可以进行增删
LinkedList<Integer> list =new LinkedList<Integer>();
list.addFirst(1);
list.addFirst(2);
list.addLast(3);
list.addLast(4);
打印的结果就是: 2 1 3 4
用作队列
操作主要在head和rear上，在head上只能出队，在rear上只能进队
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.offer(1);//在尾部进队
queue.offer(2);//在尾部进队
queue.poll();//在头部出队
打印的结果就是2
用作栈
操作主要在头上，可以在头上进行进栈出栈的操作
LinkedList<Integer> stack =new LinkedList<Integer>();
stack.push(1);//进栈
stack.push(2);//进栈
stack.push(8);//进栈
stack.pop();//弹栈
stack.pop();//弹栈
打印结果是8
如何用队列模拟一个栈:
package test1;
import java.util.LinkedList;
public class queueToStack {public static void main(String[] args) {/*** 模拟栈的三个方法：* peek()获取但不移除此列表的头（第一个元素）* pop()从此列表所表示的堆栈处弹出一个元素* push(E e) 将元素推入此列表所表示的堆栈*/// TODO Auto-generated method stubmyStack<Integer> stack =new myStack<Integer>();stack.push(8);stack.push(9);System.out.println(stack);stack.pop();System.out.println(stack);stack.peek();System.out.println(stack.peek()); }
}
class myStack<E>{private LinkedList<E> queue1;private LinkedList<E> queue2 ;//初始化两个队列public myStack() {queue1 =new LinkedList<E>();queue2 =new LinkedList<E>();}public E pop() {//判断queue是否为空，为模拟弹栈做准备/** 如果queue1不为空，就把queue1的内容保留最后一个放到queue2中，* 然后再把queue1中最后一个元素取出并且返回*/if(!queue1.isEmpty()) {int len = queue1.size();for(int i=0;i<len-1;i++) {queue2.offer(queue1.poll());}E res = queue1.poll();return res;}else {/** 如果queue2不为空，就把queue1的内容保留最后一个放到queue1中，* 然后再把queue2中最后一个元素取出并且返回*/int len = queue2.size();for(int i=0;i<len-1;i++) {queue1.offer(queue2.poll());}E res = queue2.poll();return res;}}public void push( E e) {//如果两个队都为空，就把元素放在queue1中if(queue1.isEmpty()&&queue2.isEmpty()) {queue1.offer(e);}else if (queue1.isEmpty()) {queue2.offer(e);}else {queue1.offer(e);}}/*** 跟pop()方法的原理基本相同,不同的是peek()只是返回，不弹栈*/public E peek() {if(!queue1.isEmpty()) {int len = queue1.size();for(int i=0;i<len-1;i++) {queue2.offer(queue1.poll());}E res = queue1.poll();queue2.offer(res);return res;}else {int len = queue2.size();for(int i=0;i<len-1;i++) {queue1.offer(queue2.poll());}E res = queue2.poll();queue1.offer(res);return res; }}@Override//重写stack对象的toStirng方法public String toString () {StringBuilder sb =new StringBuilder();if(queue1.isEmpty()&&queue2.isEmpty()) {return "";}else if(!queue1.isEmpty()) {int len =queue1.size();for(int i =len-1;i>=0;i--) {//栈是先进后出的sb.append(queue1.get(i));sb.append(' ');}}else {int len =queue2.size();for(int i =len-1;i>=0;i--) {//栈是先进后出的sb.append(queue2.get(i));sb.append(' ');}}return sb.toString();}
}
如何用栈模拟一个队列:
package test1;
import java.util.LinkedList;
public class stackToQueue {/*用栈模拟队列的三个方法boolean offer(E e) 入队一个元素 将指定元素添加到此列表的末尾（最后一个元素）。E poll() 出队 获取并移除此列表的头（第一个元素）E element() 获取当前队列的头元素*/public static void main(String[] args) {// TODO Auto-generated method stubmyQueue<Integer> queue =new myQueue<Integer>();queue.offer(1);queue.offer(2);queue.poll();System.out.println(queue);}
}
class myQueue<E>{private LinkedList<E> stack1;private LinkedList<E> stack2;public myQueue() {stack1 =new LinkedList<E> ();stack2=new LinkedList<E>();}//入队操作public void offer(E e) {stack1.push(e);}/**出队操作就是：把stack1中的元素，放到stack2中，这样就把顺序换过来了，然后stack2弹栈即可*/public E poll() {//将stack1中元素 放到stack2中while(!stack1.isEmpty()) {stack2.push(stack1.pop()); }E res =stack2.pop();//再把元素放回来while(!stack2.isEmpty()) {stack1.push(stack2.pop());}return res;}//获取队中的元素，原理和出队的原理基本相同，只是从队返回元素而不清除元素public E element() {//将stack1中元素 放到stack2中while(!stack1.isEmpty()) {stack2.push(stack1.pop()); }E res =stack2.peek();//再把元素放回来while(!stack2.isEmpty()) {stack1.push(stack2.pop());}return res; }public String toString() {StringBuilder sb = new StringBuilder();if(stack1.isEmpty()) {return "";}else {while(!stack1.isEmpty()) {stack2.push(stack1.pop());}while(!stack2.isEmpty()) {E e =stack2.pop();sb.append(e);sb.append(' ');stack1.push(e);}return sb.toString();} }
}
利用栈实现的一个运算器
package test1;import java.util.LinkedList;
/*** @author 王兴* 需求；用两个栈实现(1+2)*4+4/5+4*8+10的最终结果* 步骤：1，创建两个栈，一个放数值，一个放运算符* 2，我们知道运算的次序是：先算括号-->再算乘除-->再算加减* 3，当遇到'('时放到栈里，遇到'+'或'-'时，先判断栈里是否有+ - * /,如果有的话* 先进行运算，如果没有此符号入栈；遇到'*'或'/'时，先判断栈里是否有* /,如果有的话* 先进行运算，如果没有此符号入栈(* 和 /的优先级高于+ - )* 4，遇到')'时，先进行运算，运算完毕，将')'弹栈* 5，最后numOperator里面剩余两个数值，charOperator里面剩余一个运算符* 6，最后再做一次运算* 7，将结果弹栈即可*/
public class evaluateExpression {public static void main(String[] args) {// TODO Auto-generated method stubString str="(1+2)*4+5/5+4*8+10";System.out.println(evaluateTest(str));}public static int evaluateTest(String expression) {LinkedList<Integer> numOperator =new LinkedList<Integer>();LinkedList<Character> charOperator =new LinkedList<Character>();//1,将expression拼接成一个符号之间是空格间隔的字符串String newStr= strReset(expression);//2,将字符串进行截取,字符串截取接收的类型必须是数组String [] tokens = newStr.split(" ");//3，对数组进行遍历for(String token:tokens) {if(token.length()==0) {continue;}else if(token.charAt(0)=='(') {charOperator.push(token.charAt(0));}else if(token.charAt(0)=='+'||token.charAt(0)=='-') {while(!charOperator.isEmpty()&&(charOperator.peek()=='+'||charOperator.peek()=='-'||charOperator.peek()=='*'||charOperator.peek()=='/')) {//运算processAnOperator(numOperator,charOperator);}charOperator.push(token.charAt(0));}else if(token.charAt(0)=='*'||token.charAt(0)=='/') {while(!charOperator.isEmpty()&&(charOperator.peek()=='*'||charOperator.peek()=='/')) {//运算processAnOperator(numOperator,charOperator);}charOperator.push(token.charAt(0));}else if(token.charAt(0)==')') {while(charOperator.peek()!='(') {processAnOperator(numOperator,charOperator);}charOperator.pop();}else {numOperator.push(new Integer(token));}}//处理剩余的while(!charOperator.isEmpty()) {processAnOperator(numOperator,charOperator);}return numOperator.pop();}public static void processAnOperator(LinkedList<Integer> numOpertor,LinkedList<Character> charOperator) {int num1=numOpertor.pop();int num2=numOpertor.pop();char c =charOperator.pop();if(c=='+') {numOpertor.push(num2+num1);}else if(c=='-') {numOpertor.push(num2-num1);}else if(c=='*') {numOpertor.push(num2*num1);}else {numOpertor.push(num2/num1);}}public static String strReset(String expression) {StringBuilder sb = new StringBuilder();//遍历字符串for(int i=0;i<expression.length();i++) {char c = expression.charAt(i);if(c=='+'|| c=='-'||c=='*'||c=='/'||c=='('||c==')') {sb.append(' ');sb.append(c);sb.append(' ');}else {sb.append(c);}}return sb.toString(); }
}