`
sillycat
  • 浏览: 2551313 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

Interview(2)Stack and Queue

 
阅读更多
Interview(2)Stack and Queue

Stack
Last-in-first-out LIFO
Push  put one item into the stack,
Pop    get one item out of the stack

Some popular example will be the browser back and editor undo.

Some Popular operations
push(x)    pop()
getSize()    isEmpty()
top()

In JAVA, we have a class java.util.Stack
API - application programming interface - Interface

How to Implement Stack
#1 array S with N items, variable top
ExcpetionStackFull if data is over N items for the array.

Some core methods are as follow:
public Object pop() throws ExceptionStackEmpty {
    Object elem;
    if(isEmpty()){
        throw new ExceptionStackEmpty(“Error while pop method: Stack empty.");
    }
    elem = S[top];
    S[top - -] = null;
    return elem;
}

It is O(1) for all methods.

Java Method Stack
Java is call-by-value.

Fac(n) = n!
public static long factorial(long n) {
    if(n<=1)      return 1;
    else           return n*factorial(n-1);
}

Operand Stack

We can use stack to see if all (), {}, [], if they are all matched.
ParentMatch(X, n)
Inputs: array X with n items
Outputs: if () match in X

{
    initial stack S;
    for ( i = 0 to n -1){
        if(X[i] is ‘(‘){
            S.push(X[i]);
        }
        else if(X[i] is ‘)’){
            if(S.isEmpty()){
               return not_match;
            }
            if( S.pop() is not X[i]){
                return not_match;
            }
        }
    }

    if(S.isEmpty()){  return match; }
    else                { return not_match; }
}

HTML tag match

Queue
First-In-First-Out, FIFO

Basic method:
enqueue(x) : put item x into the queue
dequeue() : fetch the item from the queue

Other method:
getSize(), isEmpty(), front()

System can use array Q,
f - starter index of the Array
r - end index + 1 of the Array

Some import method implementation
public boolean isEmpty(){
    return (f == r);
}

public void enqueue(Object obj) throws ExceptionQueueFull{
    if(getSize() == capacity - 1){
        throw new ExceptionQueueFull(“Queue overflow");
    }
    Q[r] = obj;
    r = (r+1) % capacity;
}

public Object dequeue(){
    Object elem;
    if(isEmpty()){
        throw new ExceptionQueueEmpty(“Error dequeue: array empty");
    }
    elem = Q[f];
    Q[f] = null;
    f = (f+1) % capacity;
    return elem;
}

O(1)

Queue Application Samples
CPU, event and etc

Linked List
Singly Linked List
head - tail
element — content, next

This can save space.

Implement Stack on top of Singly Linked List
public class StackList implements Stack {
    protected Node top; //top elem
    protected int size;    //

    public StackList(){
        top = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return (top == null) ? true: false:
    }

    public void push(Object elem){
        Node v = new Node(elem, top); //create new node, next is the original top
        top = v;  //update top
        size++;  //update size
    }

    public Object pop() throws ExceptionStackEmpty{
        if(isEmpty()){
            throw new Exception
        }
        Object temp = top.getElem();
        top = top.getNext(); // update the top
        size—; //update size
        return temp;
    }
}

Implement Queue on top of Singly Linked List
public class QueueList implements Queue {
    protected Node head; //
    protected Node tail;
    protected int size;

    public QueueList(){
        head = tail = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return (0 == size) ? true: false;
    }

    public void enqueue(Object obj){
        Node node = new Node();
        node.setElem(obj);
        node.setNext(null);
        if( 0==size){
            head = node;
        }else{
            tail.setNext(node); // current node will be the tail
        }
        tail = node; //update the tail
        size++; // update the size
    }

    public Object dequeue() throws ExceptionQueueEmpty{
        if ( 0 == size){
            throw new ExceptionQueueEmpty(“dequeue Error: array is empty");
        }
        Object obj = head.getElem();
        head = head.getNext();
        size—;
        if(0 == size){
            tail = null;
        }
        return obj;
    }
}

Position
interface for position:
public interface Position{
    public Object getElem();
    public Object settled(Object e);
}

Double-ended Queue
insertFirst(x) - insertLast(x)
removeFirst() - removeLast()

first() - last()
getSize() - isEmpty()

Double Linked List
header - tailer
prev - next, element

public class DoubleEndQueue implement Deque{
    protected DLNode header;
    protected DLNode trailer;
    protected int size;

    public DoubleEndQueue(){
        header = new DLNode();
        trailer = new DLNode();
        header.setNext(trailer);
        trailer.setPrev(header);
        size = 0;
    }

    public boolean isEmpty(){
        return (0 == size) ? true: false;
    }

    public void insertFirst(Object obj){
        DLNode second = header.getNext();
        DLNode first = new DLNode(obj, header, second);
        second.setPrev(first);
        header.setNext(first);
        size++
    }

    public void insertLast(Object obj) {
        DLNode second = trailer.getPrev();
        DLNode first = new DLNode(obj, second, trailer);
        second.setNext(first);
        trailer.setPrev(first);
        size++;
    }

    public Object removeFirst() throws ExceptionQueueEmpty {
        if(isEmpty()){
            throw new ExceptionQueueEmpty(“Error: double end queue is empty");
        }
        DLNode first = header.getNext();
        DLNode second = first.getNext();
        Object obj = first.getElem();
        header.setNext(second);
        second.setPrev(header);
        size - - ;
        return obj;
    }

    public Objet removeLast() throws ExceptionQueueEmpty {
        if(isEmpty()){
            throw new ExceptionQueueEmpty(“Error: double end queue is empty");
        }
        DLNode first = trailer.getPrev();
        DLNode second = first.getPrev();
        Object obj = first.getElem();
        tailer.setPrev(second);
        second.setNext(trailer);
        size - - ;
        return obj;
    }
}

References:
https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html


分享到:
评论

相关推荐

    Problem.Solving.in.Data.Structures.and.Algorithms.Using.Cplusplus.epub

    We will be looking into a linked list, stack, queue, trees, heap, hash table and graphs. We will be looking into sorting, searching techniques. Then we will be looking into algorithm analysis, we ...

    Problem Solving in Data Structures & Algorithms Using Java

    We will be looking into a Linked List, Stack, Queue, Trees, Heap, Hash Table and Graphs. We will be looking into Sorting & Searching techniques. Then we will be looking into algorithm analysis, we ...

    Data Structures & Algorithms Using JavaScript

    We will be looking into a linked list, stack, queue, trees, heap, hash table and graphs. We will be looking into sorting, searching techniques. Then we will be looking into algorithm analysis, we ...

    Problem Solving in Data Structures & Algorithms Using C++

    We will be looking into a linked list, stack, queue, trees, heap, hash table and graphs. We will be looking into sorting, searching techniques. Then we will be looking into algorithm analysis, we ...

    Problem Solving in Data Structures & Algorithms Using Java, 2nd

    We will be looking into a Linked-List, Stack, Queue, Trees, Heap, Hash-Table and Graphs. We will also be looking into Sorting, Searching techniques. In last few chapters, we will be looking into ...

    c++ interview

    1. **容器**:熟悉vector、list、deque、stack、queue、set、map等容器的特性和使用场景。 2. **迭代器**:理解迭代器的概念,能够使用迭代器遍历容器中的元素。 3. **算法**:掌握STL提供的常用算法,如sort、find...

    玩转算法面试- Leetcode真题分门别类

    玩转算法面试-- Leetcode真题分门别类 资源列表: 00-The-Opening ...06-Stack-and-Queue 07-Binary-Tree-and-Recursion 08-Recurion-and-Backstracking 09-Dynamic-Programming 10-Greedy-Algorithms

    kaiyuzheng_interview_preparation.pdf

    #### BFS and DFS(广度优先搜索与深度优先搜索) - **广度优先搜索**:从根节点开始逐层向下遍历,直到找到目标节点。 - **深度优先搜索**:尽可能深地搜索树的分支。当路径走到尽头时,就回溯到上一个节点,然后...

    cSharp-Interview-necessary.rar_csharp 面试

    7. **集合与数据结构**:理解ArrayList、LinkedList、Dictionary、HashSet、Queue、Stack等常用集合的特性和使用场景。 8. **泛型**:知道如何使用泛型定义类、接口和方法,以及泛型的约束条件。 9. **委托与事件*...

    leetcode焦虑-Interview-Notes:采访笔记

    Stack Queue Graph traversals(BFS, DFS) 最短路径数学题 从之前的采访中吸取的错误和教训: 调度: 更加注意时间安排,在公司现场面试前保持2-3天的开放时间。 除非非常关键,否则不要立即安排任何事情。 可以联系 ...

    leetcode二维数组搜索-tech-interview-problems:面试、数据结构和问题解决刻意练习

    leetcode二维数组搜索DSA 准备资料库 FAANG 和其他人的数据结构和问题...Queue q = new LinkedList(); 哈希映射 - // Single Element HashMap Map.Entry majorityEle = null; // Interator for Hashmap Iterator ite

    lrucacheleetcode-Notes:有关编码、数据库、架构、DevOps等的动手学习笔记

    用Array实现Stack和Queue 用简单的Hashing function实现一个hashmap 用Adjacency Matrix和Adjacency List来实现Graph,然后在此基础上进行BFS和DFS Binary Search的迭代和递归 Merge Sort,Quick Sort,Counting ...

    Interview_Preperation

    6. **STL深入**:熟悉容器(如map、unordered_map、deque等)和算法(如排序、查找)的内部工作原理,以及适配器(如stack和queue)的使用。 7. **C++11及以后的新特性**:包括Lambda表达式、右值引用、auto关键字...

    leetcode题库-LeetCode:刷题记录

    queue_stack包为队列和栈专题记录。 linked_list包为链表专题记录。 hash_table包为哈希表专题记录。 data_structure_binary_tree包为二叉树专题记录。 introduction_to_data_structure_binary_search_tree包为二叉...

    dailyLearn:javascript,实现数据结构和算法题

    包含:list(列表),llist(链表),queue(队列),stack(堆),tree(树) 2)interview ———— 常见面试题目,练手 1ECMAScript5新增Array方法forEach的实现 2求最大公约数和最小公倍数 3声明提升 4判断字符...

    手写代码必备手册—面试必须

    2. 栈和队列(Stack & Queue):栈是后进先出(LIFO)的数据结构,只能在一端进行插入和删除操作;队列是先进先出(FIFO)的数据结构,允许在一端插入,在另一端删除。 3. 树(Tree):包括二叉树的遍历和重建...

    Cracking-the-coding-Interview:破解《编码面试》一书中的问题的Python解决方案

    - **栈(Stack)**:Python的列表可以用来实现后进先出(LIFO)的栈操作,如`append()`(压栈)和`pop()`(弹栈)。 - **队列(Queue)**:可以使用`collections.deque`实现先进先出(FIFO)的队列。 - **堆...

    leetcode与运算确定值-Interview-Prep:这仅用于面试准备,如果您想使用,请确保您“加星”此repo

    Stack是元素的集合,有两个主要操作: push ,添加到集合中, pop删除最近添加的元素 后进先出数据结构(LIFO) :最近添加的对象最先被删除 时间复杂度: 访问: O(n) 搜索: O(n) 插入: O(1) 删除: O(1) 队列 ...

    有用的C语言面试代码

    - 队列(Queue)遵循先进先出(FIFO)原则,数据的添加在一端(入队),删除在另一端(出队)。 - 栈(Stack)遵循后进先出(LIFO)原则,数据的添加和删除在同一端(顶)进行。 11. **递归函数的输出** ```c #...

Global site tag (gtag.js) - Google Analytics