最常用的Collection是数组(Array)，其最常使用的获取数据的操作是随机获取(Random access), 在C++中一般称作 subscribe。
但是有时，我们想要限制处理数据的顺序。最常见的限制是：先进先出(First in first out), 后进先出(Last in first out)。分别对应2种数据结构 队列(Queue) 和 栈(Stack)。
classMyQueue { private: // store elements vector<int> data; // a pointer to indicate the start position int p_start; public: MyQueue() {p_start = 0;} /** Insert an element into the queue. Return true if the operation is successful. */ boolenQueue(int x){ data.push_back(x); returntrue; } /** Delete an element from the queue. Return true if the operation is successful. */ booldeQueue(){ if (isEmpty()) { returnfalse; } p_start++; returntrue; }; /** Get the front item from the queue. */ intFront(){ return data[p_start]; }; /** Checks whether the queue is empty or not. */ boolisEmpty(){ return p_start >= data.size(); } };
classMyCircularQueue { vector<int> data; int head; int size; public: /** Initialize your data structure here. Set the size of the queue to be k. */ MyCircularQueue(int k) { data.insert(data.begin(), k, 0); head = 0; size = 0; } /** Insert an element into the circular queue. Return true if the operation is successful. */ boolenQueue(int value){ if (isFull()) returnfalse; data[(head + size) % data.size()] = value; size++; returntrue; } /** Delete an element from the circular queue. Return true if the operation is successful. */ booldeQueue(){ if (isEmpty()) returnfalse; head = (head + 1) % data.size(); size--; returntrue; } /** Get the front item from the queue. */ intFront(){ if (isEmpty()) return-1; return data[head]; } /** Get the last item from the queue. */ intRear(){ if (isEmpty()) return-1; return data[(head + size - 1) % data.size()]; } /** Checks whether the circular queue is empty or not. */ boolisEmpty(){ return size == 0; } /** Checks whether the circular queue is full or not. */ boolisFull(){ return size == data.size(); } };
/** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue* obj = new MyCircularQueue(k); * bool param_1 = obj->enQueue(value); * bool param_2 = obj->deQueue(); * int param_3 = obj->Front(); * int param_4 = obj->Rear(); * bool param_5 = obj->isEmpty(); * bool param_6 = obj->isFull(); */
/** * Return the length of the shortest path between root and target node. */ intBFS(Node root, Node target) { Queue<Node> queue; // store all nodes which are waiting to be processed intstep=0; // number of steps neeeded from root to current node // initialize add root to queue; // BFS while (queue is not empty) { step = step + 1; // iterate the nodes which are already in the queue intsize= queue.size(); for (inti=0; i < size; ++i) { Nodecur= the first node in queue; return step if cur is target; for (Node next : the neighbors of cur) { add next to queue; } remove the first node from queue; } } return -1; // there is no path from root to target }
/** * Return the length of the shortest path between root and target node. */ intBFS(Node root, Node target) { Queue<Node> queue; // store all nodes which are waiting to be processed Set<Node> visited; // store all the nodes that we've visited intstep=0; // number of steps neeeded from root to current node // initialize add root to queue; add root to visited; // BFS while (queue is not empty) { step = step + 1; // iterate the nodes which are already in the queue intsize= queue.size(); for (inti=0; i < size; ++i) { Nodecur= the first node in queue; return step if cur is target; for (Node next : the neighbors of cur) { if (next is not in used) { add next to queue; add next to visited; } remove the first node from queue; } } } return -1; // there is no path from root to target }
/** * Return the length of the shortest path between root and target node. */ intBFS(Node root, Node target) { Queue<Node> queue; // store all nodes which are waiting to be processed Set<Node> visited; // store all the nodes that we've visited intstep=0; // number of steps neeeded from root to current node // initialize add root to queue; add root to visited; // BFS while (queue is not empty) { step = step + 1; // iterate the nodes which are already in the queue intsize= queue.size(); for (inti=0; i < size; ++i) { Nodecur= the first node in queue; return step if cur is target; for (Node next : the neighbors of cur) { if (next is not in used) { add next to queue; add next to visited; } } remove the first node from queue; } } return -1; // there is no path from root to target }
/* * Return true if there is a path from cur to target. */ booleanDFS(Node cur, Node target, Set<Node> visited) { returntrueif cur is target; for (next : each neighbor of cur) { if (next is not in visited) { add next to visted; returntrueifDFS(next, target, visited) == true; } } returnfalse; }
/* * Return true if there is a path from cur to target. */ booleanDFS(int root, int target) { Set<Node> visited; Stack<Node> stack; add root to stack; while (s is not empty) { Nodecur= the top element in stack; remove the cur from the stack; returntrueif cur is target; for (Node next : the neighbors of cur) { if (next is not in visited) { add next to visited; add next to stack; } } } returnfalse; }
classMyQueue { stack<int> a, b; public: /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ voidpush(int x){ a.push(x); } /** Removes the element from in front of queue and returns that element. */ intpop(){ if (b.empty()) { while (!a.empty()) { b.push(a.top()); a.pop(); } } int ret = b.top(); b.pop(); return ret; } /** Get the front element. */ intpeek(){ if (b.empty()) { while (!a.empty()) { b.push(a.top()); a.pop(); } } return b.top(); } /** Returns whether the queue is empty. */ boolempty(){ return a.empty() && b.empty(); } };
/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * bool param_4 = obj.empty(); */