数据结构|栈和队列

Scroll Down

1. 定义

栈:栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈的特点:先进后出(LIFO:last in first out)
stack.png

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列的特点:先进先出(FIFO:first in first out)
queue.png

2. 利用栈实现队列

由于栈是先进后出的结构,而队列是先进先出的结构,因此在利用栈实现队列的时候,需要使用一个额外的栈。这个栈的目的是用来反转当前栈,一个元素需要经过两个栈才能出队列,在经过第一个栈时元素顺序被反转,经过第二个栈时再次被反转,此时就是先进先出顺序。实现代码如下:

public class MyQueue {

    private Stack<Integer> stack;
    private Stack<Integer> queueStack;

    //将栈反转,转换成队列
    private void stack2Queue(){
        //当队列栈为空的时候,才将栈逆序存到队列栈中
        //否则直接对队列栈进行处理
        if (queueStack.isEmpty()){
            while (!stack.isEmpty()){
                queueStack.push(stack.pop());
            }
        }
    }

    //构造函数
    public MyQueue() {
        stack = new Stack<>();
        queueStack = new Stack<>();
    }

    //在队尾添加元素
    public void push(int x) {

        stack.push(x);
    }

    //将队首的元素移除并返回
    public int pop() {
        //如果队列栈为空,则将栈转化为队列栈
        //再对队列栈进行出栈操作
        stack2Queue();
        return queueStack.pop();
    }

    //返回队首的元素,但不移除(相当于查询队首元素)
    public int peek() {
        stack2Queue();
        return queueStack.peek();
    }

    //判断当前队列是否为空
    public boolean empty() {
        //当且仅当两个栈都为空的时候返回true
        return stack.isEmpty()&&queueStack.isEmpty();
    }

    @Test
    public void test(){
        push(1);
        push(2);
        push(3);
        System.out.println(empty());
        System.out.println(peek());
        System.out.println(pop());
        System.out.println(peek());
    }

}

3. 利用队列实现栈

由于水平有限,本文只实现了用两个队列来模拟一个栈。事实上用队列来模拟栈,只需要一个队列即可。使用两个队列的思路如下:
两个队列的轮流使用,始终保持一个队列为空。
(1)push()方法直接添加在空的队列中;
(2)pop()方法在于将装载元素中的队列的前n-1都移到另外一个空队列中(利用size方法),最后一个元素直接取出并返回。
(3)top()方法和pop()方法基本思路一致,只是在前n-1个元素移动后,将最后一个元素赋值,然后在压入队列中去。
(4)empty()方法直接判断两个队列是否都为空即可。

public class MyStack {

    private LinkedList<Integer> queue1;
    private LinkedList<Integer> queue2;

    //构造函数
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    //添加一个元素到栈顶
    public void push(int x) {
        if (queue1.isEmpty()) queue2.add(x);
        if (queue2.isEmpty()) queue1.add(x);
    }

    //移除并返回栈顶元素
    public int pop() {
        if (queue1.isEmpty()){
            while (queue2.size()>1){
                queue1.add(queue2.poll());
            }
    	    //直接返回队列中的最后一个元素
            return queue2.poll();
        }
        else {
            while (queue1.size()>1){
                queue2.add(queue1.poll());
            }
            return queue1.poll();
        }
    }

    //返回栈顶元素但不移除
    public int top() {
        int top = 0;
        if (queue1.isEmpty()){
            while (queue2.size()>1){
                queue1.add(queue2.poll());
            }
            top = queue2.poll();
            //将原先非空队列的最后一个元素记录下来,并将该元素压入
            //原先空队列的队尾。
            queue1.add(top);
        }
        else {
            while (queue1.size()>1){
                queue2.add(queue1.poll());
            }
            top = queue1.poll();
            queue2.add(top);

        }
        return top;
    }

    //判断当前栈是否为空
    public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();
    }

    @Test
    public void test(){
        push(1);
        push(2);
        push(3);
        System.out.println("栈是否为空:"+empty());
        System.out.println("栈顶元素:"+top());
        System.out.println("栈顶元素出栈");
        pop();
        System.out.println("栈是否为空:"+empty());
        System.out.println("栈顶元素:"+top());
        System.out.println("栈顶元素出栈");
        pop();
        System.out.println("栈是否为空:"+empty());
        System.out.println("栈顶元素:"+top());
        System.out.println("栈顶元素出栈");
        pop();
        System.out.println("是否为空:"+empty());
    }

}