导入
使用队列实现栈
使用队列实现一个后进先出（LIFO）栈。
说明
给定一个具有常见操作如 enqueue()、dequeue() 和 size() 的队列类，实现一个具有 push()、pop() 和 isEmpty() 操作的栈类。isEmpty() 函数应在栈为空时返回 true，否则返回 false。
注意：如果栈为空，
pop()函数应返回 。
栈是一种数据结构，对象的插入和删除遵循后进先出（LIFO）原则。元素被添加到栈顶，并从栈顶移除。栈有两个重要功能：
push()：将元素插入栈顶。pop()：从栈顶移除元素并返回它。
队列是一种数据结构，对象的插入和删除遵循先进先出（FIFO）原则，即在队列中停留时间最长的对象最先被移除。队列有两个重要功能：
enqueue()：将元素插入队列末尾。dequeue()：从队列前端移除元素并返回它。
示例输入
1Push(7), Pop(), Push(9), Push(10), Pop(), IsEmpty()
期望输出
17, 10, false
自行尝试
多标签代码
C++
1#include <iostream> 2#include <queue> 3 4using namespace std; 5 6class StackUsingQueue 7{ 8 // 写 - 你的 - 代码 9 public: 10 queue<int> queue1; 11 12 void Push(int data) { 13 } 14 15 bool IsEmpty() { 16 return false; 17 } 18 19 int Pop() { 20 return -2; 21 } 22};
Java
1// 导入所需函数 2import java.util.*; 3 4class StackUsingQueue { 5 // 写 - 你的 - 代码 6 Queue<Integer> queue1 = new ArrayDeque<Integer>(); 7 8 void push(int data) {} 9 10 boolean isEmpty() { 11 return false; 12 } 13 14 int pop() { 15 return -2; 16 } 17}
Python
1class StackUsingQueue: 2 # 写 - 你的 - 代码 3 def __init__(self): 4 self.queue1 = deque() 5 6 def push(self, data): 7 return data 8 9 def is_empty(self): 10 return False 11 12 def pop(self): 13 return -2
JS
1class StackUsingQueue { 2//写 - 你的 - 代码 3 constructor() { 4 this.queue1 = []; 5 } 6 7 push(data){ 8 return data; 9 } 10 11 isEmpty() { 12 return false; 13 } 14 15 pop() { 16 return -2; 17 } 18}
Ruby
1class StackUsingQueue 2# 写 - 你的 - 代码 3 attr_accessor :queue1 4 def initialize() 5 @queue1 = [] 6 end 7 8 def push(data) 9 10 end 11 12 def is_empty() 13 return false 14 end 15 16 def pop() 17 return -2 18 end 19 20end
Go
1package main 2 3import ( 4 "fmt" 5 "math" 6 "strings" 7 "errors" 8 "sync" 9 "strconv" 10 "encoding/json" 11) 12/* 13 写 - 你的 - 代码 14 我们提供了一个自定义的队列数据结构实现 15 因为 Go 语言没有内置的队列实现。 16 que := new(Queue) // 队列实例化示例 17 我们的队列支持以下函数： 18 Enqueue(<对象>): // 将对象推入队列前端 19 Dequeue().(<对象类型>): // 从队列顶部移除类型为 BinaryTreeNode 的对象 20 Size(): // 返回当前已推入队列的元素数量 21 Peek().(<对象类型>): // 返回栈顶元素但不修改队列 22*/ 23type StackUsingQueue struct { 24 queue1 Queue 25} 26 27func (q *StackUsingQueue) InitQueue() { 28 q.queue1 = Queue{} 29} 30 31func (s *StackUsingQueue) Push(data int) { 32 33} 34 35func (s *StackUsingQueue) IsEmpty() bool { 36 return false 37} 38 39func (s *StackUsingQueue) Pop() int { 40 return -2 41}
注意：向面试官提出的一个好问题是：“在栈的实现中，哪个操作需要更快？”
解法 1
第一个解法会使 push() 操作更快。我们使用两个队列，分别命名为 queue1 和 queue2。
让我们看看 push() 和 pop() 操作的样子：
1push(): 2 始终在 queue1 中入队 3 4pop(): 5 如果栈大小为 0， 6 返回 -1 7 8 如果 queue1 中有元素， 9 将 queue1 中的所有元素出队并入队到 queue2，除了最后一个元素。 10 11 上述找到的最后一个元素将在交换 queue1 和 queue2 的引用后返回。
让我们通过一个例子来理解这个算法。我们对栈执行 push() 和 pop() 操作，并观察在 queue1 和 queue2 上执行的相应 enqueue() 和 dequeue() 操作。
多标签代码
C++
1#include <iostream> 2#include <queue> 3#include <cmath> 4using namespace std; 5 6class StackUsingQueue { 7 public: 8 queue <int> queue1; 9 queue <int> queue2; 10 11 void Push(int data) { 12 queue1.push(data); 13 } 14 15 // 使用队列类的默认 size() 方法 16 // 检查栈是否为空 17 bool IsEmpty() { 18 return queue1.size() + queue2.size() == 0; 19 } 20 21 // 辅助函数，使用临时队列交换我们的队列 22 void SwapQueues() { 23 queue <int> temp = queue1; 24 queue1 = queue2; 25 queue2 = temp; 26 } 27 28 int Pop() { 29 if (IsEmpty()) { 30 return -1; 31 } 32 33 while (queue1.size() > 1) { 34 int value = queue1.front(); 35 queue1.pop(); 36 queue2.push(value); 37 } 38 39 // 当 queue1 中只剩一个元素时，将其出队 40 // 并交换队列 41 int value = queue1.front(); 42 queue1.pop(); 43 SwapQueues(); 44 return value; 45 } 46}; 47 48int main() { 49 StackUsingQueue sq; 50 51 cout << "Pop(): " << sq.Pop() << endl; 52 // PrintStack 函数允许我们轻松 53 // 可视化栈的状态 54 PrintStack(sq); 55 56 sq.Push(3); 57 cout << "\nPush(3): " << endl; 58 PrintStack(sq); 59 60 sq.Push(5); 61 cout << "\nPush(5): " << endl; 62 PrintStack(sq); 63 64 sq.Push(9); 65 cout << "\nPush(9): " << endl; 66 PrintStack(sq); 67 68 cout << "\nPop(): " << sq.Pop() << endl; 69 PrintStack(sq); 70 71 sq.Push(10); 72 cout << "\nPush(10):" << endl; 73 PrintStack(sq); 74 75 sq.Push(16); 76 cout << "\nPush(16):" << endl; 77 PrintStack(sq); 78 79 cout << "\nPop(): " << sq.Pop() << endl; 80 PrintStack(sq); 81}
Java
1// 导入所需函数 2import java.util.*; 3 4class StackUsingQueue { 5 Queue<Integer> queue1 = new ArrayDeque<Integer>(); 6 Queue<Integer> queue2 = new ArrayDeque<Integer>(); 7 8 void push(int data) { 9 queue1.add(data); 10 } 11 12 // 使用队列类的默认 size() 方法 13 // 检查栈是否为空 14 boolean isEmpty() { 15 return queue1.size() + queue2.size() == 0; 16 } 17 18 // 辅助函数，使用临时队列交换我们的队列 19 void swapQueues() { 20 Queue<Integer> queue3 = queue1; 21 queue1 = queue2; 22 queue2 = queue3; 23 } 24 25 int pop() { 26 if (isEmpty()) { 27 return -1; 28 } 29 30 while (queue1.size() > 1) { 31 queue2.add(queue1.remove()); 32 } 33 34 // 当 queue1 中只剩一个元素时，将其出队 35 // 并交换队列 36 int value = queue1.remove(); 37 swapQueues(); 38 return value; 39 } 40 41 42 public static void main(String[] args) { 43 StackUsingQueue sq = new StackUsingQueue(); 44 45 System.out.println("Pop(): " + sq.pop()); 46 // PrintStack 函数允许我们轻松 47 // 可视化栈的状态 48 StackMethods.printStack(sq); 49 50 sq.push(3); 51 System.out.println("Push(3): "); 52 StackMethods.printStack(sq); 53 54 sq.push(5); 55 System.out.println("Push(5): "); 56 StackMethods.printStack(sq); 57 58 sq.push(9); 59 System.out.println("Push(9): "); 60 StackMethods.printStack(sq); 61 62 System.out.println("Pop(): " + sq.pop()); 63 StackMethods.printStack(sq); 64 65 sq.push(10); 66 System.out.println("Push(10):"); 67 StackMethods.printStack(sq); 68 69 sq.push(16); 70 System.out.println("Push(16):"); 71 StackMethods.printStack(sq); 72 73 System.out.println("Pop(): " + sq.pop()); 74 StackMethods.printStack(sq); 75 } 76}
Python
1from collections import deque 2 3class StackUsingQueue: 4 def __init__(self): 5 self.queue1 = deque() 6 self.queue2 = deque() 7 8 def push(self, data): 9 self.queue1.append(data) 10 11 # 使用队列类的默认 size() 方法 12 # 检查栈是否为空 13 def is_empty(self): 14 return len(self.queue1) + len(self.queue2) == 0 15 16 # 辅助函数，使用临时队列交换我们的队列 17 18 def swap_queues(self): 19 self.queue3 = self.queue1 20 self.queue1 = self.queue2 21 self.queue2 = self.queue3 22 23 def pop(self): 24 if self.is_empty(): 25 return -1 26 27 while len(self.queue1) > 1 : 28 self.queue2.append(self.queue1.popleft()) 29 30 # 当 queue1 中只剩一个元素时，将其出队 31 # 并交换队列 32 value = self.queue1.popleft() 33 self.swap_queues() 34 return value 35 36def main(): 37 sq = StackUsingQueue(); 38 print("Pop(): " + str(sq.pop())) 39 40 # PrintStack 函数允许我们轻松 41 # 可视化栈的状态 42 print_stack(sq) 43 44 sq.push(3) 45 print("\nPush(3): ") 46 print_stack(sq) 47 48 sq.push(5) 49 print("\nPush(5): " ) 50 print_stack(sq) 51 52 sq.push(9) 53 print("\nPush(9): " ) 54 print_stack(sq) 55 56 print("\nPop(): " + str(sq.pop())) 57 print_stack(sq) 58 59 sq.push(10) 60 print("\nPush(10): " ) 61 print_stack(sq) 62 63 sq.push(16) 64 print("\nPush(16): " ) 65 print_stack(sq) 66 67 print("\nPop(): " + str(sq.pop())) 68 print_stack(sq) 69 70if __name__ == '__main__': 71 main()
JS
1class StackUsingQueue { 2 constructor() { 3 this.queue1 = []; 4 this.queue2 = []; 5 } 6 7 // 将数据推入队列 8 push(data) { 9 this.queue1.push(data); 10 } 11 12 // 使用默认的 length 方法检查栈是否为空 13 isEmpty() { 14 return ((this.queue1.length + this.queue2.length) === 0); 15 } 16 17 // 辅助函数，使用临时队列交换我们的队列 18 swap_queues() { 19 let temp = this.queue1; 20 this.queue1 = this.queue2; 21 this.queue2 = temp; 22 } 23 24 pop() { 25 if (this.isEmpty()) { 26 return -1; 27 } 28 29 while (this.queue1.length > 1) { 30 this.queue2.push(this.queue1.shift()); 31 } 32 33 // 当 queue1 中只剩一个元素时，将其出队 34 // 并交换队列 35 let value = this.queue1.shift(); 36 this.swap_queues(); 37 return value; 38 }; 39}; 40 41let sq = new StackUsingQueue(); 42console.log("Pop(): " + sq.pop()); 43 44// PrintStack 函数允许我们轻松 45// 可视化栈的状态 46PrintStack(sq); 47 48sq.push(3); 49console.log("\nPush(3): "); 50PrintStack(sq); 51 52sq.push(5); 53console.log("\nPush(5): " ); 54PrintStack(sq); 55 56sq.push(9); 57console.log("\nPush(9): " ); 58PrintStack(sq); 59 60 61console.log("\nPop(): " + sq.pop()); 62PrintStack(sq); 63 64sq.push(10); 65console.log("\nPush(10): " ); 66PrintStack(sq); 67 68sq.push(16); 69console.log("\nPush(16): " ); 70PrintStack(sq); 71 72console.log("\nPop(): " + sq.pop()); 73PrintStack(sq);
Ruby
1class StackUsingQueue 2 attr_accessor :queue1, :queue2 3 4 # initialize 初始化 queue1 和 queue2 5 def initialize() 6 @queue1 = [] 7 @queue2 = [] 8 end 9 10 # Push 将数据推入栈 11 def push(data) 12 @queue1.push(data) 13 end 14 15 # is_empty 使用 queue1 和 queue2 的默认 length 方法 16 # 检查栈是否为空 17 def is_empty() 18 return @queue1.length + @queue2.length == 0 19 end 20 21 # swap_queues 是一个辅助函数，使用临时队列交换我们的队列 22 def swap_queues() 23 temp = @queue1 24 @queue1 = @queue2 25 @queue2 = temp 26 end 27 28 # Pop 从栈中弹出元素 29 def pop() 30 return -1 if self.is_empty 31 32 @queue2.push(@queue1.shift()) while @queue1.length > 1 33 34 # 当 queue1 中只剩一个元素时，将其出队 35 # 并交换队列 36 # shift() 执行相同操作：移除第一个元素 37 value = @queue1.shift() 38 self.swap_queues 39 return value 40 end 41 42end 43 44sq = StackUsingQueue.new() 45puts "Pop(): " + sq.pop().to_s 46 47# PrintStack 函数允许我们轻松 48# 可视化栈的状态 49print_stack(sq) 50 51sq.push(3) 52puts "\nPush(3): " 53print_stack(sq) 54 55sq.push(5) 56puts "\nPush(5): " 57print_stack(sq) 58 59sq.push(9) 60puts "\nPush(9): " 61print_stack(sq) 62 63puts "\nPop(): " + sq.pop().to_s 64print_stack(sq) 65 66sq.push(10) 67puts "\nPush(10): " 68print_stack(sq) 69 70sq.push(16) 71puts "\nPush(16): " 72print_stack(sq) 73 74puts "\nPop(): " + sq.pop().to_s 75print_stack(sq)
Go
1package main 2 3import ( 4 "fmt" 5 "math" 6 "strings" 7 "errors" 8 "sync" 9) 10 11// StackUsingQueue 类型结构体 12type StackUsingQueue struct { 13 queue1 Queue 14 queue2 Queue 15} 16// InitQueue 初始化 queue1 和 queue2 17func (q *StackUsingQueue) InitQueue() { 18 q.queue1 = Queue{} 19 q.queue2 = Queue{} 20} 21// Push 将数据推入栈 22func (s *StackUsingQueue) Push(data int) { 23 s.queue1.Enqueue(data) 24} 25 26/* IsEmpty 使用队列类的默认 Len() 方法 27 检查栈是否为空 */ 28func (s *StackUsingQueue) IsEmpty() bool { 29 return s.queue1.Size() + s.queue2.Size() == 0 30} 31 32// SwapQueues 是一个辅助函数，使用临时队列交换我们的队列 33func (s *StackUsingQueue) SwapQueues() { 34 temp := s.queue1 35 s.queue1, s.queue2 = s.queue2, temp 36} 37// Pop 从栈中弹出元素 38func (s *StackUsingQueue) Pop() int { 39 if s.IsEmpty() { 40 return -1 41 } 42 for s.queue1.Size() > 1 { 43 value := s.queue1.Dequeue().(int) 44 s.queue2.Enqueue(value) 45 } 46 /* 当 queue1 中只剩一个元素时，将其出队 47 并交换队列 */ 48 value := s.queue1.Dequeue().(int) 49 s.SwapQueues() 50 return value 51} 52 53func main() { 54 sq := new(StackUsingQueue) 55 sq.InitQueue() 56 57 fmt.Println("Pop(): ", sq.Pop()) 58 /* PrintStack 函数允许我们轻松 59 可视化栈的状态 */ 60 PrintStack(sq) 61 62 sq.Push(3) 63 fmt.Print("\nPush(3): ") 64 PrintStack(sq) 65 66 sq.Push(5) 67 fmt.Print("\nPush(5): ") 68 PrintStack(sq) 69 70 sq.Push(9) 71 fmt.Print("\nPush(9): ") 72 PrintStack(sq) 73 74 fmt.Print("\nPop(): ", sq.Pop()) 75 PrintStack(sq) 76 77 sq.Push(10) 78 fmt.Print("\nPush(10): ") 79 PrintStack(sq) 80 81 sq.Push(16) 82 fmt.Print("\nPush(16): ") 83 PrintStack(sq) 84 85 fmt.Print("\nPop(): ", sq.Pop()) 86 PrintStack(sq) 87}
时间复杂度
- 此解法的
push()运行时间复杂度为常数，。 - 此解法的
pop()运行时间复杂度为线性，。
空间复杂度
此解法的空间复杂度为线性，。
解法 2
第二个解法会使 pop() 操作更快。与第一个解法类似，我们维护两个队列。让我们看看 push 和 pop 操作的样子：
1push(): 2 如果 queue1 为空， 3 则在 queue1 中入队。 4 5 否则， 6 在 queue2 中入队，并将 queue1 中的所有元素出队并推入 queue2。 7 然后交换队列引用。 8 9pop(): 10 如果栈大小为 0， 11 返回 -1。 12 否则， 13 从 queue1 中出队并返回。
让我们通过一个例子来理解这个算法。我们对栈执行以下 push() 和 pop() 操作，并观察在 queue1 和 queue2 上执行的相应 enqueue() 和 dequeue() 操作。
多标签代码
C++
1#include <iostream> 2#include <queue> 3#include <cmath> 4using namespace std; 5 6class StackUsingQueue { 7 public: 8 queue <int> queue1; 9 queue <int> queue2; 10 11 void Push(int data) { 12 if (queue1.empty()) { 13 queue1.push(data); 14 } else { 15 queue2.push(data); 16 while (!queue1.empty()) { 17 // 从 queue1 中出队值并入队到 queue2 18 int value = queue1.front(); 19 queue2.push(value); 20 queue1.pop(); 21 } 22 // queue2 现在包含所有元素且顺序正确 23 SwapQueues(); 24 } 25 } 26 27 // 使用队列类的默认 size() 方法 28 // 检查栈是否为空 29 bool IsEmpty() { 30 return queue1.size() + queue2.size() == 0; 31 } 32 33 // 辅助函数，使用临时队列指针交换我们的队列 34 void SwapQueues() { 35 queue <int> temp = queue1; 36 queue1 = queue2; 37 queue2 = temp; 38 } 39 40 int Pop() { 41 if (IsEmpty()) { 42 return -1; 43 } 44 45 int value = queue1.front(); 46 queue1.pop(); 47 return value; 48 } 49}; 50 51int main() { 52 StackUsingQueue sq; 53 54 cout << "Pop(): " << sq.Pop() << endl; 55 // PrintStack 函数允许我们轻松 56 // 可视化栈的状态 57 PrintStack(sq); 58 59 sq.Push(3); 60 cout << "\nPush(3): " << endl; 61 PrintStack(sq); 62 63 sq.Push(5); 64 cout << "\nPush(5): " << endl; 65 PrintStack(sq); 66 67 sq.Push(9); 68 cout << "\nPush(9): " << endl; 69 PrintStack(sq); 70 71 cout << "\nPop(): " << sq.Pop() << endl; 72 PrintStack(sq); 73 74 sq.Push(10); 75 cout << "\nPush(10):" << endl; 76 PrintStack(sq); 77 78 sq.Push(16); 79 cout << "\nPush(16):" << endl; 80 PrintStack(sq); 81 82 cout << "\nPop(): " << sq.Pop() << endl; 83 PrintStack(sq); 84}
Java
1// 导入所需函数 2import java.util.*; 3 4class StackUsingQueue { 5 Queue<Integer> queue1 = new ArrayDeque<Integer>(); 6 Queue<Integer> queue2 = new ArrayDeque<Integer>(); 7 8 void push(int data) { 9 if (queue1.isEmpty()) { 10 queue1.add(data); 11 } else { 12 queue2.add(data); 13 while (!queue1.isEmpty()) { 14 // 从 queue1 中出队值并入队到 queue2 15 queue2.add(queue1.remove()); 16 } 17 // queue2 现在包含所有元素且顺序正确 18 swapQueues(); 19 } 20 } 21 22 // 使用队列类的默认 size() 方法 23 // 检查栈是否为空 24 boolean isEmpty() { 25 return queue1.size() + queue2.size() == 0; 26 } 27 28 // 辅助函数，使用临时队列指针交换我们的队列 29 void swapQueues() { 30 Queue<Integer> queue3 = queue1; 31 queue1 = queue2; 32 queue2 = queue3; 33 } 34 35 int pop() { 36 if (isEmpty()) { 37 return -1; 38 } 39 return queue1.remove(); 40 } 41 42 public static void main(String[] args) { 43 StackUsingQueue sq = new StackUsingQueue(); 44 45 System.out.println("Pop(): " + sq.pop()); 46 // PrintStack 函数允许我们轻松 47 // 可视化栈的状态 48 StackMethods.printStack(sq); 49 50 sq.push(3); 51 System.out.println("Push(3): "); 52 StackMethods.printStack(sq); 53 54 sq.push(5); 55 System.out.println("Push(5): "); 56 StackMethods.printStack(sq); 57 58 sq.push(9); 59 System.out.println("Push(9): "); 60 StackMethods.printStack(sq); 61 62 System.out.println("Pop(): " + sq.pop()); 63 StackMethods.printStack(sq); 64 65 sq.push(10); 66 System.out.println("Push(10):"); 67 StackMethods.printStack(sq); 68 69 sq.push(16); 70 System.out.println("Push(16):"); 71 StackMethods.printStack(sq); 72 73 System.out.println("\nPop(): " + sq.pop()); 74 StackMethods.printStack(sq); 75 } 76}
Python
1from collections import deque 2 3class StackUsingQueue: 4 def __init__(self): 5 self.queue1 = deque() 6 self.queue2 = deque() 7 8 def push(self, data): 9 if not self.queue1: 10 self.queue1.append(data) 11 else: 12 self.queue2.append(data) 13 while self.queue1: 14 self.queue2.append(self.queue1.popleft()) 15 self.swap_queues() 16 17 def is_empty(self): 18 return len(self.queue1) + len(self.queue2) == 0; 19 20 def pop(self): 21 if self.is_empty(): 22 return -1; 23 return self.queue1.popleft(); 24 25 def swap_queues(self): 26 self.queue3 = self.queue1 27 self.queue1 = self.queue2 28 self.queue2 = self.queue3 29 30def main(): 31 sq = StackUsingQueue(); 32 print("Pop(): " + str(sq.pop())) 33 34 # PrintStack 函数允许我们轻松 35 # 可视化栈的状态 36 print_stack(sq) 37 38 sq.push(3) 39 print("\nPush(3): ") 40 print_stack(sq) 41 42 sq.push(5) 43 print("\nPush(5): " ) 44 print_stack(sq) 45 46 sq.push(9) 47 print("\nPush(9): " ) 48 print_stack(sq) 49 50 print("\nPop(): " + str(sq.pop())) 51 print_stack(sq) 52 53 sq.push(10) 54 print("\nPush(10): " ) 55 print_stack(sq) 56 57 sq.push(16) 58 print("\nPush(16): " ) 59 print_stack(sq) 60 61 print("\nPop(): " + str(sq.pop())) 62 print_stack(sq) 63 64if __name__ == '__main__': 65 main()
JS
1class StackUsingQueue { 2 constructor() { 3 this.queue1 = []; 4 this.queue2 = []; 5 } 6 7 push(data) { 8 if (this.queue1.length === 0) { 9 this.queue1.push(data); 10 } else { 11 this.queue2.push(data); 12 while (this.queue1.length !== 0) { 13 // 从 queue1 中出队值并入队到 queue2 14 this.queue2.push(this.queue1.shift()); 15 } 16 // queue2 现在包含所有元素且顺序正确 17 this.swap_queues(); 18 } 19 } 20 21 // 使用默认的 length 方法检查栈是否为空 22 isEmpty() { 23 return this.queue1.length + this.queue2.length === 0; 24 } 25 26 // 辅助函数，使用临时队列指针交换我们的队列 27 swap_queues() { 28 let temp = this.queue1; 29 this.queue1 = this.queue2; 30 this.queue2 = temp; 31 } 32 33 pop() { 34 if (this.isEmpty()) { 35 return -1; 36 } 37 return this.queue1.shift(); 38 } 39 40}; 41 42let sq = new StackUsingQueue(); 43console.log("Pop(): " + sq.pop()); 44 45// PrintStack 函数允许我们轻松 46// 可视化栈的状态 47PrintStack(sq); 48 49sq.push(3); 50console.log("\nPush(3): "); 51PrintStack(sq); 52 53sq.push(5); 54console.log("\nPush(5): " ); 55PrintStack(sq); 56 57sq.push(9); 58console.log("\nPush(9): " ); 59PrintStack(sq); 60 61 62console.log("\nPop(): " + sq.pop()); 63PrintStack(sq); 64 65sq.push(10); 66console.log("\nPush(10): " ); 67PrintStack(sq); 68 69sq.push(16); 70console.log("\nPush(16): " ); 71PrintStack(sq); 72 73console.log("\nPop(): " + sq.pop()); 74PrintStack(sq);
Ruby
1class StackUsingQueue 2 attr_accessor :queue1, :queue2 3 4 # initialize 初始化 queue1 和 queue2 5 def initialize() 6 @queue1 = [] 7 @queue2 = [] 8 end 9 10 # Push 将数据推入栈 11 def push(data) 12 if @queue1.length == 0 13 @queue1.push(data) 14 else 15 @queue2.push(data) 16 # 从 queue1 中出队值并入队到 queue2 17 @queue2.push(@queue1.shift()) while @queue1.length != 0 18 # queue2 现在包含所有元素且顺序正确 19 self.swap_queues 20 end 21 end 22 23 # 使用 queue1 和 queue2 的默认 length 方法 24 # 检查栈是否为空 25 def is_empty() 26 return @queue1.length + @queue2.length == 0 27 end 28 29 # 辅助函数，使用临时队列指针交换我们的队列 30 def swap_queues() 31 temp = @queue1 32 @queue1 = @queue2 33 @queue2 = temp 34 end 35 36 # Pop 从栈中弹出元素 37 def pop() 38 return -1 if self.is_empty 39 return @queue1.shift() 40 end 41end 42 43# 驱动代码 44sq = StackUsingQueue.new() 45puts "Pop(): " + sq.pop().to_s 46 47# PrintStack 函数允许我们轻松 48# 可视化栈的状态 49print_stack(sq) 50 51sq.push(3) 52puts "\nPush(3): " 53print_stack(sq) 54 55 56sq.push(5) 57puts "\nPush(5): " 58print_stack(sq) 59 60sq.push(9) 61puts "\nPush(9): " 62print_stack(sq) 63 64puts "\nPop(): " + sq.pop().to_s 65print_stack(sq) 66 67sq.push(10) 68puts "\nPush(10): " 69print_stack(sq) 70 71sq.push(16) 72puts "\nPush(16): " 73print_stack(sq) 74 75puts "\nPop(): " + sq.pop().to_s 76print_stack(sq)
Go
1package main 2 3import ( 4 "fmt" 5 "math" 6 "strings" 7 "errors" 8 "sync" 9) 10 11// StackUsingQueue 类型结构体 12type StackUsingQueue struct { 13 queue1 Queue 14 queue2 Queue 15} 16 17// InitQueue 初始化 queue1 和 queue2 18func (q *StackUsingQueue) InitQueue() { 19 q.queue1 = Queue{} 20 q.queue2 = Queue{} 21} 22 23// Push 将数据推入栈 24func (s *StackUsingQueue) Push(data int) { 25 if s.queue1.Size() == 0 { 26 s.queue1.Enqueue(data) 27 } else { 28 s.queue2.Enqueue(data) 29 for s.queue1.Size() > 0 { 30 /* 从 queue1 中出队值并入队到 queue2 */ 31 value := s.queue1.Dequeue().(int) 32 s.queue2.Enqueue(value) 33 } 34 // queue2 现在包含所有元素且顺序正确 35 s.SwapQueues() 36 } 37} 38 39/* IsEmpty 使用队列类的默认 Len() 方法 40 检查栈是否为空 */ 41func (s *StackUsingQueue) IsEmpty() bool { 42 return s.queue1.Size() + s.queue2.Size() == 0 43} 44 45// SwapQueues 是一个辅助函数，使用临时队列交换我们的队列 46func (s *StackUsingQueue) SwapQueues() { 47 temp := s.queue1 48 s.queue1 = s.queue2 49 s.queue2 = temp 50} 51 52// Pop 从栈中弹出元素 53func (s *StackUsingQueue) Pop() int { 54 if s.IsEmpty() { 55 return -1 56 } 57 value := s.queue1.Dequeue().(int) 58 return value 59} 60 61func main() { 62 63 sq := new(StackUsingQueue) 64 sq.InitQueue() 65 66 fmt.Println("Pop(): ", sq.Pop()) 67 /* PrintStack 函数允许我们轻松 68 可视化栈的状态 */ 69 PrintStack(sq) 70 71 sq.Push(3) 72 fmt.Print("\nPush(3): ") 73 PrintStack(sq) 74 75 sq.Push(5) 76 fmt.Print("\nPush(5): ") 77 PrintStack(sq) 78 79 sq.Push(9) 80 fmt.Print("\nPush(9): ") 81 PrintStack(sq) 82 83 fmt.Print("\nPop(): ", sq.Pop()) 84 PrintStack(sq) 85 86 sq.Push(10) 87 fmt.Print("\nPush(10): ") 88 PrintStack(sq) 89 90 sq.Push(16) 91 fmt.Print("\nPush(16): ") 92 PrintStack(sq) 93 94 fmt.Print("\nPop(): ", sq.Pop()) 95 PrintStack(sq) 96}
时间复杂度
- 此解法的
push()时间复杂度为线性，。 - 此解法的
pop()时间复杂度为常数，。
空间复杂度
此解法的空间复杂度为线性，。