STL

队列基本用法

Posted by Liao on 2019-07-24

牛客上做的一个题目：https://ac.nowcoder.com/acm/contest/258/A

以样例为例：

1
2
3
4
5
6
输入
3 7
1 2 1 5 4 4 1

输出 
5

容量为3，文章长度为7，第二行为文章内容。依题意，检索到相同的就为同一个单词，当单词数量大于容量的时候，软件会清空最早存入内存的单词，腾出单元，存放新单词。因此符合队列先进先出的特点。

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
include <iostream>
include <algorithm>
include <queue>

using namespace std;
bool st[1000];
int main()
{
	queue<int> q;
	int m,n,x;
	int res = 0;
	cin >> m >> n;
	while(n--)
	{
		cin >> x;
		if(!st[x])  //还没输入过该单词 
		{
			res++;
			if(q.size()==m)
			{
				st[q.front()]=false;  //把队列第一个元素的引用置位false，表示还没有放入
				q.pop(); //把队列的第一个元素删除 
			} 
			st[x] = true;  //输入过该单词，置位true 
			q.push(x); //把单词x存入加入队列 
		}
	}
	cout << res << endl;
	return 0; 
}

LeetCode 用队列实现栈

用一个队列即可实现。每次push一个元素进来时，就把队中最前面的元素push到队尾，再删除队首元素，

直到最后一个元素变为队首元素为止。通过len记录着队列元素需要重新把队首push多少次回队尾。

例如放入1,2,3,4（栈回输出4,3,2,1）

队列长度len<=1，故继续放入元素

这时len=2 > 1，则要把队首元素重新push进队尾，并把去掉队首，len–,len=1

8

len=1不用处理，又可以继续添加元素了，于是加入3。这时len=3

2

则把队首push进队尾，len– len=2

4

len!=1，还是要继续处理，继续push队首元素。len– len=1

6

如此类推，加入4，结果如下图：

3

于是出队结果为4,3,2,1，正是出栈顺序。

pop()、top()和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
/** Initialize your data structure here. */
  queue<int> que;
  MyStack() {

  }
  
  /** Push element x onto stack. */
  void push(int x) {
      que.push(x);
      int len = que.size();
      while(len > 1)
      {
          que.push(que.front());  //每次push一个元素都放到队尾
          que.pop();
          len--;
      }
  }
  
  /** Removes the element on top of the stack and returns that element. */
  int pop() {
      if(que.empty())
          return -1;
      int temp = que.front();
      que.pop();
      return temp;
  }
  
  /** Get the top element. */
  int top() {
      return que.front();
  }
  
  /** Returns whether the stack is empty. */
  bool empty() {
      if(que.empty())
          return true;
      else
          return false;
  }
FEATURED TAGS
STL
FRIENDS