Разумевање имплементације Куеуе у Питхон-у

Структуре података играју кључну улогу у свету програмирања. Они нам помажу да организујемо своје податке на начин који се може ефикасно користити. Ред је једна од најједноставнијих доступних структура података.

У овом чланку ћемо научити о реду чекања и његовој имплементацији у Питхон-у.

Шта је ред чекања?

Ред је линеарна структура података која прати принцип Фирст Ин/Фирст Оут (ФИФО). То је супротно структури података стека.

Можемо да упоредимо ред са редом из стварног живота на шалтеру биоскопских карата. Погледајмо илустрацију реда на следећи начин.

Ако посматрате ред на шалтеру, друга особа може отићи на шалтер тек након што прва особа заврши свој посао. Овде прва особа долази на шалтер па друга особа. Дакле, овде људи следе принцип ФИФО (први ушао/први изашао). Ко први дође, он/она ће први завршити посао. Сличну врсту редова можемо видети у нашем свакодневном животу.

Структура података реда такође прати исти принцип. Сада знате шта су редови и њихов принцип. Хајде да видимо операције које се могу извршити над структуром података реда.

Операције у реду чекања

Слично стеку, наћи ћемо две главне операције у структури података реда.

у реду (подаци)

Додаје нове податке у ред на крају. Бочна страна се зове задња.

декуеуе()

Уклања податке са предње стране реда. Страна се зове предња страна.

Погледајмо илустрације операција редова ради бољег разумевања. Једна слика говори хиљаду речи.

Можемо написати неке помоћне функције да бисмо добили више информација о реду чекања. Нема ограничења у броју помоћних функција које ћете имати. Хајде да се за сада задржимо на најважнијем, једном поменутом у наставку.

задњи()

Враћа први елемент са краја реда.

фронт()

Враћа први елемент са почетка реда.

Празно()

Враћа да ли је ред празан или не.

Није ли вам досадно? Мислим на концептуалне теме.

За мене да!

Али, не можемо ништа да урадимо без познавања појмова. Морамо то да употпунимо пре имплементације. Не брините, време је да запрљамо руке неким кодом.

Претпостављам да имате инсталиран Питхон на рачунару, ако не, можете испробати и онлајн компајлер.

  Како да приступим свом Епиц Гамес налогу

Имплементација реда чекања

Имплементација реда неће трајати више од 15 минута за програмера. Кад научиш, рећи ћеш. Можда га можете имплементирати у року од неколико минута након овог упутства.

Постоји више начина за имплементацију реда у Питхон-у. Хајде да погледамо различите имплементације редова корак по корак.

#1. Листа

Листа је уграђени тип података у Питхон-у. Користићемо тип података листе за имплементацију реда у класи. Провешћемо вас кроз различите кораке за имплементацију структуре података реда од нуле без икаквих модула. Хајде да ускочимо у то.

Корак 1:

Напишите класу под називом Куеуе.

class Queue:
	pass

Корак 2:

Мора постојати нека варијабла за чување података из реда у класи. Назовимо то елементима. И то је листа наравно.

class Queue:

	def __init__(self):
		self.elements = []

Корак 3:

Да бисмо убацили податке у ред, потребан нам је метод у класи. Метод се зове енкуеуе као што смо већ дискутовали у претходном одељку туторијала.

Метода узима неке податке и додаје их у ред (елементе). Можемо користити метод додавања типа података листе да бисмо додали податке на крај реда.

class Queue:

	# ...

	def enqueue(self, data):
		self.elements.append(data)
		return data

Корак 4:

Ред мора да има излаз. И то се зове декуеуе. Мислим да сте већ погодили да ћемо користити поп метод типа података листе. Ако сте погодили или не, живјели!

Метода поп типа података листа брише елемент са листе датог индекса. Ако нисмо дали никакав индекс, онда брише последњи елемент листе.

Овде треба да избришемо први елемент листе. Дакле, морамо проследити индекс 0 у поп метод.

class Queue:

	# ...

	def dequeue(self):
		return self.elements.pop(0)

То је довољно за ред. Али, потребне су нам помоћне функције да бисмо тестирали да ли операције реда функционишу исправно или не. Хајде да напишемо и помоћне функције.

Корак 5:

Метода реар() се користи за добијање последњег елемента реда. Негативно индексирање у типу података листе помаже нам да добијемо последњи елемент реда.

class Queue:

	# ...

	def rear(self):
		return self.elements[-1]

Корак 6:

Метод фронт() се користи за добијање првог елемента реда. Први елемент реда можемо добити помоћу индекса листе.

class Queue:

	# ...

	def front(self):
		return self.elements[0]

Корак 7:

Метода ис_емпти() се користи за проверу да ли је ред празан или не. Можемо да проверимо дужину листе.

class Queue:

	# ...

	def is_empty(self):
		return len(self.elements) == 0

Фуј! завршио имплементациони део структуре података реда. Морамо да креирамо објекат који ће класа Куеуе користити.

  Како користити апликацију Стеам Линк за играње Стеам игара на свом телефону

Хајде да то урадимо.

class Queue:

	# ...

if __name__ == '__main__':
	queue = Queue()

Сада имамо објекат Куеуе. Хајде да то тестирамо са неким низом операција.

  • Проверите да ли је ред празан или не користећи методу ис_емпти. Требало би да врати Труе.
  • Додајте бројеве 1, 2, 3, 4, 5 у ред користећи методу чекања.
  • Метод ис_емпти треба да врати Фалсе. Провери.
  • Одштампајте предње и задње елементе користећи методе напред и позади.
  • Уклоните елемент из реда помоћу методе декуеуа.
  • Проверите предњи елемент. Требало би да врати елемент 2.
  • Сада уклоните све елементе из реда.
  • Метод ис_емпти треба да врати Труе. Провери.

Мислим да је то довољно да тестирамо имплементацију нашег реда. Напишите код за сваки горе поменути корак да бисте тестирали ред.

Јеси ли ти написао код?

Не, не брини.

Проверите код испод.

class Queue:

	def __init__(self):
		self.elements = []

	def enqueue(self, data):
		self.elements.append(data)
		return data

	def dequeue(self):
		return self.elements.pop(0)

	def rear(self):
		return self.elements[-1]

	def front(self):
		return self.elements[0]

	def is_empty(self):
		return len(self.elements) == 0

if __name__ == '__main__':
	queue = Queue()

	## checking is_empty method -> True
	print(queue.is_empty())

	## adding the elements
	queue.enqueue(1)
	queue.enqueue(2)
	queue.enqueue(3)
	queue.enqueue(4)
	queue.enqueue(5)

	## again checking is_empty method -> False
	print(queue.is_empty())

	## printing the front and rear elements using front and rear methods respectively -> 1, 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing the element -> 1
	queue.dequeue()

	## checking the front and rear elements using front and rear methods respectively -> 2 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing all the elements
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()

	## checking the is_empty method for the last time -> True
	print(queue.is_empty())

Мислим да покрећете горњи програм. Можете добити излаз сличан следећем резултату.

True
False
1 5
2 5
True

Можемо директно користити тип података листе као структуру података реда. Горња имплементација реда вам помаже да боље разумете имплементацију реда у другим програмским језицима.

Такође можете користити горњу имплементацију класе реда у другом програму пројекта једноставним креирањем објекта као што смо раније радили.

Имплементирали смо ред од нуле користећи тип података листе. Да ли постоје уграђени модули за ред чекања? Да! имамо уграђене имплементације редова. Хајде да их видимо.

#2. дека из збирки

Реализован је као двострани ред. Пошто подржава додавање и уклањање елемената са оба краја, можемо га користити као стек и ред. Хајде да видимо имплементацију реда чекања користећи декуеуе.

Имплементира се коришћењем других структура података које се називају двоструко повезана листа. Дакле, перформансе уметања и брисања елемената су доследне. Приступ елементима са средње повезане листе трајао је О(н) времена. Можемо га користити као ред, јер нема потребе за приступом средњим елементима из реда.

  Добро дизајнирано постоље за МацБоок које штеди простор

Хајде да проверимо различите методе које нам декуеуе нуди.

  • аппенд(дата) – користи се за додавање података у ред
  • поплефт() – користи се за уклањање првог елемента из реда

Не постоје алтернативне методе за предње, задње и ис_емпти. Можемо да одштампамо цео ред на месту предњег и задњег метода. Затим можемо користити метод лен да проверимо да ли је ред празан или не.

Пратили смо низ корака за тестирање имплементације реда у претходном. Хајде да следимо исти низ корака и овде.

from collections import deque

## creating deque object
queue = deque()

## checking whether queue is empty or not -> True
print(len(queue) == 0)

## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## again checking whether queue is empty or not -> False
print(len(queue) == 0)

## printing the queue
print(queue)

## removing the element -> 1
queue.popleft()

## printing the queue
print(queue)

## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

Добићете резултат сличан следећем излазу.

True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3. Ред из реда

Питхон има уграђени модул под називом куеуе који служи класу која се зове Куеуе за имплементацију реда. Слично је оној коју смо раније имплементирали.

Прво, хајде да проверимо различите методе класе Куеуе.

  • пут(подаци) – додаје или гура податке у ред
  • гет() – уклања први елемент из реда и враћа га
  • емпти() – враћа да ли је стек празан или не
  • ксизе() – враћа дужину реда.

Хајде да имплементирамо ред са горњим методама.

from queue import Queue

## creating Queue object
queue_object = Queue()

## checking whether queue is empty or not -> True
print(queue_object.empty())

## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## again checking whether queue is empty or not -> False
print(queue_object.empty())

## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## checking the queue size
print("Size", queue_object.qsize())

print(queue_object.get())
print(queue_object.get())

## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

Проверите излаз горњег кода.

True
False
1
2
3
Size 2
4
5
True

Постоје неке друге методе у класи Куеуе. Можете их истражити помоћу уграђене функције дир.

Закључак

Надам се да сте научили о структури података редова и њеној имплементацији. То је то за ред. Можете да користите ред на различитим местима где треба да се обради по ФИФО (први ушао/први изашао). Користите ред у решавању проблема кад год добијете случај да га користите.

Заинтересовани сте за савладавање Питхон-а? Погледајте ове ресурсе за учење.

Срећно кодирање 🙂 👨‍💻