[C++随笔录] stack && queue使用

stack

栈的特点是 先进后出(first in last out)

我们可以看出, stack的接口相比 vector/string/list 的接口少的太多了

1. 构造函数 && 容器适配器
   

• 容器适配器的含义:
  首先, 适配器 — — 用户传数据进来, 我们用合适的容器来进行管理
  其次, 容器 — — 容器要符合类型的要求. 比如堆要求用下标来访问数据, 那么我们适配的容器就应该是vector, 而不应该是list
  总结下来就是, 容器适配器是 外壳用容器封装, 数据由容器来进行管理

2. 不支持下标访问数据, 不能进行遍历.
   只能通过不断的 pop 来进行访问数据

int main()
{
	stack<int> st;
	st.push(1);
	st.push(5);
	st.push(9);
	st.push(8);
	st.push(6);
	st.push(90);

	cout << "size->" << st.size() << endl;

	cout << "出数据->";
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果:

size->6
出数据->90 6 8 9 5 1
1
2

栈的知识也就这么多, 下面进入queue

queue

队列的特点是 先进先出 (first in first out)

跟stack很相似, 但是队列不仅有队头也有队尾, 而stack只有栈顶

1. 我们发现, queue也使用的是 容器适配器
2. 跟stack一样, 不支持下标访问数据, 不能进行遍历.
   只能通过不断的 pop 来进行访问数据

int main()
{
	queue<int> q;
	q.push(1);
	q.push(5);
	q.push(9);
	q.push(8);
	q.push(6);
	q.push(90);

	cout << "size->" << q.size() << endl;

	cout << "出数据->";
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果:

size->6
出数据->1 5 9 8 6 90
1
2

题目训练

1. 最小栈

首先, 先想到的是定义一个全局变量 min, 在每次push 和 pop的时候更新一下min, 然后返回min就行了.
这么做是真的没问题吗? 看一下下面的例子:
push: 6, 5, 4, 3, pop两次
此时当前栈的最小值应该是5, 但是按照我们的想法, min应该是3才对
上面的那个想法不能很好地控制栈空间的变化

其实, 我们可以用两个栈来做: 一个负责正常工作, 一个负责记录当前栈的最小值

解题代码:

class MinStack {
public:

    void push(int val) 
    {
        st.push(val);
        // min_st进数据: 1. 首元素, 2.进入数据的元素 <= min_st的栈顶元素
        if(min_st.size() == 0 || val <= min_st.top())
        {
            min_st.push(val);
        }
    }
    
    void pop() 
    {
        if(min_st.top() == st.top())
        {
            min_st.pop();
        }
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return min_st.top();
    }

private:
    stack<int> st;
    stack<int> min_st;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. 栈的压入, 弹出序列
   
   不绕弯子了: 本题属于 模拟题, 模拟压栈,出栈的顺序来做的. 由此需要一个辅助栈来进行, 最后判断辅助栈是否为空就知道答案了!

思路:

1. 不管什么, 先进栈 st
2. 再判断栈顶元素是否和出栈数组的当前值相同
   1. 不相同, 什么事情也不用做, 继续入栈
   2. 相同, st出栈, 出栈数组向前挪动数据, 直至和栈顶元素不相同
3. 结果: 看st是否为空
   1. 为空, 说明按照入栈, 出栈的顺序走了一遍, 说明逻辑是通的
   2. 不为空, 说明中间出现了问题, 说明逻辑是错误的

解题代码:

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
{
   stack<int> st; // 辅助栈
   int pushi = 0; // 控制入栈数组
   int popi = 0;  // 控制出栈数组

   // 当没数据可入了, 说明入栈结束
   while(pushi < pushV.size())
   {
       // 先入栈
       st.push(pushV[pushi]);
       pushi++;

       // 防止st栈为空
       while(st.size() && st.top() == popV[popi])
       {
           st.pop();
           popi++;
       }

   }

   return st.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

知而不行，只是未知。
语出明·王守仁《传习录》。学了知识，而不实践，这等于没有学到知识一样。