Go 언어에는 대기열과 스택 구조가 있나요?

Go 언어에는 큐 및 스택과 관련된 데이터 구조가 없지만 슬라이스를 사용하여 스택 및 큐 작업을 구현할 수 있습니다. Go 언어는 주로 추가 및 슬라이싱(내장 배열 유형으로 작동)을 사용하여 스택과 큐를 구현합니다. 스택과 큐를 생성하는 구문은 "make([]int, 0)"이고 스택과 큐에 푸시하는 구문은 다음과 같습니다. "append(stack, 10)", 스택을 팝하는 구문은 "v:=stack[len(stack)-1] stack = stack[:len(stack)-1]"입니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, GO 버전 1.18, Dell G3 컴퓨터.

Go 언어에는 스택 및 큐와 관련된 데이터 구조가 없지만 슬라이싱을 사용하여 스택 및 큐 작업을 구현할 수 있습니다. 다음으로 스택 및 큐의 기본 작업을 구현하고 도 구현합니다. use 스택은 대기열 을 구현하고 대기열을 사용하여 스택 작업 을 구현합니다.

스택과 큐의 기본 연산 구현

1. 스택의 기본 연산

Go 언어는 주로 추가 및 슬라이스(내장 배열 유형으로 작동)를 사용하여 스택과 큐를 구현합니다

//创建栈
stack := make([]int, 0)
//push压入栈
stack = append(stack, 10)
//pop弹出
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
//检查栈空
len(stack) == 0

2. 대기열의 기본 작업

//创建队列
queue := make([]int, 0)
//enqueue入队
queue = append(queue, 10)
//dequeue出队
v := queue[0]
queue = queue[1:]
//检查队列为空
len(queue) == 0

스택을 사용하여 대기열 구현

1. 이론

스택을 사용하여 대기열의 동작을 모델링하면 확실히 작동하지 않으므로 두 개가 필요합니다. 스택, 하나의 입력 스택 및 하나의 출력 스택, 여기서는 입력 스택과 출력 스택 간의 관계에 주의해야 합니다.

아래 애니메이션은 다음 대기열의 실행 프로세스를 다음과 같이 시뮬레이션합니다.

실행 문:

queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

데이터를 푸시할 때 데이터가 입력 스택에 들어 있는 한, 팝할 때는 작업이 더 복잡합니다. 출력 스택이 비어 있으면 모든 푸시 데이터를 스택으로 가져온 다음(모든 데이터를 가져옵니다) 팝 스택에서 데이터를 팝합니다. 출력 스택이 비어 있지 않으면 데이터를 팝하면 됩니다. 팝 스택에서 직접.

결국 대기열이 비어 있는지 확인하는 방법은 무엇입니까? push와 pop이 모두 비어 있으면 시뮬레이션된 큐가 비어 있음을 의미합니다.

2. 알고리즘 질문

원래 LeetCode 질문을 살펴보겠습니다

232. 스택을 사용하여 대기열을 구현합니다.

선입선출 대기열을 구현하려면 두 개의 스택만 사용하세요. 대기열은 일반 대기열에서 지원하는 모든 작업(push, pop, peek,empty)을 지원해야 합니다.

MyQueue 클래스 구현:

void push(int x) 요소 x를 대기열 끝에 푸시합니다. int pop()은 대기열의 시작 부분에서 요소를 제거하고 반환합니다. int peek()는 대기열의 시작 부분에 있는 요소를 반환합니다. booleanempty()는 대기열이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 참고:

표준 스택 작업만 사용할 수 있습니다. 즉, 위로 밀어넣기, 위에서 살짝보기/팝, 크기 및 비어 있음 작업만 허용됩니다. 사용 중인 언어가 스택을 지원하지 않을 수 있습니다. 표준 스택 작업인 경우 목록이나 deque(양단 큐)를 사용하여 스택을 시뮬레이션할 수 있습니다.

3. 아이디어

이 문제를 해결하려면 출력 스택과 입력 스택이 필요합니다

먼저 데이터를 입력 스택에 넣은 다음 입력 스택의 데이터를 출력 스택에 넣습니다. 시간, 출력 스택의 출력 데이터 순서는 대기열과 동일합니다. 선입선출

4. 코드 부분

type MyQueue struct {
	stackIn  []int // 用来保存Push数据
	stackOut []int // 用来保存Pop数据
}

// 栈构造器
func Constructor() MyQueue {
	return MyQueue{
		stackIn:  make([]int, 0),
		stackOut: make([]int, 0),
	}
}

func (this *MyQueue) Push(x int) {
	// 判断stackOut中是否有元素，有的话全部放到stackIn
	for len(this.stackOut) != 0 {
		val := this.stackOut[len(this.stackOut)-1]
		this.stackOut = this.stackOut[:len(this.stackOut)-1]
		this.stackIn = append(this.stackIn, val)
	}
	// 将数据加进stackIn
	this.stackIn = append(this.stackIn, x)
}

func (this *MyQueue) Pop() int {
	// 判断stackIn中是否有元素，有的话全部放到stackOut
	for len(this.stackIn) != 0 {
		val := this.stackIn[len(this.stackIn)-1]
		this.stackIn = this.stackIn[:len(this.stackIn)-1]
		this.stackOut = append(this.stackOut, val)
	}
	// stackOut为零，说明没有元素，return 0
	if len(this.stackOut) == 0 {
		return 0
	}
	// stackOut Pop 元素
	res := this.stackOut[len(this.stackOut)-1]
	this.stackOut = this.stackOut[:len(this.stackOut)-1]
	return res
}

func (this *MyQueue) Peek() int {
	// 调用Pop()方法
	val := this.Pop()
	// val为零，说明没有元素，return 0
	if val == 0 {
		return 0
	}
	// Pop()方法删除了val，这里加上
	this.stackOut = append(this.stackOut, val)
	return val
}

func (this *MyQueue) Empty() bool {
	// 两个栈都为空，说明为空，否则不为空
	return len(this.stackOut) == 0 && len(this.stackIn) == 0
}

코드는 Likou에서 직접 실행할 수 있습니다. 자세한 내용은 댓글로 모두 설명했습니다. 이해가 안 되시면 블로거에게 비공개 메시지를 보내셔도 됩니다.

큐를 사용하여 스택 구현

1. 이론

큐는 실제로 하나의 큐로 충분하므로 먼저 스택을 구현하는 두 개의 큐에 대해 이야기해 보겠습니다.

큐는 선입선출 규칙입니다. 한 큐의 데이터를 다른 큐로 가져올 때 데이터의 순서는 변경되지 않으며 선입선출 순서가 되지 않습니다.

그래서 스택을 사용하여 큐를 구현하는 아이디어는 이 두 데이터 구조의 특성에 따라 큐를 사용하여 스택을 구현하는 것과 다릅니다.

하지만 스택을 시뮬레이션하려면 여전히 두 개의 대기열을 사용해야 하지만 입력과 출력 사이에는 관계가 없지만 다른 대기열은 완전히 백업에 사용됩니다!

아래 애니메이션에서 볼 수 있듯이 큐 기능을 구현하기 위해 두 개의 큐 que1과 que2가 사용됩니다. que2는 실제로 que1의 마지막 요소를 제외한 모든 요소를 ​​que2에 백업한 다음 마지막 요소를 팝업하는 기능입니다. 그런 다음 que2의 다른 요소를 다시 que1로 가져옵니다.

시뮬레이트된 대기열 실행 문은 다음과 같습니다.

queue.push(1);        
queue.push(2);        
queue.pop();   // 注意弹出的操作       
queue.push(3);        
queue.push(4);       
queue.pop();  // 注意弹出的操作    
queue.pop();    
queue.pop();    
queue.empty();

2. 알고리즘 질문 ​​

다음으로 원래 LeetCode 질문 225을 살펴보겠습니다.

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

3、思路

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

4、使用两个队列实现

type MyStack struct {
    //创建两个队列
    queue1 []int
    queue2 []int
}


func Constructor() MyStack {
    return MyStack{	//初始化
        queue1:make([]int,0),
        queue2:make([]int,0),
    }
}


func (this *MyStack) Push(x int)  {
     //先将数据存在queue2中
    this.queue2 = append(this.queue2,x)	
   //将queue1中所有元素移到queue2中，再将两个队列进行交换
    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
}

5、优化

其实这道题目就是用一个队列就够了。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

6、使用一个队列实现

type MyStack struct {
    queue []int//创建一个队列
}


/** Initialize your data structure here. */
func Constructor() MyStack {
    return MyStack{   //初始化
        queue:make([]int,0),
    }
}


/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    //添加元素
    this.queue=append(this.queue,x)
}


/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    n:=len(this.queue)-1//判断长度
    for n!=0{ //除了最后一个，其余的都重新添加到队列里
        val:=this.queue[0]
        this.queue=this.queue[1:]
        this.queue=append(this.queue,val)
        n--
    }
    //弹出元素
    val:=this.queue[0]
    this.queue=this.queue[1:]
    return val
    
}


/** Get the top element. */
func (this *MyStack) Top() int {
    //利用Pop函数，弹出来的元素重新添加
    val:=this.Pop()
    this.queue=append(this.queue,val)
    return val
}


/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    return len(this.queue)==0
}

【相关推荐：Go视频教程、编程教学】

위 내용은 Go 언어에는 대기열과 스택 구조가 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!