stl_stack_queue的使用及OJ题

stl_stack_queue的使用

#include 
#include 
#include 
using namespace std;

void test_stack()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);

	while (!st.empty())
	{
		cout << st.top() << endl;
		st.pop();
	}

}

void test_queue()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);

	while (!q.empty())
	{
		cout << q.front() << endl;
		q.pop();
	}

}

int main()
{
	test_stack();
	cout << endl;
	test_queue();

	return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47

相关OJ题

// stack 与 queue的 OJ题
//
T1. 最小栈
设计一个支持 push , pop , top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类：
  MinStack() 初始化堆栈对象。
  void push(int val) 将元素val推入堆栈
  void pop()  删除堆栈顶部的元素
  int top()  获取堆栈顶部的元素
  int getMin()  获取堆栈中的最小元素

class MinStack
{
public:
	MinStack() //当初始化列表为空时，自定义类型成员变量会去调用自身类的构造函数；而内置类型成员变量不做任何处理。
	{}

	void push(int val)
	{
		_st.push(val);

		if (_minst.empty() || val<=_minst.top()) 
			_minst.push(val);
	}

	void pop()
	{
		if (_minst.top()==_st.top())
			_minst.pop();

		_st.pop();
	}

	
	int top()
	{
		return _st.top();
	}

	int getMin()
	{
		return _minst.top();
	}

private:
	//用两个 stack 实现一个 MinStack 
	stack<int> _st;    //普通栈  
	stack<int> _minst; //最小栈  //用来记录数据的最小值
};




//T2.栈的压入、弹出序列 （栈 模拟这个过程）
//描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
// 假设压入栈的所有数字均不相等。例如序列 1，2，3，4，5 是某栈的压入顺序，序列 4，5，3，2，1 是该压栈序列对应的一个弹出序列，但 4，3，5，1，2
// 就不可能是该压栈序列的弹出序列。

class Solution
{
public:
	bool IsPopOrder(vector<int> pushV,vector<int> popV)
	{
		stack<int> st;
		int popi = 0;
		for (auto pushVal : pushV)
		{
			st.push(pushVal);

			//出栈序列匹配后要持续比较，可能会有多个匹配
			while (!st.empty() && popV[popi]==st.top())
			{
				++popi;
				st.pop();
			}
		}

		// return popi==popV.size();
		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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83