Created
May 17, 2019 10:15
-
-
Save wsgac/940f83de173a8e166412bd9d41cfebb8 to your computer and use it in GitHub Desktop.
Simple queue implementation in C++ using templates
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| template <class T> | |
| class queue { | |
| T *buffer; | |
| int buf_size; | |
| int front_index; | |
| int back_index; | |
| int buf_grow_factor; | |
| void realloc() { | |
| T *tmp = new T[buf_size*buf_grow_factor]; | |
| int size = 0; | |
| if (front_index <= back_index) { | |
| for (int i = 0; i < buf_size; i++) | |
| tmp[size++] = buffer[i]; | |
| } else { | |
| for (int i = front_index; i < buf_size; i++) | |
| tmp[size++] = buffer[i]; | |
| for (int i = 0; i < back_index; i++) | |
| tmp[size++] = buffer[i]; | |
| } | |
| front_index = 0; | |
| back_index = buf_size; | |
| delete[] buffer; | |
| buffer = tmp; | |
| buf_size *= buf_grow_factor; | |
| } | |
| public: | |
| queue(int init_size, int grow_factor) { | |
| buf_grow_factor = grow_factor; | |
| buffer = new T[init_size]; | |
| buf_size = init_size; | |
| back_index = 0; | |
| front_index = 0; | |
| } | |
| ~queue() { | |
| delete[] buffer; | |
| } | |
| void push_back(T item) { | |
| buffer[back_index++] = item; | |
| if (back_index == buf_size) | |
| back_index = 0; | |
| if (back_index == front_index) | |
| realloc(); | |
| } | |
| void pop_front() { | |
| // Decrement back_index; if it turns negative, wrap around the end | |
| front_index++; | |
| if (front_index == buf_size) | |
| front_index = 0; | |
| } | |
| T front() { | |
| return buffer[front_index]; | |
| } | |
| int size() { | |
| if (front_index <= back_index) | |
| return back_index - front_index; | |
| return buf_size - (front_index - back_index); | |
| } | |
| bool empty() { | |
| return size() == 0; | |
| } | |
| }; | |
| int main() { | |
| queue<int> q(4, 2); | |
| for(int i = 0; i < 10; i++) | |
| q.push_back(i); | |
| while (!q.empty()) | |
| { | |
| cout << q.front() << endl; | |
| q.pop_front(); | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment