栈与队列

LeetCode: [20] 有效的括号

栈:先进后出,队列:先进先出

栈与队列理论1

java Stack

1boolean empty() 
测试堆栈是否为空。
2Object peek( )
查看堆栈顶部的对象,但不从堆栈中移除它。
3Object pop( )
移除堆栈顶部的对象,并作为此函数的值返回该对象。
4Object push(Object element)
把项压入堆栈顶部。
5int search(Object element)
返回对象在堆栈中的位置,以 1 为基数。
6int size()
返回堆栈的大小与数量 (注意:不能再循环里使用stack.size(),因为pop会使size()变小)

Python Stack

python中没有确切的stack,但他的列表有pop,append(push)等栈的操作

具体可以查看https://docs.python.org/zh-cn/3/tutorial/datastructures.html

用两个栈实现队列

// LeetCode 232 用栈实现队列
class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        dumpStack();
        return stackOut.pop();
    }
    
    public int peek() {
        dumpStack();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.empty() && stackOut.empty();
    }

    private void dumpStack(){
        if(!stackOut.empty()) return;
        while(!stackIn.empty()){
            stackOut.push(stackIn.pop());
        }
    }
}

Java Queue

 Queue<Integer> queue = new LinkedList<>();
throw Exception返回false或null
添加元素到队尾add(E e)boolean offer(E e)
取队首元素并删除E remove()E poll()
取队首元素但不删除E element()E peek()
poll对空队列返回null

优先队列

// 小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a,b)->a-b);
// 大顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a,b)->b-a);

SNinfinite

立志成为Double E的程序猿

您可能还喜欢...

1 条回复

  1. 1月 16, 2022

    […] 栈与队列:https://infinite-zh.com/archives/675 […]

发表评论

您的电子邮箱地址不会被公开。