2020-04-06 318c77d5de1c4b78f585a4ccedfe4a22 99+ 1 分钟 0.2 k 0次访问

剑指offer-使用两个栈实现队列，使用两个队列实现栈

一、使用两个栈实现队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。

二、分析

两个栈，s1作为存储空间，入队先压栈到s1，s2作为元素出栈缓冲区，元素出栈在s2。

入队时，将元素压入s1。
出队时，判断s2是否为空，如不为空，则直接弹出栈顶元素；如为空，则将s1的元素逐个压入s2，把最后一个元素弹出并出队。这种思路，避免了反复压栈到缓冲栈，仅在需要时才压入一次。

三、go语言实现

type Queue struct {
	in common.Stack
	out common.Stack
}

// 判空
func (que *Queue) IsEmpty() bool {
	return que.in.IsEmpty() && que.out.IsEmpty()
}

// 入队
func (que *Queue) Push(value interface{}) {
	qu.in.Push(value)
}

// 出队
func (que *Queue) Pop() (interface{}, error) {
	if que.IsEmpty() {
		return nil, errors.New("Queue is empty")
	}

	var value interface{}
	
	if !que.out.IsEmpty() {
		value, _ = que.out.Pop()
		return value, nil
	}

	for !que.in.IsEmpty() {
		value, _ = que.in.Pop()
		que.out.Push(value)
	}
	value, _ = que.out.Pop()
	
	return value, nil
}

四、使用两个队列实现栈

题目描述

用两个队列来实现一个栈，完成栈的Push压栈操作和Pop出栈操作。

五、分析

压栈时，将元素直接加入到一个不为空的一个队列中，如果都为空，任选一个即可。
出栈时，将不为空的队列除最后一个元素依次取出放入到另一个队列中，然后将最后一个元素出队即可。

六、go语言实现

type Stack struct {
	in Queue
	out Queue
}

// 入栈
func (s *Stack) Push(value interface{}) {
	if s.in.IsEmpty() == false {
		s.in.Push(value)
	} else {
		s.out.Push(value)
	}
}

// 出栈
func (s *Stack) Pop() (interface{}, error) {
	if s.in.IsEmpty() == false {
		inlen := s.in.Size()
		var val interface{}
		for i := 0; i < inlen; i++ {
			val, _ = s.in.Pop()
			if i == inlen-1 {
				return val, nil
			} else {
				s.out.Push(val)
			}
		}
	} else if s.out.IsEmpty() == false {
		outlen := s.out.Size()
		var val interface{}
		for i := 0; i < outlen; i++ {
			val, _ = s.out.Pop()
			if i == outlen-1 {
				return val, nil
			} else {
				s.in.Push(val)
			}
		}
	}
	return nil, nil
}