[算法]模式识别-Stack

Author Avatar
与狼同行 11月 25, 2016

Stack

  1. 栈是一种数据结构,可以实现后进先出(LIFO),可以用栈辅助,实现深度优先算法。或者将递归转为while循环。
    事实上,递归本身相当于把函数一层一层加到操作系统内存栈上,利用栈数据结构去实现也非常自然。入栈操作对象相当于递归调用自身,出栈相当于递归返回。入栈操作的对象相当于需要被解决的问题。出栈对象相当于已经解决的子问题,通过共享的状态变量或返回值把子问题的结果传递出来。

  2. 队列,帮助实现先进先出(FIFO),可以用Queue做辅助,实现广度优先算法。

技巧:

  1. 通过栈实现特殊顺序地读取: 由于栈具有LIFO的特性,如需要实现任何特定顺序的读取操作,往往可以借助两个栈互相“倾倒”来实现特点顺序,事实上,很多情况下,栈并不是实现读取顺序地最佳选择,但最为面试,往往会很明确用栈实现。
    设计一个栈,带有push、pop、max方法,其时间复杂度为O1.
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
class stackWithMax{
public:
void push(int);
int pop();
int max();
private:
stack<int> valueStack;
stack<int> maxStack;
};
void stackWithMax::push(int value){
if (maxStack.empty() || maxStack.top() <= value) {
maxStack.push(value);
}
valueStack.push(value);
}
int stackWithMax::pop(){
int value = maxStack.top();
valueStack.pop();
if (value == maxStack.top()) {
maxStack.pop();
}
return value;
}
int stackWithMax::max(){
return maxStack.top();
}

题目:使用一个栈结构来实现一个队列

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
class Queue{
private:
stack<int>inputStack;
stack<int>outputStack;
public:
void enqueue(int);
int dequeue();
};
void Queue::enqueue(int value){
inputStack.push(value);
}
int Queue::dequeue(){
int value;
if (!outputStack.empty()) {
value = outputStack.top();
outputStack.pop();
return value;
}
while (!inputStack.empty()) {
outputStack.push(inputStack.top());
inputStack.pop();
}
value = outputStack.top();
outputStack.pop();
return value;
}

  1. “Save for later”,假如有一类问题有这样的特性,当前节点的解依赖于后面那个节点,这类问题可以用栈来解决。
    题目:给定一个字符串,它包含如下的字符,‘(’,‘)’,‘{’,‘}’,判断输入的字符串是否是一个有效的圆括号字符串,例如(([]))是有效的,而(和((不是
    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
    bool isLeftParentheses(char input){
    return input == '(' || input == '[' || input == '{';
    }
    bool isMatchParentheses(char left,char right){
    switch (left) {
    case '(':
    return right == ')';
    case '[':
    return right == ']';
    case '{':
    return right == '}';
    }
    return false;
    }
    bool isValidParentheses(string input){
    stack<char> pareStack;
    for (int i=0; i<input.length(); i++) {
    if (isLeftParentheses(input[i])) {
    pareStack.push(input[i]);
    }else{
    if (pareStack.empty()|| !isMatchParentheses(pareStack.top(), input[i])) {
    return false;
    }
    pareStack.pop();
    }
    }
    return pareStack.empty();
    }