今天是day8，
題目一：使用棧實(shí)現(xiàn)隊(duì)列
//先實(shí)現(xiàn)一個(gè)棧,給定int數(shù)組一個(gè)別名Mystack
type Mystack []int
//使用引用傳遞值，將v使用append追加至形參s中
func (s *Mystack) Push(v int){
*s = append(*s,v)
}
//使用val和切片獲取*s的最后一個(gè)元素并調(diào)整*s為當(dāng)前位置并將val返回出，從而實(shí)現(xiàn)了出棧
func (s *Mystack) Pop() int{
//
val := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return val
}
//返回最后一個(gè)元素
func (s *Mystack) Peek() int{
return (*s)[len(*s)-1]
}
func (s *Mystack) Size() int {
return len(*s)
}
func (s *Mystack) Empty() bool {
return s.Size() == 0
}
//如上先實(shí)現(xiàn)一個(gè)棧，聲明兩個(gè)數(shù)組一個(gè)in一個(gè)out
type MyQueue struct {
StackIn *Mystack
StackOut *Mystack
}
//使用結(jié)構(gòu)體賦值并初始化兩個(gè)數(shù)組為空
func Constructor() MyQueue {
return MyQueue{
StackIn: &Mystack{},
StackOut: &Mystack{},
}
}
//直接使用棧的push來推進(jìn)元素
func (this *MyQueue) Push(x int) {
this.StackIn.Push(x)
}
//先填充out數(shù)組，再讓out數(shù)組彈出
func (this *MyQueue) Pop() int {
this.fillStackOut()
return this.StackOut.Pop()
}
func (this *MyQueue) Peek() int {
this.fillStackOut()
return this.StackOut.Peek()
}
func (this *MyQueue) Empty() bool {
return this.StackIn.Empty() && this.StackOut.Empty()
}
//該方法用于填充out數(shù)組
func (this *MyQueue) fillStackOut() {
if this.StackOut.Empty() {
for !this.StackIn.Empty() {
val := this.StackIn.Pop()
this.StackOut.Push(val)
}
}
}
class MyQueue:
def __init__(self):
"兩個(gè)用來存放操作數(shù)值的數(shù)組"
self.stack_in = []
self.stack_out = []
"將元素壓入隊(duì)列中"
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
"先判空"
if self.empty():
return None
"這里一個(gè)遞歸"
if self.stack_out:
return self.stack_out.pop()
else:
"遍歷已有的in數(shù)組并將out數(shù)組值不斷壓入"
for i in range(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
"返回隊(duì)列頭元素，即用ans來獲取pop并將其壓入out數(shù)組中此時(shí)的ans就是第一個(gè)"
def peek(self) -> int:
ans = self.pop()
self.stack_out.append(ans)
return ans
"判空即in數(shù)組和out數(shù)組都不存在"
def empty(self) -> bool:
return not (self.stack_in or self.stack_out)
題目二：用隊(duì)列實(shí)現(xiàn)棧
from collections import deque
class MyStack:
def __init__(self):
"直接聲明兩個(gè)數(shù)組為deque即隊(duì)列"
self.queue_in = deque()
self.queue_out = deque()
def push(self, x: int) -> None:
self.queue_in.append(x)
"先判空，如果不空，遍歷整個(gè)in隊(duì)列并將其左彈出后再壓入out隊(duì)列中"
def pop(self) -> int:
if self.empty():
return None
for i in range(len(self.queue_in) - 1):
self.queue_out.append(self.queue_in.popleft())
"此時(shí)交換in out隊(duì)列值，最終返回out隊(duì)列的左彈出值"
self.queue_in,self.queue_out = self.queue_out,self.queue_in
return self.queue_out.popleft()
"先判空，再遍歷整個(gè)in隊(duì)列，將其值左彈出后壓入out隊(duì)列中"
def top(self) -> int:
if self.empty():
return None
for i in range(len(self.queue_in)-1):
self.queue_out.append(self.queue_in.popleft())
self.queue_in,self.queue_out = self.queue_out,self.queue_in
"用temp記錄out隊(duì)列的左彈出值并將其壓入in隊(duì)列中，最后返回temp就是要獲得的值"
temp = self.queue_out.popleft()
self.queue_in.append(temp)
return temp
def empty(self) -> bool:
return len(self.queue_in) == 0
from collections import deque
class MyStack:
def __init__(self):
self.que = deque()
def push(self, x: int) -> None:
self.que.append(x)
def pop(self) -> int:
if self.empty():
return None
for i in range(len(self.que) - 1):
self.que.append(self.que.popleft())
return self.que.popleft()
def top(self) -> int:
if self.empty:
return None
for i in range(len(self.que) - 1):
self.que.append(self.que.popleft())
temp = self.que.popleft()
self.que.append(temp)
return temp
def empty(self) -> bool:
return not self.que
type MyStack struct {
queue1 []int
queue2 []int
}
func Constructor() MyStack {
return MyStack{
queue1:make([]int,0),
queue2:make([]int,0),
}
}
//先將所有元素存儲(chǔ)在queue2中再調(diào)用move來交換元素
func (this *MyStack) Push(x int) {
this.queue2 = append(this.queue2,x)
this.Move()
}
//
func (this *MyStack) Move(){
if len(this.queue1) == 0{
//交換，queue1置為queue2，queue2置為空
this.queue1,this.queue2 = this.queue2,this.queue1
}else{
//queue1元素依次從頭開始追加至queue2中
this.queue2 = append(this.queue2,this.queue1[0])
this.queue1 = this.queue1[1:]//去除第一個(gè)元素
this.Move()//遞歸
}
}
func (this *MyStack) Pop() int {
val:=this.queue1[0]
this.queue1 = this.queue1[1:]
return val
}
func (this *MyStack) Top() int {
return this.queue1[0]
}
func (this *MyStack) Empty() bool {
return len(this.queue1) == 0
}
type MyStack struct {
queue []int
}
func Constructor() MyStack {
return MyStack{
queue:make([]int,0),
}
}
func (this *MyStack) Push(x int) {
this.queue = append(this.queue,x)
}
func (this *MyStack) Pop() int {
n:=len(this.queue) -1
for n!=0{
//從隊(duì)列中獲取第一個(gè)元素（即棧頂元素），將其保存到變量 val 中
val:=this.queue[0]
//移除隊(duì)列中的第一個(gè)元素，即將隊(duì)列的切片重新賦值為從索引 1 開始到末尾的部分，這樣就移除了第一個(gè)元素。
this.queue = this.queue[1:]
//將剛才移除的元素重新追加到隊(duì)列的末尾。這個(gè)操作相當(dāng)于將元素從隊(duì)列的頭部移動(dòng)到尾部，實(shí)現(xiàn)了棧的出棧操作。
this.queue = append(this.queue,val)
//在每次循環(huán)結(jié)束時(shí)，將 n 的值減 1，以便逐步減少隊(duì)列中的元素?cái)?shù)量。
n--
}
//在循環(huán)結(jié)束后，隊(duì)列中只剩下最后一個(gè)元素，因此我們直接取出這個(gè)元素。
val:=this.queue[0]
//將隊(duì)列中的最后一個(gè)元素移除。
this.queue = this.queue[1:]
return val
}
func (this *MyStack) Top() int {
val:=this.Pop()
this.queue = append(this.queue,val)
return val
}
func (this *MyStack) Empty() bool {
return len(this.queue) == 0
}
浙公網(wǎng)安備 33010602011771號(hào)