STL

栈

Posted by Liao on 2019-11-29

栈的基本操作:

stack s;

s.push(item) //入栈

s.top() 返回栈顶元素

s.pop()删除栈顶元素

s.size() //返回栈中元素个数

s.empty()检查栈是否为空，为空返回true，否则返回false

新生赛题目

输入一个字符串，通过处理能使字符串中两个相邻且相同的字符互相消除，得到新的字符串，然后继续对新字符串消除，知道没有相同的字符。

input: abbaca

output: ca

可以通过栈来解决的字符串题目

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
#include <iostream>
#include <stack>

using namespace std;
int main()
{
  stack<char> st;
  string s;
  getline(cin,s);
  int len = s.size();

  for(int i=len-1;i>=0;i--)
  {
        if(!st.empty() && st.top() == s[i])
        {
            st.pop();
        }
        else
        {
            st.push(s[i]);
        }
  }
    while(!st.empty())
    {
        cout << st.top();
        st.pop();
    }
  return 0;
}


LeetCode 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
空字符串可被认为是有效字符串。

该题目只需要用栈便能解决，类似于实现编译器

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
#include <iostream>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <cstring>
using namespace std;

bool isValid(string s)
{
    stack <char> st;
    char match;
    for(int i = 0;i < s.size(); i++)
    {
        if(s[i] == '(' || s[i] == '{' || s[i] =='[')
            st.push(s[i]);
        else
        {
           if(st.size() == 0)  //判断栈是否有元素完成剩下字符的匹配，避免了{()]]这些情况
                return false;
            char c = st.top();
            st.pop();
            if(s[i] == ')')
                match = '(';
            if(s[i] == ']')
                match = '[';
            if(s[i] == '}')
                match = '{';

            if(c != match)
                return false;
        }
    }
    if(st.size() != 0) // for循环结束后（即没有后续的匹配了），判断栈是否为空，防止{()这些情况
        return false;
    return true;

}
int main()
{
    string s;
    cin >> s;
    if(isValid(s))
    {
        cout << "true" <<endl;
    }
    else
        cout << "false" <<endl;
	return 0;
}

LeetCode用栈实现队列

  • 根据栈先进后出的特点，通过两个栈，模拟队列的push(),pop(),peak(),empty()操作。

  • 栈st2时用来模拟队列的。

  • 进行push()操作时只需要放进st1就好，先不用放进st2。等到pop()、top()等操作时才把st1的所有元素放到st2。

  • 注意只有st2为空才能直接push进st1。否则要把st2的所有元素放回st1，再把新元素push进st1。

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
/** Initialize your data structure here. */
stack<int>st1;
stack<int>st2;
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
    if(st2.empty())
    {
        st1.push(x);
    }
    else
    {
        while(!st2.empty())
        {
            st1.push(st2.top());
            st2.pop();
        }
        st1.push(x);
    }
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
    while(!st1.empty())
    {
        st2.push(st1.top());
        st1.pop();
    }
    int popElement = st2.top();
    st2.pop();
    return popElement;
}

/** Get the front element. */
int peek() {
    while(!st1.empty())
    {
        st2.push(st1.top());
        st1.pop();
    }
    return st2.top();
}

/** Returns whether the queue is empty. */
bool empty() {
    if(st1.empty() && st2.empty())
        return true;
    else 
        return false;
}

​

​ 最后编辑于2020/03/01

FEATURED TAGS
STL
FRIENDS