今天是day8，
题目一：使用栈实现队列
//先实现一个栈,给定int数组一个别名Mystack
type Mystack []int
//使用引用传递值，将v使用append追加至形参s中
func (s *Mystack) Push(v int){
*s = append(*s,v)
}
//使用val和切片获取*s的最后一个元素并调整*s为当前位置并将val返回出，从而实现了出栈
func (s *Mystack) Pop() int{
//
val := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return val
}
//返回最后一个元素
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
}
//如上先实现一个栈，声明两个数组一个in一个out
type MyQueue struct {
StackIn *Mystack
StackOut *Mystack
}
//使用结构体赋值并初始化两个数组为空
func Constructor() MyQueue {
return MyQueue{
StackIn: &Mystack{},
StackOut: &Mystack{},
}
}
//直接使用栈的push来推进元素
func (this *MyQueue) Push(x int) {
this.StackIn.Push(x)
}
//先填充out数组，再让out数组弹出
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数组
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):
"两个用来存放操作数值的数组"
self.stack_in = []
self.stack_out = []
"将元素压入队列中"
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
"先判空"
if self.empty():
return None
"这里一个递归"
if self.stack_out:
return self.stack_out.pop()
else:
"遍历已有的in数组并将out数组值不断压入"
for i in range(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
"返回队列头元素，即用ans来获取pop并将其压入out数组中此时的ans就是第一个"
def peek(self) -> int:
ans = self.pop()
self.stack_out.append(ans)
return ans
"判空即in数组和out数组都不存在"
def empty(self) -> bool:
return not (self.stack_in or self.stack_out)
题目二：用队列实现栈
from collections import deque
class MyStack:
def __init__(self):
"直接声明两个数组为deque即队列"
self.queue_in = deque()
self.queue_out = deque()
def push(self, x: int) -> None:
self.queue_in.append(x)
"先判空，如果不空，遍历整个in队列并将其左弹出后再压入out队列中"
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())
"此时交换in out队列值，最终返回out队列的左弹出值"
self.queue_in,self.queue_out = self.queue_out,self.queue_in
return self.queue_out.popleft()
"先判空，再遍历整个in队列，将其值左弹出后压入out队列中"
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队列的左弹出值并将其压入in队列中，最后返回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),
}
}
//先将所有元素存储在queue2中再调用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:]//去除第一个元素
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{
//从队列中获取第一个元素（即栈顶元素），将其保存到变量 val 中
val:=this.queue[0]
//移除队列中的第一个元素，即将队列的切片重新赋值为从索引 1 开始到末尾的部分，这样就移除了第一个元素。
this.queue = this.queue[1:]
//将刚才移除的元素重新追加到队列的末尾。这个操作相当于将元素从队列的头部移动到尾部，实现了栈的出栈操作。
this.queue = append(this.queue,val)
//在每次循环结束时，将 n 的值减 1，以便逐步减少队列中的元素数量。
n--
}
//在循环结束后，队列中只剩下最后一个元素，因此我们直接取出这个元素。
val:=this.queue[0]
//将队列中的最后一个元素移除。
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
}