数据结构与算法——队列的实现（链表实现和两个栈实现）

曾经终败给现在 2022-02-28 05:34 218阅读 0赞

队列（queue）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。  
允许插入的一端称为队尾（rear）,允许删除的是队头（front）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70]  
//链表实现队列  
//（1）添加的时候就添加链表的最后  
//（2）弹出的时候就弹出头指针后一个位置的元素  
//两个栈实现队列  
//s2为空,先将s1全部装入s2再弹出

**//链表实现队列**

#include <iostream>
    using namespace std;
    
    typedef struct Node
    { 
    	Node *next;
    	int data;
    
    }Node;
    
    static Node *pHead = NULL;//头指针不包含数据
    
    
    Node * creat_node(int elem)
    { 
    	Node *p = (Node *)malloc(sizeof(Node));
    	if (p == NULL)
    	{ 	
    		return NULL;
    	}
    	p->next = NULL;
    	p->data = elem;
    
    	return p;
    }
    
    void push(int elem)
    { 
    	if (pHead == NULL)
    	{ 
    		return;
    	}	
    
    	Node *p = creat_node(elem);
    
    	//zy 找到尾部
    	Node *q = pHead;
    	while (q->next != NULL)
    	{ 
    		q = q->next;
    	}
    
    	q->next = p;
    	p = NULL;
    	q = NULL;
    	
    }
    
    int front()
    { 
    	if (pHead->next == NULL)
    	{ 
    		return 0;
    	}
    	return pHead->next->data;
    }
    
    void pop()
    { 
    	if (pHead->next == NULL)
    	{ 
    		return;
    	}
    
    	Node *p = pHead->next;
    	pHead->next = p->next;
    	free(p);
    	p = NULL;
    }
    
    int isEmpty()
    { 
    	if (pHead == NULL || pHead->next == NULL)
    	{ 
    		return true;
    	}
    	else
    	{ 
    		return false;
    	}
    }
    
    
    int main()
    { 
    	//创建无数据的头结点
    	pHead = (Node *)malloc(sizeof(Node));
    	if (pHead == NULL)
    		return NULL;
    	pHead->next = NULL;
    
    	push(10);
    	push(20);
    	push(30);
    	pop();
    	push(40);
    
    	while (!isEmpty())
    	{ 
    		cout << front() << " ";
    		pop();
    	}
    
    	cout << endl;
    	return 0;
    }

**//两个栈实现队列**

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    stack<int> s1,s2;
    int length = 0;
    
    void push(int elem)
    { 
    	s1.push(elem);
    	length ++;
    }
    
    int pop()
    { 
    	if(s2.empty()) //s2为空,先将s1全部装入s2再弹出
    	{ 
    		while (!s1.empty())
    		{ 
    			s2.push(s1.top());
    			s1.pop();
    		}
    	}
    
    	int temp = s2.top();
    	s2.pop();
    	--length;
    	return temp;
    
    
    }
    
    int main()
    { 
    	push(10);
    	push(20);
    	push(30);
    
    	pop(); pop();
    	push(40);
    	push(50);
    
    	while (length)
    	{ 
    		cout << pop()  << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70]: /images/20220228/7657dbc65c4f4b328bc76143b0ff5a24.png