FilesExpand file tree

 master

/

implement-queue-using-stacks.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

45 lines (40 loc) · 1.31 KB

 master

/

implement-queue-using-stacks.py

Copy path

Top

File metadata and controls

• Code
• Blame

45 lines (40 loc) · 1.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

# Time: O(1), amortized

# Space: O(n)

#

# Implement the following operations of a queue using stacks.

#

# push(x) -- Push element x to the back of queue.

# pop() -- Removes the element from in front of queue.

# peek() -- Get the front element.

# empty() -- Return whether the queue is empty.

#

# Notes:

# You must use only standard operations of a stack

# -- which means only push to top, peek/pop from top, size, and is empty operations are valid.

# Depending on your language, stack may not be supported natively.

# You may simulate a stack by using a list or deque (double-ended queue),

# as long as you use only standard operations of a stack.

# You may assume that all operations are valid

# (for example, no pop or peek operations will be called on an empty queue).

#

class Queue:

# initialize your data structure here.

def __init__(self):

self.A, self.B = [], []

# @param x, an integer

# @return nothing

def push(self, x):

self.A.append(x)

# @return nothing

def pop(self):

self.peek()

self.B.pop()

# @return an integer

def peek(self):

if not self.B:

while self.A:

self.B.append(self.A.pop())

return self.B[-1]

# @return an boolean

def empty(self):

return not self.A and not self.B