By

文章目录
  1. 1. 介绍
  2. 2. 使用两个队列实现栈
  3. 3. 两个栈实现队列

介绍

队列和栈是编程中非常经典并且使用的两个数据结构：

  • 队列：先入先出
  • 栈：先入后出

队列和栈的互操作主要考察对两个数据结构的认识

使用两个队列实现栈

假设现有队列q1和q2，要通过q1,q2来构建数据的先入后出
栈每次pop的都是最后一次push的值，所以可以在pop的时候将原有值都压入另一个队列，
直到最后一个元素时直接弹出
所以这样的话在push的时候就必须将元素进队到有值的那个队列，大致的逻辑图就是这样：

假如当前q1有值[4,3,2,1]，那么压入5的时候就会压入到q1
然后在pop的时候从q1里面依次将[4,3,2,1]压入到q2，直至最后一个元素5的时候直接返回即可

所以：

  • push的时候将输入压入已有值的队列
  • pop的时候将已有值的队列出队到另一个队列中，直达最后一个元素进行返回

看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
private Queue<Integer> queue1,queue2;
	
public Queue2Stack()
{
	
	this.queue1=new LinkedList<Integer>();
	this.queue2=new LinkedList<Integer>();
}

/**
 * 压入栈的时候   只需要向有数据的队列进行压入即可
 * 这样可以保证一个队列有值，另一个队列为空
 * @param a
 */
public void push(int a)
{
	if(this.queue1.size()==0)
		this.queue2.add(a);
	else
		this.queue1.add(a);
}

/**
 * 取数据的时候，有值对队列一直向空队列进行值的压入
 * 直到最后一个值 进行弹出即可
 * @return
 */
public int pop()
{
	if(this.queue1.size()==0)
		return pop(this.queue2,this.queue1);
	else
		return pop(this.queue1,this.queue2);
}

private int pop(Queue<Integer> normQueue,Queue<Integer> emptyQueue)
{
	if(normQueue.size()==0)
		return -1;
	
	while(normQueue.size()!=1)
	{
		emptyQueue.add(normQueue.poll());
	}
	
	return normQueue.poll();
}

看下测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args)
{
	Queue2Stack queue2Stack=new Queue2Stack();
	
	queue2Stack.push(1);
	queue2Stack.push(4);
	queue2Stack.push(5);
	
	System.out.println(queue2Stack.pop());
	System.out.println(queue2Stack.pop());
	System.out.println(queue2Stack.pop());
}

输出为：

5
4
1

两个栈实现队列

根据栈实现队里相对来说更加简单一点
现有栈s1,s2，如果现将输入压入s1,然后s1出栈再压入s2，此时可以发现s2如果再出栈的话就是队列的顺序了，看图

假如见当前数据入队到s1 [4,3,2,1]，此时入队5的时候继续入s1 [5,4,3,2,1]
再出队的时候判断s2中是否有值，如果有直接pop得值就是出队的值，否则遍历s1出栈 然后入栈到s2 [1,2,3,4,5]
再从s2进行pop即可

所以：

  • enQueue:总是见数据入队到s1
  • deQueue:先判断s2是否有值，如果有直接pop，否则将s1的数据全部压入到s2 再从s2进行pop

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private Stack<Integer> stack1,stack2;
	
	
public Stack2Queue()
{
	this.stack1=new Stack<Integer>();
	this.stack2=new Stack<Integer>();
	
}


/**
 * 入队  直接压入s1即可
 * @param a
 */
public void enQueue(int a)
{
	this.stack1.push(a);
}

/**
 * 出队 先判断s2是否有值，如果没有，现将s1的值压入s2，再返回
 * @return
 */
public int deQueue(){

	if(stack2.isEmpty())
	{
		while(!stack1.isEmpty())
		{
			stack2.push(stack1.pop());
		}
	}
	
	return stack2.pop();
	
}

看下测试

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args)
{
	Stack2Queue test=new Stack2Queue();
	test.enQueue(1);
	test.enQueue(4);
	test.enQueue(5);
	
	System.out.println(test.deQueue());
	System.out.println(test.deQueue());
	System.out.println(test.deQueue());
}

输出结果为：

1
4
5

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 介绍
  2. 2. 使用两个队列实现栈
  3. 3. 两个栈实现队列