一、前提
摘自java程序设计教程(华盛顿大学/斯坦福大学著，陈志等译)-机械工业出版社
1、1栈/队列基础
像线性表一样，栈与队列中存储一组有序的值。这类数据结构至少需要支持下面几种操作：
将值放入数据结构中（添加操作）；
将值从数据结构中取出（删除操作）；
检查数据结构中是否还有值（判断数据结构是否为空）。
栈与队列很相似：都是以某种特定的顺序存储元素序列。栈是一种后进先出/LIFO(LAST IN FIRST OUT)的结构，也就是最后保存到结构中的元素会最先被访问。队列则是一种先进先出/FIFO(FIRST IN FIRST OUT)的结构，也就是最早保存到结构中的元素会最先被访问。
1、2栈的概念
对于栈这种数据结构来说，所有支持的操作都集中在它的一端，我们称为栈的顶部。添加元素的操作成为压栈(push)，删除元素的操作称为出栈(pop)。压栈会将新元素保存到栈的顶部，出栈会将栈顶部的元素删除。
举例：我们需要用盘子的时候一般会取最上面的一个，因为如果用下面的盘子，那么会将上面的盘子先挪开。类似的，洗干净的盘子一般直接摞在最上面，而不放在最底下。所以利用栈的这个特性，可以改变元素的顺序。嘴后面加入的元素在出栈时会排在最前面，这样元素的顺序就反转了。
1、2、1Stack与Vector
栈是一种泛型结构，准确的定义为Stack
1、2、2例子
package org.mbox.test1;
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
String str[] = {"aa","bb","cc","dd"};
Stack<String> stack = new Stack<String>();
for (int i = 0; i < str.length; i++) {
stack.push(str[i]);
}
System.out.println("栈为:"+stack);
System.out.println("栈的大小为:"+stack.size());
System.out.println("删除并返回栈最新顶端的值:"+stack.pop());
System.out.println("逻辑删除栈顶端的值并返回原栈顶端的值:"+stack.peek());
//以下两个方法的输出是和原数组的顺序是相反的。
//pop方法删除栈顶端的值并返回最新栈顶端的值
//顺序打印cc,bb,aa
// while(!stack.isEmpty()){
// System.out.println("pop:"+stack.pop()+" .");
// }
//peek方法不删除栈顶端的值但返回删除后栈顶端的最新值
//注意peek元素并不会修改元素
//一直打印cc是死循环
// while(!stack.isEmpty()){
// System.out.println("peek:"+stack.peek()+" .");
// }
}
}
1、3队列的概念
与栈不同，队列允许在数据结构的两端进行操作：在队列尾部添加数据，从队列头部删除数据。队列支持的操作与栈相同，但名称有区别。队列的添加和删除操作有时也称为入队和出队操作。
1、3、1Queue
Queue
1、3、2例子
输出结果表明队列中元素存储的顺序就是各个元素加入的顺序。
package org.mbox.test1;
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
String str[]= {"22","33","44","55","66"};
Queue<String> queue = new LinkedList<String>();
for(String test:str){
queue.add(test);
}
System.out.println("队列为:"+queue);
System.out.println("队列大小为:"+queue.size());
System.out.println("队列逻辑删除首部元素并返回原元素peek:"+queue.peek());
// System.out.print("被删除的队列中的每一个值为:");
// while(!queue.isEmpty()){
// System.out.print(queue.remove()+ " ");//返回删除的每个新队列的首部的值
// }
//如果要测试下面的方法，记得把上面的打开
//下面永久打印22的死循环
// while(!queue.isEmpty()){
// System.out.println(queue.peek());
// }
}
}
1、4栈与队列常用操作
1、4、1随机生成栈
package org.mbox.test1;
import java.util.Random;
import java.util.Stack;
public class StackExample2 {
public static void main(String[] args) {
Stack<Integer> stack = getRandomStack(10);
System.out.println("栈为:"+stack);
}
//生成随机栈
public static Stack<Integer> getRandomStack(int number){
Stack<Integer> stack = new Stack<Integer>();
Random random = new Random();
for (int i =0; i < number; i++) {
stack.push(random.nextInt(number));
}
return stack;
}
}
1、4、2随机生成队列
package org.mbox.test1;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
public class QueueExample2 {
public static void main(String[] args) {
Queue<Integer> queue = getRandomQueue(10);
System.out.println("新队列为:"+queue);
}
//生成随机的队列
public static Queue<Integer> getRandomQueue(int number){
Queue<Integer> queue = new LinkedList<Integer>();
Random random = new Random();
for (int i =0; i < 10; i++) {
queue.add(random.nextInt(number));
}
return queue;
}
}
1、4、3栈与队列互换
package org.mbox.test1;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
public class StackQueueExample {
public static void main(String[] args) {
Queue<Integer> oldQueue = getRandomQueue(10);
System.out.println("第一版队列:"+oldQueue);
Stack<Integer> newStack = getStackOfQueue(oldQueue);
System.out.println("通过第一版队列生成栈:"+newStack);
Queue<Integer> newQueue = getQueueOfStack(newStack);
System.out.println("通过第一版生成的栈生成的队列:"+newQueue);
}
//队列换成栈
public static Stack<Integer> getStackOfQueue(Queue<Integer> queue){
Stack<Integer> stack = new Stack<Integer>();
while(!queue.isEmpty()){
int n =queue.remove();//注意这里是remove方法
stack.push(n);//注意这里是push压栈方法,而不是add方法,注意两个方法的区别
}
return stack;
}
//栈换成队列
public static Queue<Integer> getQueueOfStack(Stack<Integer> stack){
Queue<Integer> queue = new LinkedList<Integer>();
while(!stack.isEmpty()){
int n =stack.pop();//注意这里是pop方法而不是peek方法
queue.add(n);//注意这里是add方法
}
return queue;
}
//生成随机的队列
public static Queue<Integer> getRandomQueue(int number){
Queue<Integer> queue = new LinkedList<Integer>();
Random random = new Random();
for (int i =0; i < 10; i++) {
queue.add(random.nextInt(number));
}
return queue;
}
//生成随机栈
public static Stack<Integer> getRandomStack(int number){
Stack<Integer> stack = new Stack<Integer>();
Random random = new Random();
for (int i =0; i < number; i++) {
stack.push(random.nextInt(number));
}
return stack;
}
}
1、4、4队列求和（注意和栈求和的区别）
package org.mbox.test1;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
public class QueueExample3 {
public static void main(String[] args) {
Queue<Integer> queue = getRandomQueue(10);
System.out.println("执行前queue:"+queue);
System.out.println("相加结果:"+sum(queue));
System.out.println("执行后queue:"+queue);
}
//生成随机的队列
public static Queue<Integer> getRandomQueue(int number){
Queue<Integer> queue = new LinkedList<Integer>();
Random random= new Random();
for (int i =0; i < 10; i++) {
queue.add(random.nextInt(number));
}
return queue;
}
//队列求和
public static int sum(Queue<Integer> queue){
int sum = 0;
//1
// //用while循环改变了原队列的内容是不可取的
//但是可以使用一个新的队列进行处理
// Queue<Integer> queue2 = new LinkedList<Integer>();
while(!queue.isEmpty()){
int n =queue.remove();
sum +=n;
// queue2.add(n);
}
// System.out.println(queue2);
//2
// for (int i =0; i < queue.size(); i++) {
//// System.out.println(i);
// int n = queue.remove();
// sum +=n;
// //注意在使用下述原队列进行处理的时候,
// //如果不执行add操作,那么sum只会加了前五个值,因为remove的同时这个队列的值的个数也是随之减少的
// queue.add(n);
// //队列的定义是从首部删除,尾部进入
// //虽然新元素进入了队列,但是还是从首部一个个删除的,此时队列的长度是保持不变的
// //所以等删除到最后一个元素的时候,新加入的10个元素还是以前的10个元素,是不会变的,此时for循环也结束了。
// }
return sum;
}
}
1、4、5栈求和（注意和队列求和的区别）
package org.mbox.test1;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
public class StackExample3 {
public static void main(String[] args) {
Stack<Integer> stack = getRandomStack(10);
System.out.println("执行前栈为:"+stack);
System.out.println("求和结果为:"+sum(stack));
System.out.println("执行后栈为:"+stack);
}
//生成随机栈
public static Stack<Integer> getRandomStack(int number){
Stack<Integer> stack = new Stack<Integer>();
Random random = new Random();
for (int i =0; i < number; i++) {
stack.push(random.nextInt(number));
}
return stack;
}
//栈求和
public static int sum(Stack<Integer> stack){
int sum = 0;
// //1方案
// //下述操作是不可行的,栈是后进先出原则
// //下列操作相当于把最后一个元素加了10次
// //看起来生成的最终结果跟原结果相同,但是是不对的
// for (int i =0; i < stack.size(); i++) {
// int n =stack.pop();//拿出来尾部元素
// sum +=n;
// stack.push(n);//把拿出来的尾部元素再放回原位置
// }
// //2
// //下述操作只把最后五个数相加了
// for (int i =0; i < stack.size(); i++) {
// System.out.println(i);
// int n =stack.pop();
// sum +=n;
// }
//3
Queue<Integer> queue = new LinkedList<Integer>();
while(!stack.isEmpty()){
int n =stack.pop();
sum +=n;
queue.add(n);
}
System.out.println(queue);
System.out.println(getStackOfQueue(queue,stack));
System.out.println(getQueueOfStack(stack,queue));
System.out.println(getStackOfQueue(queue,stack));
return sum;
}
//队列换成栈
public static Stack<Integer> getStackOfQueue(Queue<Integer>queue,Stack<Integer> stack){
while(!queue.isEmpty()){
int n =queue.remove();//注意这里是remove方法
stack.push(n);//注意这里是push压栈方法,而不是add方法,注意两个方法的区别
}
return stack;
}
//栈换成队列
public static Queue<Integer> getQueueOfStack(Stack<Integer>stack,Queue<Integer> queue){
while(!stack.isEmpty()){
int n =stack.pop();//注意这里是pop方法而不是peek方法
queue.add(n);//注意这里是add方法
}
return queue;
}
}
1、5栈和队列高级操作
1、5、1删除队列中指定的元素
package org.mbox.test1;
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample4 {
public static void main(String[] args) {
Queue<Integer> queue = getQueue();
System.out.println(""+ queue);
System.out.println(getNewQueue(queue,5));
}
public static Queue<Integer>getQueue(){
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(5);
queue.add(5);
queue.add(2);
queue.add(51);
queue.add(5);
queue.add(3);
queue.add(5);
queue.add(6);
return queue;
}
public static Queue<Integer> getNewQueue(Queue<Integer> queue,int number){
int oldSize= queue.size();//这里一定要先获取到原队列的长度,不然会造成数据错误
for (int i =0; i < oldSize; i++) {
int n =queue.remove();
if(n !=number){
queue.add(n);
}
}
return queue;
}
}
1、5、2比较两个栈奇偶是否一样
package org.mbox.test1;
import java.util.Stack;
public class StackExample4 {
public static void main(String[] args) {
Integer array1[] = {1,2,3,4,5,6,7};
Integer array2[] = {11,12,13,15,15,16,17};
Stack<Integer> stack1 = getStack(array1);
Stack<Integer> stack2 = getStack(array2);
System.out.println("stack1:"+stack1);
System.out.println("stack2:"+stack2);
System.out.println(checkStack(stack1,stack2));
}
public static boolean checkStack(Stack<Integer> stack1,Stack<Integer> stack2){
System.out.println("1--------------------stack1:"+stack1);
System.out.println("1--------------------stack2:"+stack2);
if(stack1.size()!= stack2.size()){
returnfalse;
}else{
boolean flag = true;
Stack<Integer> stack3 = new Stack<Integer>();
while(flag&& !stack1.isEmpty() && !stack2.isEmpty()){
intn1 = stack1.pop();
intn2 = stack2.pop();
if((n1% 2) != (n2 % 2)){
flag= false;
}
stack3.push(n1);
stack3.push(n2);
}
System.out.println("2--------------------stack1:"+stack1);
System.out.println("2--------------------stack2:"+stack2);
System.out.println("2--------------------stack3:"+stack3);
while(!stack3.isEmpty()){
stack2.push(stack3.pop());
stack1.push(stack3.pop());
}
System.out.println("3--------------------stack1:"+stack1);
System.out.println("3--------------------stack2:"+stack2);
System.out.println("3--------------------stack3:"+stack3);
return flag;
}
}
public static Stack<Integer> getStack(Integer array[]){
Stack<Integer> stack = new Stack<Integer>();
for(Integer num : array){
stack.push(num);
}
return stack;
}
}