Stack
image.png
由于堆棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作噩斟。實(shí)現(xiàn)方式主要有順序棧和鏈棧
基本操作:
init: -> Stack
push: N x Stack -> Stack
top: Stack -> (N U ERROR)
pop: Stack -> Stack
isempty: Stack -> Boolean
一、先看LeetCode 155. Min Stack
- 順序棧孤个， 使用python的list實(shí)現(xiàn)
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.data = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.data.append(x)
def pop(self):
"""
:rtype: void
"""
if self.data:
self.data.pop(-1)
def top(self):
"""
:rtype: int
"""
if self.data:
return self.data[-1]
def getMin(self):
"""
:rtype: int
"""
if self.data:
return min(self.data)
- 鏈棧剃允，由于棧操作只在一斷操作，可以用單鏈表采用頭插法實(shí)現(xiàn)
class Node(object):
def __init__(self, x):
self.val = x
self.next = None
self.pre = None
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.head = Node(None)
def push(self, x):
"""
:type x: int
:rtype: void
"""
node = Node(x)
if self.head.next:
node.next = self.head.next
self.head.next = node
else:
self.head.next = node
def pop(self):
"""
:rtype: void
"""
if self.head.next:
self.head.next = self.head.next.next
def top(self):
"""
:rtype: int
"""
if self.head.next:
return self.head.next.val
def getMin(self):
"""
:rtype: int
"""
p = self.head.next
min = float('inf')
while p:
if min > p.val:
min = p.val
p = p.next
return min
可以看到getMin函數(shù)需要的時(shí)間復(fù)雜度是O(n)齐鲤，如果要降低getMin的時(shí)間復(fù)雜度斥废，可以每個(gè)數(shù)據(jù)元存儲(chǔ)當(dāng)前值加當(dāng)前最小值，需要空間復(fù)雜度O(n)
Queue
image.png
是先進(jìn)先出（FIFO, First-In-First-Out）的線性表给郊。在具體應(yīng)用中通常用鏈表或者數(shù)組來(lái)實(shí)現(xiàn)牡肉。隊(duì)列只允許在后端（稱為rear）進(jìn)行插入操作，在前端（稱為front）進(jìn)行刪除操作丑罪。
那么如何用鏈表實(shí)現(xiàn)一個(gè)隊(duì)列呢荚板，首先隊(duì)列是雙端操作凤壁，涉及到出隊(duì)的時(shí)候需要?jiǎng)h除尾節(jié)點(diǎn)吩屹，如果用單鏈表的話每次刪除都是O(n)的操作跪另，所以用雙向鏈表實(shí)現(xiàn)煤搜，可以控制刪除操作為O(1)
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
self.pre = None
class Queue(object):
def __init__(self):
self.tail = ListNode(None)
self.head = ListNode(None)
self.tail.next = self.head
self.head.next = self.tail
def enqueue(self, item):
cur_node = ListNode(item)
if self.head.next == self.tail:
self.head.next = cur_node
self.tail.next = cur_node
cur_node.pre = self.head
cur_node.next = self.tail
else:
pre_node = self.head.next
self.head.next = cur_node
pre_node.pre = cur_node
cur_node.pre = self.head
def dequeue(self):
cur_node = self.tail.next
pre_node = cur_node.pre
if cur_node == self.head:
return
self.tail.next = pre_node
pre_node.next = self.tail
return cur_node.val
def empty(self):
return self.head.next == self.tail
二免绿、LeetCode 225. Implement Stack using Queues
用隊(duì)列實(shí)現(xiàn)棧，這里先用list實(shí)現(xiàn)一個(gè)隊(duì)列FIFO嘲驾，根據(jù)棧的特性FILO,
所以用兩個(gè)隊(duì)列，入棧的操作直接壓入有數(shù)據(jù)的隊(duì)列辽故，當(dāng)出棧是直接把有數(shù)據(jù)的隊(duì)列依次pop到另一個(gè)空隊(duì)列症见，當(dāng)剩下最后一個(gè)數(shù)據(jù)即棧頂元素
class Queue(object):
def __init__(self):
self.data = []
def pop(self):
if self.data:
return self.data.pop(0)
def push(self, x):
self.data.append(x)
def tail(self):
if self.data:
return self.data[-1]
def empty(self):
if self.data:
return False
return True
class MyStack(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue_a = Queue()
self.queue_b = Queue()
def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
q = self.queue_b if self.queue_a.empty() else q = self.queue_a
q.push(x)
def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
if not self.queue_a.empty():
sour_q = self.queue_a
dest_q = self.queue_b
else:
dest_q = self.queue_a
sour_q = self.queue_b
while not sour_q.empty():
data = sour_q.pop()
if sour_q.empty():
return data
dest_q.push(data)
def top(self):
"""
Get the top element.
:rtype: int
"""
q = self.queue_b if self.queue_a.empty() else q = self.queue_a
return q.tail()
def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return self.queue_a.empty() and self.queue_b.empty()
三、LeetCode 232. Implement Queue using Stacks
根據(jù)隊(duì)列FIFO和棧FILO的特性谋作，使用兩個(gè)棧的話遵蚜，一個(gè)棧專入數(shù)據(jù)stack_in帖池，一個(gè)棧專出數(shù)據(jù)stack_out，所有數(shù)據(jù)走stack_out出吭净，即實(shí)現(xiàn)隊(duì)列
class Stack(object):
def __init__(self):
self.data = []
def push(self, x):
self.data.append(x)
def pop(self):
if self.data:
return self.data.pop(-1)
def empty(self):
if self.data:
return False
return True
def buttom(self):
if self.data:
return self.data[0]
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack_in = Stack()
self.stack_out = Stack()
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.stack_in.push(x)
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if self.stack_out.empty():
while not self.stack_in.empty():
data = self.stack_in.pop()
self.stack_out.push(data)
return self.stack_out.pop()
def peek(self):
"""
Get the front element.
:rtype: int
"""
if self.stack_out.empty() and not self.stack_in.empty():
return self.stack_in.data[0]
else:
return self.stack_out.data[-1]
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return self.stack_in.empty() and self.stack_out.empty()
