OJ刷題記錄：佇列的儲存結構與操作

佇列的順序儲存結構與操作 題目編號:460

題目要求：
請定義一個順序佇列，可以對佇列進行「入隊」、「出隊」、「清空佇列」、「獲取隊首元素」等操作。鍵盤輸入一些命令，可以執行上述操作。本題中，佇列的元素為字母， 佇列的最大元素個數為100。
輸入描述

輸入各個命令，它們對應的格式如下：

入隊：E a，a代表入隊的元素，這裡E和元素之間用空格分隔。

清空佇列：C

獲取隊頭元素：當輸入的命令為D時，輸出出隊的元素值；

當輸入的命令是G時，輸出當前隊首元素值；

如果沒有元素可出隊或可取,

輸出描述

當輸入的命令為D時，輸出出隊的元素值；

當輸入的命令是G時，輸出當前隊首元素值；

如果沒有元素可出隊或可取,請輸出None；

輸入樣例

E a
G
C
E b
D
D
Q

輸出樣例

a
b
None

解題思路：
每一次操作時需要對移動的陣列下標（head_ 或者 rear_）進行取模，以實現陣列的首尾迴圈，防止假溢位。

通關程式碼：

#include <iostream>

#define MaxSize 100

using namespace std;

class Queue {
	public:
		Queue();
		
	public:
		void Push(char ch);
		char Pop();
		void Clear();
		char getHead();
		
	private:
		char arr_[MaxSize];
		int head_;
		int rear_;
};

Queue::Queue() {
	head_ = 0;
	rear_ = 0;
}

void Queue::Push(char ch) {
	if ((rear_ + 1) % MaxSize == head_) throw "上溢";
	
	arr_[rear_] = ch;
	rear_ = (rear_ + 1) % MaxSize;
}

char Queue::Pop() {
	if (rear_ == head_) throw "None";
	
	char ch = arr_[head_]; 
	
	head_ = (head_ + 1) % MaxSize;
	
	return ch;
}

void Queue::Clear() {
	head_ = 0;
	rear_ = 0;
}

char Queue::getHead() {
	if (rear_ == head_) throw "None";
	
	return arr_[head_];
}

int main() {
	Queue q;	
	char val, key;

	while (cin >> key) {
		if (key == 'Q') break;
		
		try {
			switch (key) {
				case 'E':
					cin >> val;
					q.Push(val);
					break;

				case 'C':
					q.Clear();
					break;

				case 'G':
					cout << q.getHead() << endl;
					break;

				case 'D':
					cout << q.Pop() << endl;
					break;
			}
		} catch (const char* str) {
			cout << str << endl;
		}
	}
	
	return 0;
}

佇列的鏈式儲存結構與操作 題目編號:115

題目要求：
同上。

解題思路：
水。

通關程式碼：

#include <iostream>

using namespace std;

struct Node {
	char _val;
	Node* _next;
	Node(int val):_val(val), _next(NULL) {}
};

class Queue {
	public:
		Queue();
		~Queue();

	public:
		void Push(char ch);
		char Pop();
		void Clear();
		char getHead();

	private:
		Node* head_;
		Node* rear_;
};

Queue::Queue() {
	head_ = new Node(-1);
	rear_ = head_;
}

Queue::~Queue() {
	Node* afterHead = NULL;

	for (Node* p = head_; p != NULL; p = afterHead) {
		afterHead = p->_next;
		delete p;
	}
}

void Queue::Push(char ch) {
	Node* node = new Node(ch);

	rear_->_next = node;
	rear_ = node;
}

char Queue::Pop() {
	if (head_->_next == NULL) throw "None";
	
	Node* popedNode = head_->_next;

	char res = popedNode->_val;
	head_->_next = popedNode->_next;

	delete popedNode;

	return res;
}

void Queue::Clear() {
	Node* afterHead = NULL;

	for (Node* p = head_->_next; p != NULL; p = afterHead) {
		afterHead = p->_next;
		delete p;
	}
	
	head_->_next = NULL;
	rear_ = head_;
}

char Queue::getHead() {
	if (head_->_next == NULL) throw "None";
	
	return head_->_next->_val;
}

int main() {
	Queue q;
	char val, key;

	while (cin >> key) {
		if (key == 'Q') break;

		try {
			switch (key) {
				case 'E':
					cin >> val;
					q.Push(val);
					break;

				case 'C':
					q.Clear();
					break;

				case 'G':
					cout << q.getHead() << endl;
					break;

				case 'D':
					cout << q.Pop() << endl;
					break;
			}
		} catch (const char* str) {
			cout << str << endl;
		}
	}

	return 0;
}

畢。