135-1821-9792

浅析数据结构栈和队列的相互实现

" 编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。"

算法，一门既不容易入门，也不容易精通的学问。

栈和队列都是用来保存数据的，无论底层是使用数组还是链表来实现，其基本原理是不变的，那就是栈的特点的先进后出，队列的特点是先进先出。

栈

栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构。线性表是用数组来实现的，对于栈这种只能一头插入删除的线性表来说，用数组下标为0(栈底不变，只需要跟踪栈顶的变化即可)的一端作为栈底比较合适。

列表封装的这些方法，实现栈这个常用的数据结构比较容易。栈是一种只能在列表一端进出的特殊列表，pop方法正好完美实现：

 
 
 
 
    
  
  
  
  
  1. In [1]: stack=[1,3,5] 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. In [2]: stack.append(0) # push元素0到尾端，不需要指定索引 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. In [3]: stack 
    6. 
  
  
  
  
  6. Out[3]: [1, 3, 5, 0] 
    7. 
  
  
  
  
  7.  
    8. 
  
  
  
  
  8. In [4]: stack.pop() # pop元素，不需指定索引，此时移出尾端元素 
    9. 
  
  
  
  
  9. Out[4]: 0 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11. In [5]: stack 
    12. 
  
  
  
  
  12. Out[5]: [1, 3, 5] 
    13.

由此可见Python的列表当做栈用，完全没有问题，push 和 pop 操作的时间复杂度都为 O(1)

队列

队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构.。使用顺序表存储队列时，队列元素的出队是在队头，即下标为0的地方，当有元素出队时，出队元素后面的所有元素都需要向前移动，保证队列的队头始终处在下标为0的位置，此时会大大增加时间复杂度。

使用列表模拟队列，需要借助Python的collections模块中的双端队列deque实现。如下模拟队列的先进先出，后进后出：

 
 
 
 
    
  
  
  
  
  1. In [1]: from collections import deque 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. In [2]: queue = [1,3,5] 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. In [3]: deq = deque(queue) 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. In [4]: deq.append(0)  
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. In [5]: deq 
    10. 
  
  
  
  
  10. Out[5]: deque([1, 3, 5, 0]) # 后进插入到队列尾部 
    11. 
  
  
  
  
  11.  
    12. 
  
  
  
  
  12. In [6]: deq.popleft()   
    13. 
  
  
  
  
  13. Out[6]: 1 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. In [7]: deq 
    16. 
  
  
  
  
  16. Out[7]: deque([3, 5, 0])# 先进的先出 
    17.

LeetCode 第 225题：用队列实现栈#使用队列实现栈

 
 
 
 
    
  
  
  
  
  1. #使用队列实现栈的下列操作：  
    2. 
  
  
  
  
  2. # push(x) -- 元素 x 入栈  
    3. 
  
  
  
  
  3. # pop() -- 移除栈顶元素  
    4. 
  
  
  
  
  4. # top() -- 获取栈顶元素  
    5. 
  
  
  
  
  5. # empty() -- 返回栈是否为空  
    6. 
  
  
  
  
  6. # 注意:  
    7. 
  
  
  
  
  7. # 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。  
    8. 
  
  
  
  
  8. # 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。  
    9. 
  
  
  
  
  9. # 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。  
    10. 
  
  
  
  
  10. # Related Topics 栈 设计 
    11.

根据题意，我们只能使用队列的基本操作，队列因为是先进先出，要实现先进后出的栈。

无论是用队列实现栈，还是用栈实现队列。常见的解法方法是使用两个队列或者两个栈。

假设有q1，q2两个队列，我们先初始化队列。

 
 
 
 
    
  
  
  
  
  1. from collections import deque 
    2. 
  
  
  
  
  2. class MyStack: 
    3. 
  
  
  
  
  3.     def __init__(self): 
    4. 
  
  
  
  
  4.         """ 
    5. 
  
  
  
  
  5.         Initialize your data structure here. 
    6. 
  
  
  
  
  6.         """ 
    7. 
  
  
  
  
  7.         self.q1 = deque() 
    8. 
  
  
  
  
  8.         self.q2 = deque() 
    9.

push(x) ：元素 x 入栈 时和队列添加元素的方法一样。

压入栈时，加入到q1的末尾，那么q1末尾的元素就是栈顶元素。因此只需要append(x)即可。

 
 
 
 
    
  
  
  
  
  1. def push(self, x: int) -> None: 
    2. 
  
  
  
  
  2.     """ 
    3. 
  
  
  
  
  3.     Push element x onto stack. 
    4. 
  
  
  
  
  4.     """ 
    5. 
  
  
  
  
  5.     self.q1.append(x) 
    6.

对于pop删除元素，我们可以使用q2保存q1的最后的元素之前的元素，然后将q1的元素进行删除，最后将两个队列进行互换。

我们需要弹出栈顶元素，也就是q1最后的元素，队列只能是先进先出，我们得用q2把q1出队的元素装着，最后一个出队元素就是栈顶元素。

因此，代码需要对q1的长度进行判断，如果q1的长度大于1，那么将q1的头部元素添加到q2，直到q1只有最后一个元素。

 
 
 
 
    
  
  
  
  
  1. def pop(self) -> int: 
    2. 
  
  
  
  
  2.     """ 
    3. 
  
  
  
  
  3.     Removes the element on top of the stack and returns that element. 
    4. 
  
  
  
  
  4.     """ 
    5. 
  
  
  
  
  5.     while len(self.q1) > 1: 
    6. 
  
  
  
  
  6.         self.q2.append(self.q1.popleft()) 
    7. 
  
  
  
  
  7.     tmp = self.q1.popleft() 
    8. 
  
  
  
  
  8.     self.q2, self.q1 = self.q1, self.q2 
    9. 
  
  
  
  
  9.     return tmp 
    10.

判断是否为空，只需要判断q1的队列是否为空。

 
 
 
 
    
  
  
  
  
  1. def empty(self) -> bool: 
    2. 
  
  
  
  
  2.     """ 
    3. 
  
  
  
  
  3.     Returns whether the stack is empty. 
    4. 
  
  
  
  
  4.     """ 
    5. 
  
  
  
  
  5.     return not bool(self.q1) 
    6.

取栈顶元素。这里其实可以巧妙地解决，我们直接调用pop方法进行删除，在pop进行删除时用一个变量进行保存，还需要对该元素重新进行插入操作。

 
 
 
 
    
  
  
  
  
  1. def top(self) -> int: 
    2. 
  
  
  
  
  2.     ans = self.pop() 
    3. 
  
  
  
  
  3.     self.q1.append(ans) 
    4. 
  
  
  
  
  4.     return ans 
    5.

下面就是用队列实现栈完整代码

 
 
 
 
    
  
  
  
  
  1. from collections import deque 
    2. 
  
  
  
  
  2. class MyStack: 
    3. 
  
  
  
  
  3.     def __init__(self): 
    4. 
  
  
  
  
  4.         """ 
    5. 
  
  
  
  
  5.         Initialize your data structure here. 
    6. 
  
  
  
  
  6.         """ 
    7. 
  
  
  
  
  7.         self.q1 = deque() 
    8. 
  
  
  
  
  8.         self.q2 = deque() 
    9. 
  
  
  
  
  9.  
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.     def push(self, x: int) -> None: 
    12. 
  
  
  
  
  12.         """ 
    13. 
  
  
  
  
  13.         Push element x onto stack. 
    14. 
  
  
  
  
  14.         """ 
    15. 
  
  
  
  
  15.         self.q1.append(x) 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17.  
    18. 
  
  
  
  
  18.     def pop(self) -> int: 
    19. 
  
  
  
  
  19.         """ 
    20. 
  
  
  
  
  20.         Removes the element on top of the stack and returns that element. 
    21. 
  
  
  
  
  21.         """ 
    22. 
  
  
  
  
  22.         while len(self.q1) > 1: 
    23. 
  
  
  
  
  23.             self.q2.append(self.q1.popleft()) 
    24. 
  
  
  
  
  24.         tmp = self.q1.popleft() 
    25. 
  
  
  
  
  25.         self.q2,self.q1 = self.q1, self.q2 
    26. 
  
  
  
  
  26.         return tmp 
    27. 
  
  
  
  
  27.  
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29.     def top(self) -> int: 
    30. 
  
  
  
  
  30.         """ 
    31. 
  
  
  
  
  31.         Get the top element. 
    32. 
  
  
  
  
  32.         """ 
    33. 
  
  
  
  
  33.         ans = self.pop() 
    34. 
  
  
  
  
  34.         self.q1.append(ans) 
    35. 
  
  
  
  
  35.         return ans 
    36. 
  
  
  
  
  36.  
    37. 
  
  
  
  
  37.  
    38. 
  
  
  
  
  38.     def empty(self) -> bool: 
    39. 
  
  
  
  
  39.         """ 
    40. 
  
  
  
  
  40.         Returns whether the stack is empty. 
    41. 
  
  
  
  
  41.         """ 
    42. 
  
  
  
  
  42.         return not bool(self.q1) 
    43.

LeetCode 第232题：用栈实现队列

 
 
 
 
    
  
  
  
  
  1. #使用栈实现队列的下列操作： 
    2. 
  
  
  
  
  2. # push(x) -- 将一个元素放入队列的尾部。  
    3. 
  
  
  
  
  3. # pop() -- 从队列首部移除元素。  
    4. 
  
  
  
  
  4. # peek() -- 返回队列首部的元素。  
    5. 
  
  
  
  
  5. # empty() -- 返回队列是否为空。 
    6. 
  
  
  
  
  6. # 示例: 
    7. 
  
  
  
  
  7. # MyQueue queue = new MyQueue(); 
    8. 
  
  
  
  
  8. #queue.push(1); 
    9. 
  
  
  
  
  9. #queue.push(2);   
    10. 
  
  
  
  
  10. #queue.peek();  // 返回 1 
    11. 
  
  
  
  
  11. #queue.pop();   // 返回 1 
    12. 
  
  
  
  
  12. #queue.empty(); // 返回 false 
    13. 
  
  
  
  
  13. # 说明: 
    14. 
  
  
  
  
  14. # 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。  
    15. 
  
  
  
  
  15. # 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。  
    16. 
  
  
  
  
  16. # 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。 
    17. 
  
  
  
  
  17. # Related Topics 栈 设计 
    18.

最简单的方法使用list表示一个栈，只能使用栈的相关方法，如append()，pop()，s[-1]，分别是栈顶追加元素,删除栈顶元素,取出栈顶元素.。

 
 
 
 
    
  
  
  
  
  1. class MyQueue: 
    2. 
  
  
  
  
  2.     def __init__(self): 
    3. 
  
  
  
  
  3.         self.s = [] 
    4. 
  
  
  
  
  4.     def push(self, x: int) -> None: 
    5. 
  
  
  
  
  5.         self.s.append(x) 
    6. 
  
  
  
  
  6.     def pop(self) -> int:     
    7. 
  
  
  
  
  7.         return self.s.pop(0) 
    8. 
  
  
  
  
  8.     def peek(self) -> int: 
    9. 
  
  
  
  
  9.         return self.s[0] 
    10. 
  
  
  
  
  10.     def empty(self) -> bool: 
    11. 
  
  
  
  
  11.         return not bool(self.s) 
    12.

当然也可以使用两个栈，这个是比较复杂的操作，「但也是比较常见的算法考点。」

(1)初始化两个栈结构，s1为主栈，s2为辅助栈。

(2)push往s1末尾添加元素，利用append即可实现。

(3)pop时候，先将s1元素向s2转移，知道s1只剩下一个元素时候(这就是我们要返回的队列首部元素)，然后我们再把2中的元素转移回s1中即可。

(4)返回队列首部的元素，类似于步骤(3)的操作，唯一不同是这里我们需要将elenment先添加回stack2，然后再将stack2的元素转移回stack1中，因为peek操作不需要删除队列首部元素

(5)empty判断stack1尺寸即可。

出队操作首先判断缓存栈s2是否有元素，有的话直接取出s2栈顶元素;若s2为空并且s1中有元素，将s1中元素全部转移到s2中，再取出s2栈顶元素，即可模拟队列出队操作;本例中没有出现s2和s1都为空的情况。

 
 
 
 
    
  
  
  
  
  1. class MyQueue: 
    2. 
  
  
  
  
  2.     def __init__(self): 
    3. 
  
  
  
  
  3.         """ 
    4. 
  
  
  
  
  4.         Initialize your data structure here. 
    5. 
  
  
  
  
  5.         """ 
    6. 
  
  
  
  
  6.         self.s1 = [] 
    7. 
  
  
  
  
  7.         self.s2 = [] 
    8. 
  
  
  
  
  8.          
    9. 
  
  
  
  
  9.     def push(self, x: int) -> None: 
    10. 
  
  
  
  
  10.         """ 
    11. 
  
  
  
  
  11.         Push element x to the back of queue. 
    12. 
  
  
  
  
  12.         """ 
    13. 
  
  
  
  
  13.         self.s1.append(x) 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15.     def pop(self) -> int: 
    16. 
  
  
  
  
  16.         """ 
    17. 
  
  
  
  
  17.         Removes the element from in front of queue and returns that element. 
    18. 
  
  
  
  
  18.         """ 
    19. 
  
  
  
  
  19.         if self.s2: 
    20. 
  
  
  
  
  20.             return self.s2.pop() 
    21. 
  
  
  
  
  21.         else: 
    22. 
  
  
  
  
  22.             if  self.s1 : 
    23. 
  
  
  
  
  23.                 while self.s1: 
    24. 
  
  
  
  
  24.                     self.s2.append(self.s1.pop()) 
    25. 
  
  
  
  
  25.                 return self.s2.pop() 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27.     def peek(self) -> int: 
    28. 
  
  
  
  
  28.         """ 
    29. 
  
  
  
  
  29.         Get the front element. 
    30. 
  
  
  
  
  30.         """ 
    31. 
  
  
  
  
  31.         if self.s2: 
    32. 
  
  
  
  
  32.             return self.s2[-1] 
    33. 
  
  
  
  
  33.         else: 
    34. 
  
  
  
  
  34.             if  self.s1 : 
    35. 
  
  
  
  
  35.                 while self.s1: 
    36. 
  
  
  
  
  36.                     self.s2.append(self.s1.pop()) 
    37. 
  
  
  
  
  37.                 return self.s2[-1] 
    38. 
  
  
  
  
  38.  
    39. 
  
  
  
  
  39.     def empty(self) -> bool: 
    40. 
  
  
  
  
  40.         """ 
    41. 
  
  
  
  
  41.         Returns whether the queue is empty. 
    42. 
  
  
  
  
  42.         """ 
    43. 
  
  
  
  
  43.         if self.s1 or self.s2: 
    44. 
  
  
  
  
  44.             return False 
    45. 
  
  
  
  
  45.         else: 
    46. 
  
  
  
  
  46.             return True 
    47. 
  
  
  
  
  47.  
    48. 
  
  
  
  
  48. # Your MyQueue object will be instantiated and called as such: 
    49. 
  
  
  
  
  49. # obj = MyQueue() 
    50. 
  
  
  
  
  50. # obj.push(x) 
    51. 
  
  
  
  
  51. # param_2 = obj.pop() 
    52. 
  
  
  
  
  52. # param_3 = obj.peek() 
    53. 
  
  
  
  
  53. # param_4 = obj.empty() 
    54.

本文已收录 GitHub:

https://github.com/MaoliRUNsen/runsenlearnpy100


当前名称：浅析数据结构栈和队列的相互实现
文章地址：http://www.wtcwzsj.com/article/djogoeh.html

其他资讯


关于我们
我们的服务
网站建设案例
新闻动态
联系我们

135-1821-9792

公司服务热线
友情链接： 创新互联   绵阳服务器托管   网站建设方案   南充发电机组维修   成都柴油发电机回收   德阳服务器托管   彭州网站建设   成都网络营销   彭州沃尔沃发电机   内江网站建设   

Copyright © 2009-2022 www.wtcwzsj.com 青羊区广皓图文设计工作室（个体工商户） 版权所有　蜀ICP备19037934号