栈和队列的基本实现和特性

Stack： last in first out
Queue： last in last out

insert: O(1)
delete: O(1)
lookup: O(n)

栈的实现

  1. function Stack() {
  2.     this.dataStore = []
  3.     this.top = 0
  4. }
  5. Stack.prototype.push = function(el) {
  6.     this.dataStore[this.top++] = el
  7. }
  8. Stack.prototype.pop = function() {
  9.     return this.dataStore[--this.top]
  10. }
  11. Stack.prototype.peek = function() {
  12.     return this.dataStore[this.top-1]
  13. }
  14. Stack.prototype.length = function() {
  15.     return this.top
  16. }

队列的实现

  1. function Queue() {
  2.     this.dataStore = []
  3. }
  4. Queue.prototype.enqueue = function(el) {
  5.     this.dataStore.push(el)
  6. }
  7. Queue.prototype.dequeue = function() {
  8.     return this.dataStore.shift()
  9. }
  10. Queue.prototype.front = function() {
  11.     return this.dataStore[0]
  12. }
  13. Queue.prototype.back = function() {
  14.     return this.dataStore[this.dataStore.length - 1]
  15. }
  16. Queue.prototype.empty = function() {
  17.     return this.dataStore.length === 0
  18. }

双端队列的实现

  1. function Dequeue(k) {
  2.     this.dataStore = []
  3. }
  4. Dequeue.prototype.insertFront = function (value) {
  5.     this.dataStore.unshift(value)
  6. }
  7. Dequeue.prototype.insertLast = function (value) {
  8.     this.dataStore.push(value)
  9. }
  10. Dequeue.prototype.deleteFront = function () {
  11.     if(this.dataStore.length) {
  12.         this.dataStore.shift()
  13.     }
  14. }
  15. Dequeue.prototype.deleteLast = function () {
  16.     if(this.dataStore.length) {
  17.         this.dataStore.pop()
  18.     }
  19. }
  20. Dequeue.prototype.getFront = function () {
  21.     if (this.dataStore.length) {
  22.         return this.dataStore[0]
  23.     }
  24. }
  25. Dequeue.prototype.getRear = function () {
  26.     if (this.dataStore.length) {
  27.         return this.dataStore[this.dataStore.length - 1]
  28.     }
  29. }
  30. Dequeue.prototype.empty = function () {
  31.     return this.dataStore.length === 0
  32. }

优先队列

insert: O(1)
delete: O(1)
lookup: O(logN)

哈希表

  1. function HashTable() {
  2.     this.table = new Array(137)
  3. }
  4. HashTable.prototype.simpleHash = function (data) {
  5.     var total = 0
  6.     for(var i = 0; i < data.length; ++i) {
  7.         total += data.charCodeAt(i)
  8.     }
  9.     return total % this.table.length
  10. }
  11. HashTable.prototype.put = function (data) {
  12.     var pos = this.simpleHash(data)
  13.     this.table[pos] = data
  14. }
  15. HashTable.prototype.get = function (data) {
  16.     return this.table[this.simpleHash(data)]
  17. }

Map

get
set
has
delete

set

has
add
delete