栈---后入先出( LIFO )的数据结构

与队列不同，栈是一个 LIFO 数据结构，将首先处理添加到栈中的最新元素。通常，插入操作在栈中被称作入栈 push 。与队列类似，总在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

为方便理解，下面我

用golang中的切片（slice）实现基本栈

要求：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

type MyStack struct {
	data	[]int
}

// 构造函数
func Constructor() MyStack {
	return MyStack{
		data: []int{},
	}
}

// 向栈内添加元素
func (m *MyStack) Push(x int)  {
	m.data = append(m.data, x)
}

// 删除栈顶元素，若栈为空，返回-1
func (m *MyStack) Pop() int {
	if m.Empty() {
		return -1
	}
	dataLen := m.data[len(m.data)-1]
	m.data = m.data[:len(m.data)-1]
	return dataLen
}

// 得到栈顶元素
func (m *MyStack) Top() int {
	if m.Empty() {
		return -1
	}
	return m.data[len(m.data)-1]
}

// 判断栈是否为空
func (m *MyStack) Empty() bool {
	return len(m.data) == 0
}


/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

大多数流行的语言都提供了内置的栈库（如golang中切片），因此我们不必重新发明轮子。除了初始化，我们还需要知道如何使用两个最重要的操作：入栈和退栈。除此之外，我们应该能够从栈中获得顶部元素，详细代码见上例。

下面进行几个栈的实例进行进一步学习

1. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。 --- 重点考察

import "math"

/*
采用辅助栈的方法，即新建一个栈作为辅助栈，始终使其栈顶等于主栈的最小元素（主栈每添加一个新元素，便与辅助栈栈顶元素比较并添加一次），这样直接返回辅助栈栈顶元素即可。
 */

type MinStack struct {
	data    []int
	minData []int
}

// 构造函数
func Constructor() MinStack {
	return MinStack{
		data: []int{},
		// 第一次提取辅助栈栈顶元素时，令辅助栈不为空
		minData: []int{math.MaxInt64},
	}
}

// 元素入栈，同时令辅助栈栈顶始终为最小元素
func (m *MinStack) Push(x int) {
	m.data = append(m.data, x)
	top := m.minData[len(m.minData)-1]
	m.minData = append(m.minData, min(x, top))
}

// 移除栈顶元素，同时辅助栈栈顶元素出栈
// 此处需注意，辅助栈的元素始终和主栈的元素数量相同
func (m *MinStack) Pop() {
	m.data = m.data[:len(m.data)-1]
	m.minData = m.minData[:len(m.minData)-1]
}

// 返回主栈栈顶元素
func (m *MinStack) Top() int {
	return m.data[len(m.data)-1]
}

// 返回栈中最小元素，即返回辅助栈栈顶元素
func (m *MinStack) GetMin() int {
	return m.minData[len(m.minData)-1]
}

// 比较函数，返回较小值或相等值
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

2. 有效的括号

给定一个只包括 ‘(‘，‘)‘，‘{‘，‘}‘，‘[‘，‘]‘ 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

/*
1. 定义一个映射，并初始化栈。
2. 依次处理字符串中的每个括号。
3. 如果遇到左括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。
4. 如果我们遇到一个右括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，则删除栈顶元素。否则，这意味着表达式无效。
5. 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。
 */

func isValid(s string) bool {
   // 定义一个映射
   hash := map[byte]byte{
      ‘)‘:‘(‘,
      ‘]‘:‘[‘,
      ‘}‘:‘{‘,
   }
   // byte切片作为栈
   data := make([]byte, 0)
   // 如果字符串为空，返回true
   if s == "" {
      return true
   }

   // 遍历字符串
   for i := 0; i < len(s); i++ {

      if s[i] == ‘(‘ || s[i] == ‘[‘ || s[i] == ‘{‘ {
         data = append(data, s[i])   // 左括号入栈
      } else if len(data) > 0 && data[len(data)-1] == hash[s[i]] { // 右括号类型匹配栈顶元素
         data = data[:len(data)-1]  // 匹配成功则删除栈顶元素，即循环结束后如果完全匹配，则栈一定为空
      } else {
         return false // 其他情况直接返回false
      }
   }
   return len(data) == 0 // 栈为空则返回true
}

3. 每日温度

根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用0来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

**提示： **气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

方法一：双重循环

/*
在用栈解决这个问题之前，先用一个比较容易想到的方法暴力破解
双重循环
 */
func dailyTemperatures(T []int) []int {
	data := make([]int, 0)
	for i := 0; i < len(T)-1; i++ {
		for j := i + 1; j < len(T); j++ {
			if T[j] > T[i] {
				data = append(data, j-i) // 相隔天数
				break
			}
		}
		if len(data) != i+1 { // 如果天数不相等，说明后续温度没能超过本日温度，返回0
			data = append(data, 0)
		}
	}
	data = append(data, 0) // 最后一天一定为0
	return data
}

方法二：利用堆栈

画图理解比较迅速，相对方法一 时间快了许多

/*
遍历数组T，令当前最大的数（最高温度）入栈，判断栈顶温度与当前温度（所遍历到的温度）大小，
若栈顶温度>当前温度，栈顶出栈，循环此过程。
 */

type Stack struct {
   val   int
   index int
}

func dailyTemperatures(T []int) []int {
   // 栈的每个元素都包含 温度值 和 日期索引，开始栈为空
   tempStack := make([]Stack, 0)
   // 要返回的栈
   day := make([]int, len(T))

   // 遍历数组：i日期，v当日温度
   for i, v := range T {
       
       // 栈不为空时，如果 当日温度v > 栈顶温度，将间隔天数（当前日期-栈顶日期）入day栈，同时tempStack栈顶出栈
      // 循环上述过程，直至当日温度 <= 栈顶温度时跳出（此时已将所需日期索引入day栈）或者栈为空
      for len(tempStack) > 0 {
         if v > tempStack[len(tempStack)-1].val {
            day[tempStack[len(tempStack)-1].index] = i - tempStack[len(tempStack)-1].index

            tempStack = tempStack[:len(tempStack)-1]
         } else {
            break
         }
      }
       
      tempStack = append(tempStack, Stack{v, i}) // 将 当日温度 和 日期索引 入栈，以待下次循环进行比较
   }
   return day

栈和深度优先搜索

待续

数据结构-栈

原文：https://www.cnblogs.com/newbase/p/12906514.html