iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 6

【Day6】[資料結構]-堆疊Stack-實作

堆疊(Stack)建立的方法

  • push: 新增元素
  • pop: 從頂端移除元素
  • peek: 查看頂端(top)元素
  • size: 查看此堆疊的元素量

堆疊的介紹可以參考此篇


JavaScript(使用陣列)

//Stack

class Stack {
  constructor(){
    this.list = []
  }
  // 新增元素
  push(data) {
    this.list.push(data)
  }
  // 從頂端移除元素
  pop(){
    return this.list.pop()
  }
  // 此堆疊元素量
  size(){
    return this.list.length;
  }
  // 查看最頂端元素
  peek(){
    return this.list[this.list.length -  1]
  }
}

let stack = new Stack()
stack.push(20)
stack.push(60)
console.log(stack.size())//2
console.log(stack.peek())//60
stack.pop()
console.log(stack.peek())//20

陣列的介紹可以參考此篇


JavaScript(使用鏈結串列)

//Stack

class StackNode {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedStack {
  constructor() {
    this.top = null
    this.length = 0
  }
  
  // 新增元素
  push(data) {
    let node = new StackNode(data)
    if(!this.top){
      this.top = node
      this.length = 1
    }else{
        let current = new StackNode(data)
      current.next = this.top
      this.top = current
      this.length+=1
    }
    
  }
  
  // 刪除頂端元素
  pop() {
    if(!this.top){
      return null
    }else{
      this.top = this.top.next
      this.length -= 1
    }
  }
  
  // 查看最頂端元素
  peek() {
    if(!this.top){
      return null
    }else{
      return this.top.data
    }
  }

  // 此堆疊元素量
  size() {
    return this.length
  }


}
let stack = new LinkedStack()
stack.push('20')
stack.push('30')
stack.push('40')
console.log(stack.size())//3
console.log(stack.peek())//"40"
stack.pop()
console.log(stack.peek())//"30"
console.log(stack.size())//2
stack.pop()
console.log(stack.size())//1
console.log(stack.peek())//"20"

Python(使用鏈結串列)

#Stack
class StackNode():
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = None


class LinkedStack():
    def __init__(self, top=None):
        self.top = top
    
    def push(self, data):
        if self.top is None:
            self.top = StackNode(data)
        else:
            current = StackNode(data)
            current.next = self.top
            self.top = current
    
    def pop(self):
        if self.top is None:
            return None
        else:
            self.top = self.top.next
            return

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

    def size(self):
        count = 0
        current = self.top
        while current:
            count += 1
            current = current.next
        return count

stack = LinkedStack()
stack.push('20')
stack.push('30')
stack.push('40')
print(stack.size())#3
print(stack.peek())#"40"
stack.pop()
print(stack.peek())#"30"
print(stack.size())#2
stack.pop()
print(stack.size())#1
print(stack.peek())#"20"

鏈結串列的介紹可以參考此篇


上一篇
【Day5】[資料結構]-堆疊Stack
下一篇
【Day7】[資料結構]-佇列Queue
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言