2020考研-王道数据结构-栈和队列-队列

た入场券 2022-01-30 09:23 276阅读 0赞

# 第一题 #

##### 题目简述 #####

实现一个循环队列，能充分利用空间内的元素。

##### 代码 #####

#include <iostream>
    #include <algorithm>
    #include <ctime>
    
    using namespace std;
    
    #define MAXSIZE 10
    typedef int Elemtype;
    
    class Queue{
        
    private:
    	Elemtype data[MAXSIZE];
    	int tag[2];
    public:
    	// 0域表示front、1域表示back
    	Queue(){
         tag[0] = 0, tag[1] = 0; }
    	void push(Elemtype e);
    	int pop();
    	bool isEmpty(){
         return tag[0] == tag[1]; };
    };
    
    void Queue::push(Elemtype e){
        
    	if ((tag[1] + 1) % MAXSIZE == tag[0]){
        
    		cerr << "队列满!" << endl;
    		return;
    	}
    	data[tag[1]] = e;
    	tag[1] = (tag[1] + 1) % MAXSIZE;
    	return;
    }
    
    int Queue::pop(){
        
    	if (tag[0] == tag[1]) {
        
    		cerr << "队列空!" << endl;
    		return -1;
    	}
    	int x = data[tag[0]];
    	tag[0] = (tag[0] + 1) % MAXSIZE;
    	return x;
    }
    
    int main()
    {
        
    	Queue que;
    	srand(time(0));
    	for (int i = 0; i < 12; i++){
        
    		int x = rand() % 10;
    		que.push(x);
    		cout << x << " ";
    	}
    
    	cout << endl;
    	while (!que.isEmpty()){
        
    		cout << que.pop() << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

# 第二题 #

##### 题目简述 #####

Q是一个队列，S是一个空栈，利用S实现将Q中的元素逆置。

##### 代码 #####

#include <iostream>
    #include <queue>
    #include <stack>
    
    using namespace std;
    
    void reverseQueue(queue<int> &que)
    {
        
    	stack<int> stk;
    	while (que.size()) {
        
    		stk.push(que.front());
    		que.pop();
    	}
    	while (stk.size()){
        
    		que.push(stk.top());
    		stk.pop();
    	}
    }
    
    int main()
    {
        
    	queue<int> que;
    	que.push(1);
    	que.push(2);
    	que.push(3);
    	que.push(5);
    	que.push(4);
    	reverseQueue(que);
    	while (que.size())
    	{
        
    		cout << que.front() << " ";
    		que.pop();
    	}
    	cout << endl;
    	return 0;
    }

# 第三题 #

##### 题目简述 #####

利用两个栈，实现一个队列。

##### 代码 #####

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    typedef int Elemtype;
    
    class Queue
    {
        
    private:
    	stack<Elemtype> stk1, stk2;
    public:
    	void EnQueue(Elemtype x);
    	Elemtype Dequeue();
    	bool QueueEmpty(){
         return stk1.empty() && stk2.empty(); };
    };
    
    void Queue::EnQueue(Elemtype e){
        
    	// TODO 这个位置应该有判满操作，因为使用的是stl中的nb栈，所以跳过
    	stk1.push(e);
    }
    
    Elemtype Queue::Dequeue(){
        
    	if (stk1.empty() && stk2.empty()){
        
    		cerr << "队列为空" << endl;
    		return -1;
    	}
    	Elemtype res;
    	if (!stk2.empty()){
        
    		res = stk2.top();
    		stk2.pop();
    	}
    	else{
        
    		while (!stk1.empty()){
        
    			stk2.push(stk1.top());
    			stk1.pop();
    		}
    		res = stk2.top();
    		stk2.pop();
    	}
    
    	return res;
    }
    
    int main()
    {
        
    	Queue que;
    	for (int type, x;;){
        
    		cin >> type;
    		if (type){
        
    			cin >> x;
    			que.EnQueue(x);
    		}
    		else{
        
    			cout << que.Dequeue() << endl;
    		}
    	}
    	return 0;
    }