Polyglot CheatSheet - Data Structures

Updated: 2018-06-25

Specialized or advanced data structures, beyond basic array, map and set.

Stack

Python

List provides pop() method for stack

stack = []
stack.append(1)
stack.pop()

Java

Stack<Object> stack = new Stack<>();

Queue

Python

There are 2 queues in Python:

  • queue.Queue: intended for allowing different threads to communicate using queued messages/data
  • collections.deque: intended as a data structure.
from collections import deque
q = deque()
q.append(1)
q.appendleft(0)
q.pop()
q.popleft()

Java

Queue<Object> queue = new LinkedList<>();

Summary of Queue methods

  • Throws exception: add(e), remove(), element()
  • Returns special: offer(e), poll(), peek()

Heap / PriorityQueue

Python

from heapq import heappush, heappop

heap = []
heappush(heap, 1)
heappop(heap)

Java

Simple case: integers

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(10);
pq.offer(3);

while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}

Dealing with objects(Java 8+):

import java.util.PriorityQueue;

PriorityQueue<Pair> pq = new PriorityQueue<>((Pair x, Pair y) -> x.priority - y.priority);

pq.offer(new Pair(1, 1));
pq.offer(new Pair(2, 10));
pq.offer(new Pair(3, 5));
pq.offer(new Pair(4, 9));
pq.offer(new Pair(5, 2));

while (!pq.isEmpty()) {
    System.out.print(pq.poll().value + " ");
}

The definition of Pair:

class Pair {
    int value;
    int priority;

    Pair(int v, int p) {
        value = v;
        priority = p;
    }
}
  • PriorityQueue((JavaDoc))[http://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html]
  • PriorityBlockingQueue((JavaDoc))[http://docs.oracle.com/javase/8/docs/api/java/util/concurrent/PriorityBlockingQueue.html]

BitSet

http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html