算法初级——栈和队列的相互实现

如何仅用队列结构实现栈结构?
/*
* 队列结构实现栈
* 两个队列,一个主队列,一个辅助队列
* 从压栈开始操作,主队列压栈,弹出时,需要判断主队列是否为空,如果为空,抛出异常,然后判断主队列长度,
* 如果主队列长度为一,直接弹出,否则将主队列除最后一个元素外的所有元素全部压入辅助队列,主队列和辅助队列交换,
* 然后弹出主队列留的最后一个元素,即为栈所要弹出的元素。查询操作,判断主队列是否为空,
* 如果不为空,判断主队列长度是否等于一,如果不等于一,将主队列除最后一个元素外的所有元素全部压入辅助队列,
* 然后赋值给临时变量,然后再将最后一个元素压入辅助栈,交换主队列和辅助队列,返回临时变量。,
*/

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.LinkedList;
import java.util.Queue;

public class QueuetoStack {
    public static class Mystack{
        private Queue<Integer>queue1;
        private Queue<Integer>queue2;
       
        public Mystack(){
            queue1 = new LinkedList<Integer>();
            queue2 = new LinkedList<Integer>();
        }
        public void push(int num) {
            queue1.add(num);
        }
        public int pop() {
            if(queue1.isEmpty()) {
                throw new RuntimeException("empty");
            }
            while(queue1.size() > 1) {
                queue2.add(queue1.poll());
            }
            int res= queue1.poll();
            swap();
            return res;
        }
        public int peek(){  
            if(queue1.isEmpty()){  
                throw new RuntimeException("the stack is empty!");  
            }  
            //队列1的数全部压进队列2  
            while(queue1.size()!=1){  
                queue2.add(queue1.poll());  
            }  
            int res = queue1.poll();  
            queue2.add(res);  
            swap();  
            return res;  
        }
        private void swap() {
            // TODO Auto-generated method stub
            Queue<Integer>queue = queue1;  
            queue1 = queue2;  
            queue2 = queue;
        }
        public boolean isEmpty(){  
            return queue1.isEmpty();  
        }
    }
    public static void main(String[] args) {
        Mystack myStack1 = new Mystack();  
        myStack1.push(3);  
        myStack1.push(6);  
        myStack1.push(9);  
        System.out.println("===="+myStack1.peek()+"====");  
        while(!myStack1.isEmpty()){
            System.out.println("===="+myStack1.peek()+"====");
            System.out.println(myStack1.pop());
        }
    }
}

如何仅用栈结构实现队列结构?
/*
* 栈结构实现队列
* 两个栈,一个主栈,一个辅助栈
* 压入元素:主栈压入元素;弹出操作:判断主栈是否为空,如果主栈不空,将主栈所有元素全部压入辅助栈,弹出辅助栈的第一个元素,
* 然后判断辅助栈是否为空,若不为空,将辅助栈的所有元素再压回到主栈内;查询操作:判断主栈是否为空,如果主栈不空,
* 将主栈所有元素全部压入辅助栈,执行辅助栈的peek操作,然后判断辅助栈是否为空,若不为空,将辅助栈的所有元素再压回到主栈内;
*/

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.Stack;

public class StacktoQueue {
    public static class Myqueue{
        private Stack<Integer>stack1;  
        private Stack<Integer>stack2;
        public Myqueue(){  
            stack1 = new Stack<Integer>();  
            stack2 = new Stack<Integer>();  
        }
        public void push(int num) {
            stack1.push(num);
        }
        public int pull() {
            if(stack1.isEmpty()) {
                throw new RuntimeException("empty");
            }
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            int res = stack2.pop();
            while(!stack2.isEmpty()){  
                stack1.push(stack2.pop());  
            }  
            return res;
        }
        public int peek(){  
            if(stack1.isEmpty()){  
                throw new RuntimeException("the queue is empty!");  
            }  
            while(!stack1.isEmpty()){  
                stack2.push(stack1.pop());  
            }  
            int res = stack2.peek();  
            while(!stack2.isEmpty()){  
                stack1.push(stack2.pop());  
            }  
            return res;  
        }
        public boolean isEmpty(){  
            return stack1.isEmpty();  
        }
       
       
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Myqueue myQueue = new Myqueue();  
        myQueue.push(2);  
        myQueue.push(4);  
        myQueue.push(7);  
        System.out.println("===="+myQueue.peek()+"====");  
        while(!myQueue.isEmpty()){
            System.out.println("===="+myQueue.peek()+"====");
            System.out.println(myQueue.pull());  
        }  

    }

}
0 条评论
发表一条评论