Структури на данни — опашки и стекове

известен още като FIFO & LIFO

В компютърните науки структурата на данни е конкретен начин за организиране на данни в компютър, така че да могат да се използват ефективно. Структурите на данни предоставят начин на системите да управляват ефективно големи количества данни, като например бази данни. Тази публикация ще бъде една от многото в поредица, която анализира тънкостите на конкретни структури от данни. Като начало ще разгледаме двете основни структури от данни: Опашки и Стекове.

Опашка
Както подсказва името, структура от данни на опашка се държи точно като опашка (или линия). С други думи, това е структура, дефинирана от нейните методи „първи влязъл, първи излязъл“. Тези методи за добавяне и премахване често се представят с имената на методите enqueueи dequeue.

Казано от гледна точка на JavaScript, опашката може да се разглежда като масив с методите pushи shift. В това упражнение ще се съсредоточим върху това как да изградим опашка от нулата.

// Create our Queue Class
  // Queue will have a storage property
  // Queue will have two counter variables to identify the first and last keys 
// Create an Enqueue method
  // Enqueue will add values onto the storage
// Create a Dequeue method
  // Store dequeued value onto a temporary value
  // remove the first value
  // return the first temporary value

Не забравяйте, че методът за изваждане от опашката трябва да връща стойността от опашката почти по същия начин, по който shift връща изместената стойност на масив. Сега, след като сме псевдокодирали, ние сме готови да приложим решение:

// Create our Queue Class
class Queue {
  constructor() {
    this.storage = {};
    this.first = 0;
    this.last = 0;
  }
}
// Create an Enqueue method
Queue.prototype.enqueue = (value) => {
  this.storage[this.last++] = value;
} 
// Create a Dequeue method
Queue.prototype.dequeue = () => {
  let temp = this.storage[this.first];
  delete this.storage[this.first];
  this.first++
  return temp;
}

Доста просто, нали? Въпреки че може да има по-интуитивни методи за поставяне на опашка и премахване на опашка, този по-горе ни позволява да запазим времевата си сложност до постоянно време, като същевременно не използваме естествени методи на JavaScript Object.

Стек
Както подсказва името, структурата от данни на стека се държи точно като стек от неща. С други думи, това е структура, дефинирана от нейните методи „Последен влязъл, първи излязъл“. Един лесен начин да мислите за купчина би бил като купчина чинии – след като чиниите започнат да се трупат, няма да миете най-стария съд в купчината, ще искате да започнете от върха (последния в стека) и работете надолу. Тези методи за добавяне и премахване често се представят с имената на методите pushи pop.

Казано от гледна точка на JavaScript, стекът може да се разглежда като масив с методите pushи pop. В това упражнение ще се съсредоточим върху това как да изградим стек от нулата.

// Create our Stack Class
  // Stack will have a storage property
  // Stack will have a counter variable to identify the keys
  // Stack will have a length property
// Create an Push method
  // Push will add values onto the end of the storage 
// Create a Pop method
  // Store popped values onto a temporary value
  // remove the last value
  // return the temporary value

Не забравяйте, че точно като родния метод за pop array, тази функция pop ще върне изскачащата стойност. Сега, след като сме псевдокодирали, ние сме готови да приложим решение:

// Create our Stack Class
class Stack {
  constructor() {
    this.storage = {};
    this.count = 0;
    this.length = Object.keys(this.storage).length || 0;
  }
}
// Create a Push method
Stack.prototype.enqueue = (value) => {
  this.storage[this.last++] = value;
}
// Create a Pop method
Stack.prototype.dequeue = () => {
  let temp = this.storage[--this.length];
  delete this.storage[this.length];
  return temp;
}

Този пример показва точно как можем да използваме съществуващите Object методи, за да внедрим стека, но има много други начини за внедряване на стек, без да използваме тези естествени методи.

Обобщение:
- Структурите на данни са начини за ефективно и ефективно съхраняване на данни
- Основните структури на данни включват опашки ('FIFO) и стекове ('LIFO)
- И двете Опашките и купчините използват методи за добавяне и премахване
- Опашките могат да се разглеждат като чакащи на опашка, докато купчините могат да се разглеждат като купчина ястия

Това е част I от серия от много части за структурите на данни. Ако се интересувате да продължите с поредицата за структури от данни и да научите за свързани списъци, щракнете тук.

Структури на данни — опашки и стекове

Подобни въпроси