Stack
image.png
由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。实现方式主要有顺序栈和链栈
基本操作:
init: -> Stack
push: N x Stack -> Stack
top: Stack -> (N U ERROR)
pop: Stack -> Stack
isempty: Stack -> Boolean
一、先看LeetCode 155. Min Stack
- 顺序栈， 使用python的list实现
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)
- 链栈，由于栈操作只在一断操作，可以用单链表采用头插法实现
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函数需要的时间复杂度是O(n)，如果要降低getMin的时间复杂度，可以每个数据元存储当前值加当前最小值，需要空间复杂度O(n)
Queue
image.png
是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
那么如何用链表实现一个队列呢，首先队列是双端操作，涉及到出队的时候需要删除尾节点，如果用单链表的话每次删除都是O(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
用队列实现栈，这里先用list实现一个队列FIFO，根据栈的特性FILO,
所以用两个队列，入栈的操作直接压入有数据的队列，当出栈是直接把有数据的队列依次pop到另一个空队列，当剩下最后一个数据即栈顶元素
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
根据队列FIFO和栈FILO的特性，使用两个栈的话，一个栈专入数据stack_in，一个栈专出数据stack_out，所有数据走stack_out出，即实现队列
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()
