分享

队与栈的相互实现

 头号码甲 2022-11-22 发布于北京

队列是一种先进先出的数据结构,栈是一种先进后出的数据结构.
这两种数据结构底层其实都是数组或者链表实现的,只是 API 限定了它们的特性

1.用栈实现队列
方法是用两个栈,stack1用于入队,stack2用于出队。当创造一个队列时,也就是创造了两个栈;当一个新元素入队的时候,就是在stack1之中加入新元素,当要出队列的时候,若stack1为空则队列为空,因为队列是先入先出,也就是要去除stack1中的最后一个元素,那么就把stack1中的元素依次加入stack2中,那么stack1中栈底元素就成了stack2的栈顶了,那么stack2 直接pop() 就完成任务,完成之后再把stack2的元素重新加入stack1之中。
剑指09.

class CQueue {
    private Stack<Integer> s1,s2;

    public CQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    
    public void appendTail(int value) {
        s1.push(value);

    }
    
    public int deleteHead() {
        if(s1.empty()){return -1;}
        while(!s1.empty()){
            s2.push(s1.pop());
        }
        int deleitem= s2.pop();
        while(!s2.empty()){
            s1.push(s2.pop());
        }
        return deleitem;
    }
}

栈结构实现一个队列,核心思想是利用两个栈互相配合。

2.用队列实现栈

class MyStack {
    private Queue<Integer> q1;
    int top_ele=0;

    /** Initialize your data structure here. */
    public MyStack() {
        q1=new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        q1.offer(x);
        top_ele=x;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int sz=q1.size();
        for(int i=0;i<sz-2;i++){
            q1.offer(q1.poll());
        }
        top_ele=q1.peek();
        q1.offer(q1.poll());
        return q1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return top_ele;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.isEmpty();
    }
}

这里的操作比较直接。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多