티스토리 뷰

Python

Data Structure

techbard 2016.05.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


댓글
댓글쓰기 폼
공지사항
Total
410,043
Today
5
Yesterday
38
«   2019/11   »
          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
글 보관함