栈

链表保证每次稳定快 数组保证总时长快

用链表实现

struct Node {
	string item;
	Node* next;
};

class Stack {
private:
	Node* first = NULL;
public:
	bool isEmpty() {
		return first == NULL;
	}

	void push(string item) {
		Node* oldfirst = first;
		first = new Node();
		first->next = oldfirst;
		first->item = item;
	}

	string pop() {
		string item = first->item;
		first = first->next;
		return item;
	}
};

用数组实现

固定大小

class Stack{
	private:
		int s[100];
		int N = 0;
	public:    
		bool isEmpty(){
			return N == 0;
		}
		
		void push(int x){
			s[N++] = x;
		}
		
		int pop(){
			return s[--N]; //注意这里
		}
};

数组长加倍/减倍

class Stack {
private:
	int* s = new int[1];
	int N = 0;
	int length = 1;
public:
	bool isEmpty() {
		return N == 0;
	}
	void resize(int capacity) {
		int* copy = new int[capacity];
		for (int i = 0; i < length; i++)
			copy[i] = s[i];
		s = copy;
	}

	void push(int x) {
		if (N == length) {
			resize(length * 2);
			length *= 2;
		}
		s[N++] = x;

	}

	//当数组变为1/4长时减半而不是1/2时 这样可以避免在半长左右反复增减元素导致重复复制元素
	int pop() {
		int item = s[--N];
		if (N > 0 && N == length / 4) {
			resize(length / 2);
			length /= 2;
		}
		return item;
	}

	int getLength() {
		return length;
	}

};