《iOS面试题整理》- 栈和队列

两个栈实现队列

思路：

1. stack1 用于存放 push 的元素
2. pop 的时候分两种情况

• stack2 为空, 把stack1 的栈顶元素弹出, 然后压入 stack2, 最后调用 stack2.pop 方法弹出
• stack2 不为空, 直接调用 stack2.pop 方法弹出

  Stack *stack1 = Stack new();
  Stack *stack2 = Stack new();

// 入队列
void add(data) {
  stack1.push(data);
}

// 出队列
void poll() {

    if (stack1.empty() && stack2.empty()) return ;
    
// 队列2 有元素直接弹出
    if (!stack2.empty()) {
        stack2.pop();
        return;
    } 
    
    // 把队列1的元素都给队列2
      while(!s1.empty()) {
        data = s1.top();
        stack2.push(data);
       stack1.pop();  
    }
    
    // 模拟出队列操作
     stack2.pop();
  }
}

两个队列实现栈

思路：

1. 如果两个队列为空, 则 push 操作在任意一个queue中执行都行
2. 如果有队列不为空, 则 push 操作在队列不为空的队列中执行
3. pop 操作, 把有数据的队列除队尾的元素, 全部出队列压入另外一个不为空的队列中, 最后 pop 队尾元素

两个队列在操作过程中总保持其中一个队列为空

  Queue *queue1 = Queue new();
  Queue *queue2 = Queue new();

  // 入栈
  void push(data) {
    // 判断两个队列是否同时为空
      if (queue1.empty() && queue2.empty) {
        queue1.add(data);
        return;
    }

    if (queue1.size() > 0) {
      queue1.add(data);
    } else {
      queue2.add(data);
    }

  // 出栈
  void pop() {
    if (queue1.empty() && queue2.empty()) return;
    
    if (!queue1.empty()) {
       
        while(queue1.size() > 0) {
            result = queue1.poll();
            if(queue1.size()  != 0) {
                queue2.add(result);
            }
        }
        
    } else {
       
        while(queue2.size() > 0) {
            result = queue2.poll();
            if (queue2.size() != 0) {
                queue1.add(result);
            }
        }
        
    }
}