Implement Stack or Queue With GetMin?Max/Median 如何实现具有最大值、最小值和中间值的栈和队列


如何实现具有最大值、最小值和中间值的栈和队列
在研究“如何实现具有最大值、最小值和中间值的栈和队列”前,我们先考虑以下问题,然后由此过度到题目问题。
1)如何用两个栈实现队列
2)如何用两个队列实现栈
3)如何实现包含获取最小值函数getMin()的栈
4)如何实现包含获取中间值函数getMedian()的栈
5)如何实现包含获取最小值函数getMin()的队列

1 如何用两个栈实现队列

在研究问题前,我们可以用2个栈模拟一下具体操作过程,可以总结出以下规律:
入队:元素插入stack1;
出队:如果stack2中为空,先将stack1中元素入栈stack2,然后再将stack2的栈顶元素出栈。否则直接将stack2中元素出栈。

2 如何用两个队列实现栈

还是先用2个队列模拟栈的出栈和入栈过程,可以得出以下规律:
入栈:压入非空的那个队列
出栈:将非空队列中的n-1个元素压入空的队列中,然后将第n个元素出栈。
具体过程见下图(图来自《剑指offer》)

3 如何实现包含获取最小值函数的栈 // we can improve this 

问题:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的getMin函数。在该栈中,调用getMin、push及pop的时间复杂度都是O(1).
思路:用一个辅助栈stack2记住每次入栈stack1的当前最小值:在stack1入栈时,往stack2中加入当前最小值;stack1元素出栈时,stack2也出栈一个元素。最小值从stack2中获取及栈顶元素。

4 如何实现包含获取中间值函数的栈

如果能对栈中元素进行排序,那么排序好的中间值即为所求。问题3和问题4的具体代码如下,代码中同时实现了获取栈的最大值、最小值和中间值
public class Stack<E extends Comparable<E>> {
 
 private LinkedList<E> heartStack=new LinkedList<E>(); 
 private LinkedList<E> curMinStack=new LinkedList<E>(); //辅助栈,用于记录当前最小值
 private LinkedList<E> curMaxStack=new LinkedList<E>(); //辅助栈,用于记录当前最大值
 
 public void push(E e){
           heartStack.push(e);
           //当前最小值入栈curMinStack
           E currentMin=curMinStack.peek();
           if(currentMin.compareTo(e)>0){
            curMinStack.push(e);
           }//end if
           else
            curMinStack.push(currentMin);
           
           //当前最大值入栈curMinStack
           E currentMax=curMinStack.peek();
           if(currentMax.compareTo(e)<0){
            curMaxStack.push(e);
           }//end if
           else
            curMaxStack.push(currentMax);
 }//end push()
 
 public E pull(){
  if(isEmpty())
   return null;
  else{
   E e=heartStack.poll();
   curMinStack.poll();
   curMaxStack.poll();
   return e;
  }//end else
 }//end pull()
 
 public E getMax(){
  return curMaxStack.peek();
 }//end getMax()
 
 public E getMin(){
  return curMinStack.peek();
 }//end getMin()
 
 public int size(){
  return heartStack.size();
 }//end size()
 
 public boolean isEmpty(){
  return heartStack.isEmpty();
 }//end isEmpty()
 
 public E getMedian(){
  E[] e=(E[]) heartStack.toArray();
  Arrays.sort(e);
  return e[e.length/2];
 }//end getMedian()
 
 public E[] toArray(){
  return (E[])heartStack.toArray();
 }//end toArray()
}

5 如何实现包含获取最小值函数的队列

问题:定义队列的数据结构,请在该类型中实现一个能够得到队列的最小元素的getMin函数。在该队列中,调用getMin、insert及remove的时间复杂度都是O(1).
思路1:用最小堆实现优先队列,获取最小值时间复杂度为O(nlogn),但优先队列只能获取最小值,remove获取的不是先入队的元素。
思路2:
如果能用栈有效地实现队列,而栈的获取最小值的操作又很容易实现,那么队列的获取最小值的操作也很容易完成。
因为上面可用2个栈实现栈的min函数,而用2个栈可以实现队列。所以可以用已实现了获取最小值的栈stack1和stack2实现队列,而整个队列的最小值从min(stack1.getMin(),stack2.getMin())中获取。具体实现代码见问题6中代码。

6 如何实现具有最大值、最小值和中间值的栈和队列

问题5解决了用O(1)时间获取栈的最小值,那么解决最大值的问题也迎刃而解。对于获取队列的中间值,可以将队列中所有元素排序,然后获取排序后的中间值。
具体实现如下(代码中的stack类为上述问题4中已实现的可以获取最大值和最小值的栈):
public class ExmaPeekableQueue<E extends Comparable<E>>  implements IExamPeekableQueue{
 Stack stack1=new Stack();
 Stack stack2=new Stack();
 
 @Override
 public void enqueue(Comparable e) {
  stack1.push(e);  
 }//end enqueue()

 @Override
 public Comparable<E> dequeue() {
  if(stack2.isEmpty()){
   stack2.push(stack1.pull());
  }//end if
  
  return stack2.pull();
 }//end dequeue()

 @Override
 public Comparable<E> peekMedian() {
  Comparable[] arr=null; //用于存储队列中当前元素的数组
  
  if(stack1.isEmpty()){
   arr=stack2.toArray();
  }//end if
  else if(stack2.isEmpty()){
   arr=stack1.toArray();
  }//end if
  else{
   arr=new Comparable[size()];
   Comparable[] arrE1=stack1.toArray();
   Comparable[] arrE2=stack2.toArray();
   
   //将2个栈中的元素复制到一个数组中
   int i=0;
            for(;i<stack1.size();i++){
             arr[i]=arrE1[i];
            }//end for
            
            for(int j=0;j<stack2.size();j++){
             arr[++i]=arrE2[j];
            }//end for
  }//end else
   
  Arrays.sort(arr);
  return arr[arr.length/2];
 }//end peekMedian()

 @Override
 public Comparable peekMaximum() {
  Comparable max1=stack1.getMax();
  Comparable max2=stack2.getMax();
  
  if(max1.compareTo(max2)>0){
   return max1;
  }//end if
  else
   return max2;
 }

 @Override
 public Comparable<E> peekMinimum() {
  Comparable min1=stack1.getMin();
  Comparable min2=stack2.getMin();
  
  if(min1.compareTo(min2)>0){
   return min2;
  }//end if
  else
   return min1;
 }//end peekMinimum()

 @Override
 public int size() {
  return (stack1.size()+stack2.size());
 }//end size()
}//end class
http://blog.csdn.net/louistech/article/details/12450575
http://m.blog.csdn.net/blog/xiaorang_java/12450575

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts