Leetcode-栈的压入弹出序列

/*
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。



*/


#include <iostream>
#include <vector>

using namespace std;

class Stack{
private:
	int top_loci;
	int size;
	int capacity;
	int *data;
public:
	Stack(int init_size=100);
	~Stack();

	void push(const int val);
	void pop();
	int top();
	bool empty();
	bool full();
	void allocate();

};

Stack::Stack(int init_size){
	top_loci = 0;
	capacity = init_size;
	size = 0;
	data = new int[init_size];
}

Stack::~Stack(){
	delete [] data;
	data = nullptr;
	capacity = 0;
	size = 0;
	top_loci = 0;
}

void Stack::push(const int val){
	if(full()){
		allocate();
	}

	size++;
	data[top_loci++] = val;
}

void Stack::pop(){
	if(empty())
		std::cerr<<"stack empty,cant pop"<<endl;
	size--;
	top_loci--;
}

int Stack::top(){
	if(empty())
		std::cerr<<"stack empty, cant top"<<endl;
	return data[top_loci-1];
}

void Stack::allocate(){
	int *tmp = new int[2*capacity];
	for(int i=0;i<size;i++)
		tmp[i] = data[i];
	capacity = 2*capacity;
	delete []data;
	data = tmp;
	
}

bool Stack::empty(){
	return size == 0;
}

bool Stack::full(){
	return size==capacity;
}



class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    	if(pushed.empty() || popped.empty())
    		return false;

    	Stack s(2);
    	int popped_ptr = 0;
    	int pushed_ptr = 0;
    	
    	int curr_top_val;
    	while(pushed_ptr<pushed.size()){
    		if( !s.empty() && s.top()==popped[popped_ptr]){
    			popped_ptr++;
    			s.pop();
    		}else{
    			s.push(pushed[pushed_ptr++]);
    		}
    	}

    	while(!s.empty()){
    		if(s.top()==popped[popped_ptr++])
    			s.pop();
    		else
    			break;
    	}

    	//cout<<popped_ptr<<"==";
    	return popped_ptr==popped.size();
    }
};

int main(int argc, char const *argv[])
{
	Solution solu;
	
	vector<int> pushed1 = {1,2,3,4,5};
	vector<int> poped1 = {4,5,3,2,1};
	
	vector<int> pushed2 = {1,2,3,4,5};
	vector<int> poped2 = {4,3,5,1,2};

	cout<<solu.validateStackSequences(pushed1,poped1)<<endl;
	cout<<solu.validateStackSequences(pushed2,poped2)<<endl;

	return 0;
}

Leetcode-栈的压入弹出序列

原文：https://www.cnblogs.com/zhouyc/p/13574954.html