重写数据结构--栈和队列

栈：

# include <iostream> # define SIZE 100 using namespace std; void error(const char* str) { cout << str << endl; return; } typedef struct stack { int array[SIZE]; int top_index; stack() { top_index = -1; } int top() { if (top_index < 0) { error("Underflow"); return -1; } else { return array[top_index]; } } void pop() { if (top_index < 0) { error("Underflow"); } else { top_index --; } } void push(int a) { if (top_index < SIZE - 1) { top_index ++; array[top_index] = a; return; } else { error("Full Stack"); } } }stack; int main() { }

队列：

跟同学讨论到一个问题，就是在c++里面（gcc 4.2.1）结构体和类的区别简单理解就在于类默认私有，结构体默认公有了； 说到这个是因为我在写队列的时候突然想到要用this,但是是用结构体写的，尝试编译了一下，竟然过了。

这里的队列是，head指向第一个元素的下一个索引； 所以队空：

bool isEmpty() { if (head == (tail + 1) % size) { return true; } return false; }

队满：

bool isFull() { if (head == tail) { return true; } return false; }

全部代码：

# include <iostream> # define SIZE 100 using namespace std; void error(const char* ch) { cout << ch << endl; } typedef struct queue { int array[SIZE]; int head; int tail; int size; queue(int n) { tail = 0; head = 1; size = n + 1; //注意这里保持语义的正确性，保证能够保存n个元素 } void EnQueue(int x) { if (! this->isFull()) { array[head] = x; head ++; head = head % size; } else{ error("Full"); } } void DeQueue() { if (! this->isEmpty()) { tail = tail + 1; tail = tail % size; } } bool isFull() { if (head == tail) { return true; } return false; } bool isEmpty() { if (head == (tail + 1) % size) { return true; } return false; } void print() { if (!this->isEmpty()) { int i = head - 1; do { i = (i + size) % size; cout << array[i] << " "; i--; } while( (i + size) % size != (tail + size) % size ); cout << endl; } else { error("Empty"); } } }queue; int main() { // queue q(8); // for (int i = 0; i < 10; i ++) { // q.EnQueue(i+1); // } // q.DeQueue(); // q.DeQueue(); // q.print(); }