Data Structure

Python

by techbard 2016. 5. 27. 11:37

# Stack Implementation

class Stack(object):

def __init__(self):

self.items = []

def isEmpty(self):

return self.items == []

def push(self, item):

self.items.append(item)

def pop(self):

return self.items.pop()

def peek(self):

return self.items[len(self.items)-1]

def size(self):

return len(self.items)

s = Stack()

print(s.isEmpty())

s.push(1)

s.push('two')

print(s.peek())

print(s.size())

s.pop()

s.pop()

print(s.size())

# 결과

True

two

2

0

# Queue Implementation

class Queue(object):

def __init__(self):

self.items = []

def isEmpty(self):

return self.items == []

def enquque(self, item):

self.items.insert(0, item)

def dequeue(self):

return self.items.pop()

def size(self):

return len(self.items)

q = Queue()

print(q.size())

q.enquque(1)

q.enquque(2)

q.dequeue()

print(q.items)

# 결과

0

[2]

# Deque Implementation

class Deque(object):

def __init__(self):

self.items = []

def isEmpty(self):

return self.items == []

def addFront(self, item):

self.items.append(item)

def addRear(self, item):

self.items.insert(0, item)

def removeFront(self):

return self.items.pop()

def removeRear(self):

return self.items.pop(0)

def size(self):

return len(self.items)

d = Deque()

d.addFront('hello')

d.addRear('world')

print(d.size())

print(d.removeFront() + ' ' + d.removeRear())

# 결과

2

hello world

# Balanced Parentheses Check

def balance_check(s):

if len(s) % 2 != 0:

return False

opening = set('([{')

matches = set([('(', ')'), ('[', ']'), ('{', '}')] )

stack = []

for paren in s:

if paren in opening:

stack.append(paren)

else:

if len(stack) == 0:

return False

last_opening = stack.pop()

if (last_opening, paren) not in matches:

return False

return len(stack) == 0

print(balance_check('()[]'))

# 결과

True

# Queue using 2 Stacks

class Queue2Stacks(object):

def __init__(self):

self.in_stack = []

self.out_stack = []

def enqueue(self, item):

self.in_stack.append(item)

def dequeue(self):

if not self.out_stack:

while self.in_stack:

self.out_stack.append(self.in_stack.pop())

return self.out_stack.pop()

q = Queue2Stacks()

q.enqueue(1)

q.enqueue(2)

q.enqueue(3)

o = q.dequeue()

print(o)

print(q.out_stack)

print(q.in_stack)

# 결과

1

[3, 2]

[]

# Singly Linked List Cycle Check

def cycle_check(node):

marker1 = node

marker2 = node

while marker2 != None and marker2.next_node != None:

marker1 = marker1.next_node

marker2 = marker2.next_node.next_node

if marker2 == marker1:

return True

return False

class Node(object):

def __init__(self, values):

self.value = value

self.next_node = None

# Linked List Reversal

class Node(object):

def __init__(self, value):

self.value = value

self.next_node = None

def reverse(head):

current = head

previous = None

next_node = None

while current:

next_node = current.next_node

current.next_node = previous

previous = current

current = next_node

return previous

a = Node(1)

b = Node(2)

c = Node(3)

d = Node(4)

a.next_node = b

b.next_node = c

c.next_node = d

print(a.next_node.value)

print(b.next_node.value)

print(c.next_node.value)

reverse(a)

print(b.next_node.value)

print(c.next_node.value)

print(d.next_node.value)

# 결과

2

3

4

1

2

3

# Representing a Tree

class BinaryTree(object):
def __init__(self, rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None

def insertLeft(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRight(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

def getRightChild(self):
return self.rightChild

def getLeftChild(self):
return self.leftChild

def setRootVal(self, obj):
self.key = obj

def getRoolVal(self):
return self.key

r = BinaryTree('a')

r.insertLeft('b')

o = r.getLeftChild().getRoolVal()

print(o)

# 결과
b

# deque supports both first-in, first-out (queue) &
# last-in, first-out (stack) behaviour

from collections import deque
from string import ascii_lowercase

def palindrome(sentence):
letters = deque()

for char in sentence:
char = char.lower()
# remove whilte space
if char in ascii_lowercase:
letters.append(char)

while len(letters) > 1:
if letters.popleft() != letters.pop():
return False

return True

o = palindrome("madam, i'm adam")
print(o)

# 결과
True

def balanced(expr):
groupings = {
')': '(',
']': '[',
'>': '<',
'}': '{'}

stack = []
for char in expr:
if char in groupings.values():
stack.append(char)

elif char in groupings:
if not stack or stack.pop() != groupings[char]:
return False

return not stack

o = balanced('()')
print(o)
o = balanced('())')
print(o)

# 결과
True
False

# heapq module

from random import randrange
# nums = [randrange(0, 100) for _ in range(10)]
nums = [20, 22, 33, 29, 24, 67, 81, 77, 64, 40]

from heapq import heapify
heapify(nums)

print(nums)

from heapq import heappush
heappush(nums, 55)

print(nums)

from heapq import nsmallest, nlargest
print(nlargest(3, nums), nsmallest(3, nums))

# 결과
[20, 22, 33, 29, 24, 67, 81, 77, 64, 40]
[20, 22, 33, 29, 24, 67, 81, 77, 64, 40, 55]
[81, 77, 67] [20, 22, 24]

# heapq module - heappop()

nums = [20, 22, 33, 29, 24, 67, 81, 77, 64, 40]
from heapq import heappop

while nums:
print(heappop(nums))

# 결과
20
22
24
29
33
40
64
67
77
81