Scribd
Upload
7 views14 pages

Data Structures: Stack and Queue Concepts

The document provides implementations for various data structures including stacks, queues, circular queues, linked lists, and binary trees in Python. It also includes algorithms for evaluating postfix expressions, checking balanced parentheses, implementing a queue with two stacks, and creating a priority queue. Additionally, it features a function to detect cycles in a linked list.

Uploaded by

matin.13.dob
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views14 pages

Data Structures: Stack and Queue Concepts

The document provides implementations for various data structures including stacks, queues, circular queues, linked lists, and binary trees in Python. It also includes algorithms for evaluating postfix expressions, checking balanced parentheses, implementing a queue with two stacks, and creating a priority queue. Additionally, it features a function to detect cycles in a linked list.

Uploaded by

matin.13.dob
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

class stack:

def __init__(self , limit=100):


)Stack( ‫پشته‬
[Link] = -1
‫ اولین‬،‫پشته یک ساختمان داده است که بر اساس اصل "آخرین ورودی‬
[Link] = limit
[Link] = [None]*limit .‫) انجام میشود‬LIFO - Last In, First Out( "‫خروجی‬

def push(self , item):


if self.is_full():
print("stack is full")
return
[Link] += 1
[Link][[Link]] = item

def pop(self):
if self.is_empty():
print("stack is empty")
return
popped_item = [Link][[Link]]
[Link]([Link])
[Link] -= 1
return popped_item

def is_empty(self):
return [Link] == -1 : )Dynamic Stack( ‫پشته پویا‬
def is_full(self):
class dynamic_stack:
return [Link] == [Link] - 1
def __init__(self):
[Link] = -1
def show(self): # or showV()
[Link] = []
if self.is_empty():
print("stack is empty")
def push(self, item):
return
[Link](item)
data = []
[Link] += 1
for i in range([Link] + 1):
[Link]([Link][i])
def pop(self):
return data
if self.is_empty():
print("stack is empty")
def peek(self): # or top()
return
if [Link] == -1:
popped_item = [Link][[Link]]
print("stack is empty")
[Link]()
return
[Link] -= 1
return [Link][[Link]]
return popped_item

def find(self , item):


def is_empty(self):
if self.is_empty():
return [Link] == -1
print("stack is empty")
return
for i in range([Link] + 1):
if [Link][i] == item:
return True
return False

def clear(self):
[Link] = -1
[Link] = []*[Link]
class queue():
)Queue( ‫صف‬
def __init__(self,size=100):
[Link] = -1
‫ یک ساختمان داده است که بر اساس اصل "اولین‬،‫ مانند پشته‬،‫صف‬
[Link] = -1
[Link] = size
.‫) عمل میکند‬FIFO - First In, First Out( "‫ اولین خروجی‬،‫ورودی‬
[Link] = [None]*size

def enqueue(self,item):
if self.is_full():
print("queue is full")
return
if [Link] == -1:
[Link] = 0
[Link] = 0
[Link][[Link]] = item
return
[Link] += 1
[Link][[Link]] = item

def dequeue(self):
if self.is_empty():
print("queue is empty")
return
[Link] += 1

def show(self): # or display()


if self.is_empty():
return None
data = []
for i in range([Link], [Link] + 1):
[Link]([Link][i])
return data

def is_empty(self):
return [Link] == -1

def is_full(self):
return [Link] == [Link] - 1

def peek(self): # or front()


if self.is_empty():
return
return [Link][[Link]]
class Cqueue: )Circular Queue( ‫صف حلقوی‬
def __init__(self,size=100):
[Link] = -1
[Link] = -1
[Link] = size
[Link] = [None]*size

def enqueue(self,item):
if self.is_full():
print("queue is full")
return
if self.is_empty():
[Link] = [Link] = 0
[Link][0] = item
return
[Link] = ([Link] + 1) % [Link]
[Link][[Link]] = item

def dequeue(self):
if self.is_empty():
print("queue is empty")
return
if [Link] == [Link]:
[Link] , [Link] = -1 , -1
return
def showIV(self):
[Link] = ([Link] + 1) % [Link]
if [Link] == [Link]:
return None
def is_empty(self):
data = []
return [Link] == -1
i = [Link] + 1
while True:
def is_full(self):
if [Link][i] == None:
return ([Link] + 1) % [Link] == [Link]
pass
else:
def showV(self):
[Link]([Link][i])
if [Link] == [Link]:
if i == [Link] - 1:
return None
break
data = []
i = (i + 1) % [Link]
i = [Link]
return data
while True:
[Link]([Link][i])
if i == [Link]:
break
i = (i + 1) % [Link]
return data
class Node:
def __init__(self, data): )Singly Linked List( ‫لیست پیوندی یک طرفه‬
[Link] = data
[Link] = None

class singly_linked_list:
def __init__(self):
[Link] = None

def insert_at_end(self,value): # or append()


if [Link] is None:
new_node = Node(value)
[Link] = new_node
return
current = [Link]
while [Link]:
current = [Link]
new_node = Node(value)
[Link] = new_node

def insert_at_first(self,value): # or prepend()


new_node = Node(value)
new_node.next = [Link]
[Link] = new_node

def insert_after(self,prev_node,value):
if [Link] is None:
return "Error"
current = [Link]
if [Link] is None:
if [Link] == prev_node:
new_node = Node(value) def is_find(self, value):

[Link] = new_node current = [Link]

else: while current:

return "Error" if [Link] == value:

while current: return True

if [Link] == prev_node: current = [Link]

new_node = Node(value) return False

new_node.next = [Link]
[Link] = new_node def replace(self, old_value, new_value):

return current = [Link]

current = [Link] while current:

return "Error" if [Link] == old_value:


[Link] = new_value

def delete_first(self): return

if [Link] is None: current = [Link]

return "list is empty"


current = [Link] def display(self): # or show()

[Link] = [Link] current = [Link]

del current while [Link]:


print(f"{[Link]} -> ",end="")

def is_empty(self): current = [Link]

return [Link] == None print([Link],end="")


)Circular Singly Linked List( ‫لیست پیوندی یک طرفه حلقوی‬

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class circular_singly_linked_list:
def __init__(self):
[Link] = None

def insert_at_end(self,value): # or append()


if [Link] is None:
new_node = Node(value)
new_node.next = new_node
[Link] = new_node
return
current = [Link]
while [Link] != [Link]:
current = [Link]
new_node = Node(value)
[Link] = new_node
new_node.next = [Link]

def insert_at_first(self,value): # or prepend()


new_node = Node(value)
if [Link] is None:
[Link] = new_node
new_node.next = new_node
else:
current = [Link]
new_node.next = [Link] def replace(self, old_value, new_value):
[Link] = new_node current = [Link]
while [Link] != [Link]: while current:
current = [Link] if [Link] == old_value:
[Link] = new_node [Link] = new_value
[Link] = new_node return
current = [Link]
def is_empty(self): if current == [Link]:
return [Link] == None break

def search(self, value): # or is_find def display(self): # or show()


current = [Link] current = [Link]
while current: while current:
if [Link] == value: print(f"{[Link]} -> ",end="")
return True current = [Link]
current = [Link] if current == [Link]:
if current == [Link]: break
break print([Link],end="")
return False
)Doubly Linked List( ‫لیست پیوندی دوطرفه‬

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class doubly_linked_list:
def __init__(self):
[Link] = None

def insert_at_end(self,value): # or append()


if [Link] is None:
new_node = Node(value)
[Link] = new_node
return
current = [Link]
while [Link]:
current = [Link]
new_node = Node(value) def delete_first(self):
[Link] = new_node if [Link] is None:
new_node.prev = current return "list is empty"
current = [Link]
def insert_at_first(self,value): # or prepend() [Link] = [Link]
new_node = Node(value) [Link] = [Link]
new_node.next = [Link] del current
if [Link]:
[Link] = new_node def is_empty(self):
[Link] = new_node return [Link] == None

def insert_after(self,prev_node,value): def is_find(self, value):


if [Link] is None: current = [Link]
return "Error" while current:
current = [Link] if [Link] == value:
if [Link] is None: return True
if [Link] == prev_node: current = [Link]
new_node = Node(value) return False
[Link] = new_node
else: def replace(self, old_value, new_value):
return "Error" current = [Link]
while current: while current:
if [Link] == prev_node: if [Link] == old_value:
new_node = Node(value) [Link] = new_value
new_node.next = [Link] return
new_node.prev = current current = [Link]
if [Link]:
[Link] = new_node def display(self): # or show()
[Link] = new_node current = [Link]
return while [Link]:
current = [Link] print(f"{[Link]} <-> ",end="")
return "Error" current = [Link]
print([Link],end="")
class Node:
)Binary Tree( ‫درخت باینری‬
def __init__(self, d):
[Link] = d
[Link] = None
[Link] = None

class Node:
def __init__(self, key): def inorder(self, node):
[Link] = None if node:
[Link] = None [Link]([Link])
[Link] = key print([Link], end=' ')
[Link]([Link])
def insert(self, key):
new_node = Node(key) def preorder(self, node):
if not [Link]: if node:
[Link] = new_node print([Link], end=' ')
return [Link]([Link])
queue = [[Link]] [Link]([Link])
while queue:
temp = [Link](0) def postorder(self, node):
if not [Link]: if node:
[Link] = new_node [Link]([Link])
return [Link]([Link])
else: print([Link], end=' ')
[Link]([Link])
if not [Link]: def level_order(self):
[Link] = new_node if not [Link]:
return return
else: queue = [[Link]]
[Link]([Link]) while queue:
temp = [Link](0)
def search(self, key): print([Link], end=' ')
if not [Link]: if [Link]:
return False [Link]([Link])
queue = [[Link]] if [Link]:
while queue: [Link]([Link])
node = [Link](0)
if [Link] == key:
return True
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
return False

def height(self, node):


if not node:
return 0
return 1 + max([Link]([Link]), [Link]([Link]))
‫نمونه سواالت‬
def evaluate_postfix(expression): ‫ الگوریتمی بنویسید که یک عبارت ریاضی در‬.1
stack = dynamic_stack()
‫نمادگذاری پسوندی را دریافت کرده و مقدار آن را‬
operators = "+-*/"
tokens = [Link]() ‫ از یک پشته برای حل مسئله استفاده‬.‫محاسبه کند‬
.‫کنید‬
for token in tokens:
if token not in operators:
[Link](float(token))
else:
right = [Link]()
left = [Link]()
if token == '+':
result = left + right
elif token == '-':
result = left - right
elif token == '*':
result = left * right
elif token == '/':
if right == 0:
raise ZeroDivisionError("Division by zero")
result = left / right
[Link](result)

return [Link]()

.‫ {} را بررسی کند و تشخیص دهد آیا پرانتزها به درستی بسته شدهاند یا خیر‬,][ ,)( ‫ تابعی بنویسید که یک رشته شامل پرانتزهای‬.2

def is_balanced(expression):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}

for char in expression:


if char in '([{':
[Link](char)
elif char in ')]}':
if not stack or stack[-1] != pairs[char]:
return False
[Link]()

return len(stack) == 0
class QueueWithTwoStacks:
‫ یک صف را با استفاده از دو پشته پیاده سازی کنید‬.3
def __init__(self):
self.stack_in = []
self.stack_out = []

def enqueue(self, x):


self.stack_in.append(x)

def dequeue(self):
if self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
if not self.stack_out:
print("Queue is empty")
return self.stack_out.pop()

def is_empty(self):
return not self.stack_in and not self.stack_out

class Node:
def __init__(self, data, priority): ‫) با‬Priority Queue( ‫ یک صف اولویت دار‬.4
[Link] = data
.‫استفاده از لیست پیوندی پیاده سازی کنید‬
[Link] = priority
[Link] = None

class PriorityQueue:
def __init__(self):
[Link] = None

def is_empty(self):
return [Link] is None

def enqueue(self, data, priority):


new_node = Node(data, priority)
if self.is_empty() or priority < [Link]:
new_node.next = [Link]
[Link] = new_node
else:
current = [Link]
while [Link] and [Link] <= priority:
current = [Link]
new_node.next = [Link]
[Link] = new_node

def dequeue(self):
if self.is_empty():
print("Queue is empty!")
return None
removed = [Link]
[Link] = [Link]
return [Link]
class Node:
‫ الگوریتمی بنویسید که تشخیص دهد آیا یک لیست‬.5
def __init__(self, data):
[Link] = data .‫پیوندی دارای حلقه است یا خیر‬
[Link] = None

def has_cycle(head):
slow = head
fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]

if slow == fast:
return True
return False

class Node:
‫ تابعی بنویسید که یک لیست پیوندی را به صورت‬.6
def __init__(self, data): .‫ گره) معکوس کند‬k ‫گروهی (هر‬
[Link] = data
[Link] = None

def reverse_k_group(head, k):


current = head
count = 0

while current and count < k:


current = [Link]
count += 1

if count == k:
reversed_head = reverse_k_group(current, k)
current = head
for _ in range(k):
next_node = [Link]
[Link] = reversed_head
reversed_head = current
current = next_node
head = reversed_head
return head

def print_list(node):
while node:
print([Link], end=" → " if [Link] else "\n")
node = [Link]
class Node: ‫ الگوریتمی بنویسید که یک درخت دودویی را به‬.7
def __init__(self, x):
‫صورت مورب پیمایش کند و مقادیر هر مورب را‬
[Link] = x
[Link] = None )diagonal traversal( .‫چاپ کند‬
[Link] = None

def diagonalRecur(root, level, levelData):


if root is None:
return
if level not in levelData:
levelData[level] = []
levelData[level].append([Link])
diagonalRecur([Link], level + 1, levelData)
diagonalRecur([Link], level, levelData)

def diagonal(root):
ans = []
levelData = {}
diagonalRecur(root, 0, levelData)
level = 0
while level in levelData:
[Link](levelData[level])
level += 1
return ans

.‫) دریافت کند و کوچکترین جد مشترک آنها را برگرداند‬BST( ‫ تابعی بنویسید که دو گره در یک درخت جستجوی دودویی‬.8

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

def find_LCA_BST(root, p, q):


if not root:
return None
if [Link] < [Link] and [Link] < [Link]:
return find_LCA_BST([Link], p, q)
if [Link] > [Link] and [Link] > [Link]:
return find_LCA_BST([Link], p, q)
return root
class Node:
‫ یک‬Inorder ‫ الگوریتمی بنویسید که پیمایش‬.9
def __init__(self, data):
[Link] = data ‫درخت دودویی را بدون بازگشت و با استفاده از‬
[Link] = None .‫یک پشته انجام دهد‬
[Link] = None

def inorder_iterative(root):
stack = []
current = root
while stack or current:
while current:
[Link](current)
current = [Link]
current = [Link]()
print([Link], end=" ")
current = [Link]

class Node:
def __init__(self, key, value):
‫ را با‬LRU (Least Recently Used) ‫ یک سیستم کش‬.10
[Link] = key ‫ترکیب یک صف (بر اساس لیست پیوندی) و یک هش مپ‬
[Link] = value
.‫ را شرح دهید‬put ‫ و‬get ‫پیادهسازی کنید و عملیات‬
[Link] = None
[Link] = None

class LRUCache:
def __init__(self, capacity):
[Link] = capacity
[Link] = dict()

[Link] = Node(0, 0)
[Link] = Node(0, 0)
[Link] = [Link]
[Link] = [Link]

def _remove(self, node):


prev = [Link]
nxt = [Link]
[Link] = nxt
[Link] = prev

def _add_to_front(self, node):


[Link] = [Link]
[Link] = [Link]
def put(self, key, value):
[Link] = node
if key in [Link]:
[Link] = node
self._remove([Link][key])
elif len([Link]) == [Link]:
def get(self, key):
lru = [Link]
if key in [Link]:
self._remove(lru)
node = [Link][key]
del [Link][[Link]]
self._remove(node)
node = Node(key, value)
self._add_to_front(node)
self._add_to_front(node)
return [Link]
[Link][key] = node
return -1
class Node:
def __init__(self, data): ‫ پیاده سازی صف با لیست پیوندی‬.11
[Link] = data
[Link] = None
def dequeue(self):
if self.is_empty():
class LinkedQueue:
print("queue is empty")
def __init__(self):
return None
[Link] = None
value = [Link]
[Link] = None
[Link] = [Link]
if [Link] is None:
def is_empty(self):
[Link] = None
return [Link] is None
return value

def enqueue(self, value):


def peek(self):
new_node = Node(value)
if self.is_empty():
if [Link] is None:
return None
[Link] = [Link] = new_node
return [Link]
else:
[Link] = new_node
def display(self):
[Link] = new_node
current = [Link]
while current:
print([Link], end=" ")
current = [Link]

class Node: ‫ پیاده سازی پشته با لیست پیوندی‬.12


def __init__(self, data):
[Link] = data
[Link] = None

class LinkedStack:
def __init__(self):
[Link] = None

def is_empty(self):
return [Link] is None

def push(self, value): def peek(self):

new_node = Node(value) if self.is_empty():

new_node.next = [Link] print("stack is empty")

[Link] = new_node return None


return [Link]

def pop(self):
if self.is_empty(): def display(self):

print("stack is empty") current = [Link]

return None while current:

value = [Link] print([Link], end=" ")

[Link] = [Link] current = [Link]

return value
def find_lca(root, n1, n2):
‫ کوچک ترین جد مشترک دو گره در یک درخت دودویی‬.13
if root is None:
return None )BT(
if [Link] == n1 or [Link] == n2: ‫ مراجعه کنید‬8 ‫ به سوال‬class node ‫برای‬ •
return root
left_lca = find_lca([Link], n1, n2)
right_lca = find_lca([Link], n1, n2)
if left_lca and right_lca:
return root
return left_lca if left_lca is not None else right_lca

‫ کوچک ترین جد مشترک دو گره بدون استفاده از تابع بازگشتی‬.14


def find_path(root, target):
stack = [(root, [root])]
while stack:
node, path = [Link]()
if [Link] == target:
return path
if [Link]:
[Link](([Link], path + [[Link]]))
if [Link]:
[Link](([Link], path + [[Link]]))
return None

def find_lca(root, n1, n2):


path1 = find_path(root, n1)
path2 = find_path(root, n2)

if path1 is None or path2 is None:


return None

lca = None
for u, v in zip(path1, path2):
if [Link] == [Link]:
lca = u
else:
break
return lca

You might also like