数据结构-双向链表——栈和队列

（1）双向链表

【1】头插法

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
	ElemType data;
	Node *prev,*next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
int insertHead(Node *L,ElemType e){
	Node *p=new Node;
	p->data=e;
	p->prev=L;
	p->next=L->next;
	if(L->next!=NULL){
		
		L->next->prev=p;
	}
	L->next=p;
	return true;
}
void listNode(Node* L)
{	
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int main()
{
	Node* list=initList();
	insertHead(list,10);
	insertHead(list,20);
	insertHead(list,30);//头插法 
	listNode(list);
}

【2】尾插法

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
	ElemType data;
	Node *prev,*next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
int insertHead(Node *L,ElemType e){
	Node *p=new Node;
	p->data=e;
	p->prev=L;
	p->next=L->next;
	if(L->next!=NULL){
		
		L->next->prev=p;
	}
	L->next=p;
	return true;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* insertTail(Node *tail,ElemType e)
{
	Node *p=new Node;
	p->data=e;
	p->prev=tail;
	tail->next=p;
	p->next=NULL;
	return p;
}
void listNode(Node* L)
{	
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int main()
{
	Node* list=initList();
	Node* tail=get_tail(list);//头插法 
	tail=insertTail(tail,40);
	tail=insertTail(tail,30);//尾插法 
	tail=insertTail(tail,20);
	tail=insertTail(tail,10);
	listNode(list);
}

【3】在指定位置插入数据

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
	ElemType data;
	Node *prev,*next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
int insertHead(Node *L,ElemType e){
	Node *p=new Node;
	p->data=e;
	p->prev=L;
	p->next=L->next;
	if(L->next!=NULL){
		
		L->next->prev=p;
	}
	L->next=p;
	return true;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* insertTail(Node *tail,ElemType e)
{
	Node *p=new Node;
	p->data=e;
	p->prev=tail;
	tail->next=p;
	p->next=NULL;
	return p;
}
void listNode(Node* L)
{	
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int insertNode(Node *L,int pos,ElemType e)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL){
			return 0;
		}
	} 
	Node *q=new Node;
	q->data=e;
	q->prev=p;
	q->next=p->next;
	p->next=q;
	p->next->prev=q;
	return true;
}
int main()
{
	Node* list=initList();
	Node* tail=get_tail(list);//头插法 
	tail=insertTail(tail,40);
	tail=insertTail(tail,30);//尾插法 
	tail=insertTail(tail,20);
	tail=insertTail(tail,10);
	insertNode(list,2,55);//在指定位置插入数据 
	listNode(list);
}

【4】删除节点

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
	ElemType data;
	Node *prev,*next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
int insertHead(Node *L,ElemType e){
	Node *p=new Node;
	p->data=e;
	p->prev=L;
	p->next=L->next;
	if(L->next!=NULL){
		
		L->next->prev=p;
	}
	L->next=p;
	return true;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* insertTail(Node *tail,ElemType e)
{
	Node *p=new Node;
	p->data=e;
	p->prev=tail;
	tail->next=p;
	p->next=NULL;
	return p;
}
void listNode(Node* L)
{	
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int insertNode(Node *L,int pos,ElemType e)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL){
			return 0;
		}
	} 
	Node *q=new Node;
	q->data=e;
	q->prev=p;
	q->next=p->next;
	p->next=q;
	p->next->prev=q;
	return true;
}
void freeList(Node *L)
{
	Node *p=L->next;
	Node *q;
	while(p!=NULL){
		q=p->next;
		delete p;
		p=q;
	}
	L->next=NULL;	
}
int deleteNode(Node* L,int pos)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL){
			return 0;
		}
	}
	if(p->next==NULL){
		cout<<"删除错误"<<endl;
		return 0;
	}
	Node *q=p->next;
	p->next=q->next;
	q->next->prev=p;
	delete q;
	return true;
}
int main()
{
	Node* list=initList();
	Node* tail=get_tail(list);//头插法 
	tail=insertTail(tail,40);
	tail=insertTail(tail,30);//尾插法 
	tail=insertTail(tail,20);
	tail=insertTail(tail,10);
	insertNode(list,2,55);//在指定位置插入数据 
	deleteNode(list,3);//删除指定位置的节点 
	listNode(list);
}

【5】其他的都和单项链表一样

【6】栈的顺序结构实现

#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Stack{
	ElemType data[MAXSIZE];
	int top;
};
void initStack(Stack *s){
	s->top=-1;
}
int isEmpty(Stack *s)
{
	if(s->top==-1){
		cout<<"空的"<<endl;
		return true;
	}
	else
	{
		return false;
	}
}
int push(Stack *s,ElemType e)
{
	if(s->top>=MAXSIZE-1){
		cout<<"满了"<<endl;
		return false;
	}
	s->top++;
	s->data[s->top]=e;
	return true;
}
ElemType pop(Stack *s,ElemType *e)
{
	if(s->top==-1)
	{
		cout<<"空的"<<endl;
		return false;
	}
	*e=s->data[s->top];
	s->top--;
	return true; 
}
int getTop(Stack *s,ElemType *e)
{
	if(s->top==-1){
		cout<<"空的"<<endl;
		return 0;
	} 
	*e=s->data[s->top];
	return 0;
}
int main()
{
	Stack s;
	initStack(&s);//初始化 
	push(&s,90);
	push(&s,80);
	push(&s,70);//压栈 
	ElemType e;
	pop(&s,&e);//出栈 
	cout<<e<<endl;
	getTop(&s,&e);//获得栈顶元素 
	cout<<e<<endl;
}

【7】栈的顺序结构-动态内存分配

只有初始化和结构体改变了

#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Stack{
	ElemType *data;
	int top;
};
Stack* initStack(){
	Stack *s=new Stack;
	s->data=new ElemType[MAXSIZE];
	s->top=-1;
	return s;
}
int isEmpty(Stack *s)
{
	if(s->top==-1){
		cout<<"空的"<<endl;
		return true;
	}
	else
	{
		return false;
	}
}
int push(Stack *s,ElemType e)
{
	if(s->top>=MAXSIZE-1){
		cout<<"满了"<<endl;
		return false;
	}
	s->top++;
	s->data[s->top]=e;
	return true;
}
ElemType pop(Stack *s,ElemType *e)
{
	if(s->top==-1)
	{
		cout<<"空的"<<endl;
		return false;
	}
	*e=s->data[s->top];
	s->top--;
	return true; 
}
int getTop(Stack *s,ElemType *e)
{
	if(s->top==-1){
		cout<<"空的"<<endl;
		return 0;
	} 
	*e=s->data[s->top];
	return 0;
}
int main()
{
	Stack *s=initStack();//初始化 
	push(s,90);
	push(s,80);
	push(s,70);//压栈 
	ElemType e;
	pop(s,&e);//出栈 
	cout<<e<<endl;
	getTop(s,&e);//获得栈顶元素 
	cout<<e<<endl;
}

【8】栈的链式结构

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Stack{
	ElemType data;
	Stack *next; 
};
Stack* initStack()
{
	Stack *s=new Stack;
	s->data=0;
	s->next=NULL;
	return s;
}
int isEmpty(Stack *s)
{
	if(s->next==NULL)
	{
		cout<<"空的"<<endl;
		return 1;
	}
	else
	{
		return 0;
	}
}
int push(Stack *s,ElemType e)
{
	Stack *p=new Stack;
	p->data=e;
	p->next=s->next;
	s->next=p;
	return true;
}
int pop(Stack *s,ElemType *e)
{
	if(s->next==NULL)
	{
		cout<<"空的"<<endl;
		return 0;
	}
	*e=s->next->data;
	Stack *q=s->next;
	s->next=q->next;
	delete q;
	return true;
}
int getTop(Stack *s,ElemType *e)
{
	if(s->next==NULL)
	{
		cout<<"空的"<<endl;
		return 0;
	}
	*e=s->next->data;
	return 1; 
}
int main()
{
	Stack *s=initStack();
	push(s,10);
	push(s,20);
	push(s,30);
	ElemType e;
	pop(s,&e);
	cout<<e<<endl;
	getTop(s,&e);
	cout<<e<<endl;
	
}

【9】队列顺序结构

（1）栈内存中的形式

#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Queue{
	ElemType data[MAXSIZE];
	int front;
	int rear;
};
void initQueue(Queue *Q){
	Q->front=0;
	Q->rear=0;
}
int isEmpty(Queue *Q){
	if(Q->front==Q->rear){
		cout<<"空的"<<endl;;
		return true;
	}
	else
	{
		return false;
	}
}
ElemType dequeue(Queue *Q)
{
	if(Q->front==Q->rear)
	{
		cout<<"空的"<<endl;
		return 0;
	}
	ElemType e=Q->data[Q->front];
	Q->front++;
	return e;
}
int queueFull(Queue *Q)
{
	if(Q->front>0)
	{
		int step=Q->front;
		for(int i=Q->front;i<=Q->rear;i++)
		{
			Q->data[i-step]=Q->data[i];
		}
		Q->front=0;
		Q->rear=Q->rear-step;
		return true;
	}
	else
	{
		cout<<"真的满了"<<endl;
		return false;
	}
}
int equeue(Queue *Q,ElemType e)
{
	if(Q->rear>=MAXSIZE)
	{
		if(!queueFull(Q))
		{
			return 0;
		}
	}
	Q->data[Q->rear]=e;
	Q->rear++;
	return 1; 
}

int getHead(Queue *Q,ElemType *e)
{
	if(Q->front==Q->rear)
	{
		cout<<"空的"<<endl;
		return 0; 
	}
	*e=Q->data[Q->front];
	return 1;
}
int main()
{
	Queue q;
	initQueue(&q); 
	equeue(&q,10);
	equeue(&q,20);
	equeue(&q,30);
	equeue(&q,40);//队列入队 
	cout<<dequeue(&q)<<endl;
	cout<<dequeue(&q)<<endl;//出队 
	ElemType e;
	getHead(&q,&e);//获取队头元素 
	cout<<e<<endl;
}

（2）堆内存的形式

#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Queue{
	ElemType *data;
	int front;
	int rear;
};
Queue * initQueue(){
	Queue *q=new Queue;
	q->data=new ElemType[MAXSIZE];
	q->front=0;
	q->rear=0;
	return q; 
}
int isEmpty(Queue *Q){
	if(Q->front==Q->rear){
		cout<<"空的"<<endl;;
		return true;
	}
	else
	{
		return false;
	}
}
ElemType dequeue(Queue *Q)
{
	if(Q->front==Q->rear)
	{
		cout<<"空的"<<endl;
		return 0;
	}
	ElemType e=Q->data[Q->front];
	Q->front++;
	return e;
}
int queueFull(Queue *Q)
{
	if(Q->front>0)
	{
		int step=Q->front;
		for(int i=Q->front;i<=Q->rear;i++)
		{
			Q->data[i-step]=Q->data[i];
		}
		Q->front=0;
		Q->rear=Q->rear-step;
		return true;
	}
	else
	{
		cout<<"真的满了"<<endl;
		return false;
	}
}
int equeue(Queue *Q,ElemType e)
{
	if(Q->rear>=MAXSIZE)
	{
		if(!queueFull(Q))
		{
			return 0;
		}
	}
	Q->data[Q->rear]=e;
	Q->rear++;
	return 1; 
}

int getHead(Queue *Q,ElemType *e)
{
	if(Q->front==Q->rear)
	{
		cout<<"空的"<<endl;
		return 0; 
	}
	*e=Q->data[Q->front];
	return 1;
}
int main()
{
	Queue *q=initQueue();
	equeue(q,10);
	equeue(q,20);
	equeue(q,30);
	equeue(q,40);//队列入队 
	cout<<dequeue(q)<<endl;
	cout<<dequeue(q)<<endl;//出队 
	ElemType e;
	getHead(q,&e);//获取对头元素 
	cout<<e<<endl;
}

【10】循环队列（普通队列的效率太慢了，才引入循环队列）

（1）代码是存在bug的无论如何都会空出一个格，如图

alt

#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Queue{
	ElemType *data;
	int front;
	int rear;
};
Queue * initQueue(){
	Queue *q=new Queue;
	q->data=new ElemType[MAXSIZE];
	q->front=0;
	q->rear=0;
	return q; 
}
int isEmpty(Queue *Q){
	if(Q->front==Q->rear){
		cout<<"空的"<<endl;;
		return true;
	}
	else
	{
		return false;
	}
}
ElemType dequeue(Queue *Q)
{
	if(Q->front==Q->rear)
	{
		cout<<"空的"<<endl;
		return 0;
	}
	ElemType e=Q->data[Q->front];
	Q->front=(Q->front+1)%MAXSIZE;
	return e;
}
int equeue(Queue *Q,ElemType e)
{
	if((Q->rear+1)%MAXSIZE==Q->front)
	{
		cout<<"满了"<<endl;
		return 0;
	}
	Q->data[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXSIZE;
	return 1; 
}

int getHead(Queue *Q,ElemType *e)
{
	if(Q->front==Q->rear)
	{
		cout<<"空的"<<endl;
		return 0; 
	}
	*e=Q->data[Q->front];
	return 1;
}
int main()
{
	Queue *q=initQueue();
	equeue(q,10);
	equeue(q,20);
	equeue(q,30);
	equeue(q,40);//队列入队 
	cout<<dequeue(q)<<endl;
	cout<<dequeue(q)<<endl;//出队 
	ElemType e;
	getHead(q,&e);//获取对头元素 
	cout<<e<<endl;
}