C++ 手撕--基本数据结构的简单实现

C++面试手撕代码----基本数据结构的简单实现

1. String 数据结构的简单实现：

#include <iostream>
#include <cstring> // for strcpy strlen methods

using namespace std;

class String {
private:
	char* data;
	size_t length;
public:
	String() : data(nullptr), length(0){}

	String(const char* str){ // parameter constructor function
        if (str){
            length = strlen(str);
            data = new char[length + 1];
            strcpy(data, str);
        }
        else {
            data = nullptr;
            length = 0;
        }
    }

	String(const String& other){ // copy constructor function
        length = other.length;
        if (length > 0){
            data = new char[length + 1];
            strcpy(data, other);
        }
        else{
            data = nullptr;
        }
    }

	String(String&& other) onexcept : length(other.length), data(other.data) { // move constructor function
        other.length = 0;
        other.data = nullptr;
    }

	~String(){    // release resource by deconstructor function
        delete[] data;
    }

	size_t get_size() const { // outside API for get size of String
        return length;
    }

	void printStr() const { // for print String
        if (data){
            cout << data << endl;
        }
        else {
            cout << "Empty String" << endl;
        }
    }
};

2. Vector数据结构的简单实现：

#include <iostream>
#include <stdexcept>

using namespace std;

class Vector {
private:
	size_t size; // current size of vector
	size_t capacity; // max capacity
	int *arr; // dynamic array
	
	void resize(){ // expand capacity if current capacity not enough
		capacity *= 2;
		int* newArr = new int[capacity];
		for (size_t i = 0; i < size; ++i){
			newArr[i] = arr[i];
		}
		arr = newArr;
	}
public:
	Vector() : size(0), capacity(2){
		arr = new int[capacity];
	}
	
	Vector(const Vector& other) : size(other.size), capacity(other.capacity) { // copy constructor function
		arr = new int[capacity];
		for (size_t i = 0; i < size; ++i){
			arr[i] = other.arr[i];
		}
	}
	int& operator[](int index){ // override operator [] for get i-th data;
		if (index < 0 || index >= size){
			throw std::out_of_range("Index out of range");
		}
		return arr[index];
	}
	const int& operator[](int index) const {
		if (index < 0 || index >= size){
			throw std::out_of_range("Index out of range");
		}
		return arr[index];
	}
	Vector& operator=(const Vector& other){ // override operator = to copy vector;
		if (this == &other){
			return *this;
		}
		delete[] arr;
		size = other.size;
		capacity = other.capacity;
		arr = new int[capacity];
		
		for (size_t i = 0; i < size; ++i){
			arr[i] = other.arr[i];
		}
		return *this;
	}
	
	~Vector() {
		delete[] arr;
	}
	
	void push_back(const int value) { // push element to back of vector
		if (size >= capacity){
			resize();
		}
		arr[size++] = value;
	}
	void pop_back(){  // pop back element of vector;
		if (size == 0){
			throw std::out_of_range("Vector is empty");
		}
		--size;
	}
	
	size_t size() const {
		return size;
	}
	
	size_t capacity() const {
		return capacity;
	}
};

3. 基于Stack实现Queue数据结构：

#include <iostream>
#include <stdexcept>
#include <stack>

using namespace std;

class Queue {
private:
	stack<int> inputStack;
	stack<int> outputStack;
	
public:
	Queue() {}
	~Queue() {}
	
	void push(int value) {
		inputStack.push(value);
	}
	
	int pop() {
		if (outputStack.empty()){
			while(!inputStack.empty()){
				outputStack.push(inputStack.top());
				inputStack.pop();
			}
		}
		if (outputStack.empty()){
			throw std::out_of_range("Queue is empty");
		}
		int pop_v = outputStack.top();
		outputStack.pop();
		return pop_v;
	}
	
	int front() {
		if (outputStack.empty()){
			while(!inputStack.empty()){
				outputStack.push(inputStack.top());
				inputStack.pop();
			}
		}
		if (outputStack.empty()){
			throw std::out_of_range("Queue is empty");
		}
		return outputStack.top();
	}
	
	bool empty() const {
		return inputStack.empty() && outputStack.empty();
	}
	
}

4.基于Queue实现Stack：

#include <iostream>
#include <stdexcept>
#include <queue>

using namespace std;

class Stack {
private:
	queue<int> inputQueue;
	queue<int> auxiQueue;
	
public:
	Stack() {}
	~Stack() {}
	
	void push(int value) {
		inputQueue.push(value);
	}
	
	int pop() {
		if (inputQueue.size() == 0) {
			throw std::out_of_range("Stack is empty");
		}
		while (inputQueue.size() > 1){
			auxiQueue.push(inputQueue.front());
			inputQueue.pop();
		}
		int pop_v = inputQueue.front();
		inputQueue.pop();
		std::swap(inputQueue, auxiQueue);
		return pop_v
	}
	
	int top() {
		if (inputQueue.size() == 0) {
			throw std::out_of_range("Stack is empty");
		}
		while (inputQueue.size() > 1){
			auxiQueue.push(inputQueue.front());
			inputQueue.pop();
		}
		int pop_v = inputQueue.front();
		inputQueue.pop();
		auxiQueue.push(pop_v);
		
		std::swap(inputQueue, auxiQueue);
		
		return pop_v;
	}
	
	bool empty() const {
		return inputQueue.empty();
	}
}