fork download 
  1. # Max Stack
  2.  
  3. class MaxStack:
  4. 	def __init__(self):
  5. 		self._sorted_pos = []
  6. 		self._v = []
  7.  
  8. 	@property
  9. 	def max(self):
  10. 		toret = None
  11.  
  12. 		if len(self._v) > 0:
  13. 			toret = self._v[self._sorted_pos[0]]
  14.  
  15. 		return toret
  16.  
  17. 	def push(self, x):
  18. 		self._v.append(x)
  19.  
  20. 		if len(self._v) == 1:
  21. 			self._sorted_pos = [0]
  22. 		elif x > self.max:
  23. 			self._sorted_pos.insert(0, len(self._v) - 1)
  24.  
  25. 	def pop(self):
  26. 		toret = self._v.pop()
  27.  
  28. 		if len(self._v) > 0:
  29. 			while self._sorted_pos[0] >= len(self._v):
  30. 				del self._sorted_pos[0]
  31.  
  32. 		return toret
  33.  
  34. 	def __len__(self):
  35. 		return len(self._v)	
  36.  
  37. 	def __str__(self):
  38. 		return "[" + ", ".join([str(x) for x in self._v]) + "]"
  39.  
  40.  
  41. if __name__ == "__main__":
  42. 	ms = MaxStack()
  43. 	ms.push(1)
  44. 	ms.push(2)
  45. 	ms.push(5)
  46. 	ms.push(3)
  47. 	ms.push(4)
  48. 	ms.push(6)
  49.  
  50. 	print("Stack (#", len(ms), "):", str(ms))
  51.  
  52. 	print("Stack max:", ms.max)
  53.  
  54. 	while len(ms) > 0:
  55. 		print("Popping:", ms.pop())
  56. 		print("Stack max:", ms.max)
  57.  
  58. 	print("\nNow (#", len(ms), "):", str(ms))
  59. 	print("Stack max:", ms.max)
  60.  
Success #stdin #stdout 0.02s 27712KB
comments (?)
stdin 
Standard input is empty
stdout 
Stack (# 6 ): [1, 2, 5, 3, 4, 6]
Stack max: 6
Popping: 6
Stack max: 5
Popping: 4
Stack max: 5
Popping: 3
Stack max: 5
Popping: 5
Stack max: 2
Popping: 2
Stack max: 1
Popping: 1
Stack max: None

Now (# 0 ): []
Stack max: None
https://ideone.com/9ofjIS
Python stack storing the max.
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!