C/C++教程

图解数据结构:使用C++(第四章)

本文主要是介绍图解数据结构:使用C++(第四章),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第四章 堆栈与队列

堆栈(stack)是一组类型相同数据的组合(如数组)。具有先进后出的特性,所有的操作都在栈顶进行。


“heap和stack区别:1、heap是堆,stack是栈;2、stack的空间由操作系统自动分配和释放,heap的空间是手动申请和释放的;3、stack空间有限,heap的空间是很大的自由区。”

stack相对速度快。


//
// Ch04_01
//
#include <iostream>
#include <iomanip>
#define MAXSTACK 100		//定义堆栈的最大容量
using namespace std;
int stack[MAXSTACK];		//声明用于堆栈操作的数组
int top=-1;				//堆栈的顶端
//判断是否为空堆栈
int isEmpty() 
{
    if(top==-1) return 1;
    else return 0;
}
//将指定的数据压入堆栈
int push(int data)
{
    if(top>=MAXSTACK)
    {
       cout<<"堆栈已满,无法再压入"<<endl;
       return 0; 
    }
    else
    {
       stack[++top]=data;		//将数据压入堆栈
       return 1;
        
    }
}
//从堆栈弹出数据
int pop()
{
    if(isEmpty())			//判断堆栈是否为空,如果是则返回-1
       return -1;
    else
       return stack[top--];	//将数据弹出后,再将堆栈指针往下移
}
//主程序
int main(void)
{
    int value;
    int i;
    cout<<"请按序输入10个数据:"<<endl;
    for(i=0;i<10;i++)
    {
       cin>>value;
       push(value);
    }
    cout<<"===================="<<endl;
    while(!isEmpty())		//将数据陆续从顶端弹出
       cout<<"堆栈弹出的顺序为:"<<setw(2)<<pop()<<endl; 
    cout<<"===================="<<endl;
    system("pause");      
    return 0; 
}

//
// Ch04_02
//
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>

using namespace std;
void Swap(int*,int*);
void push(int statck[],int MAX,int val);
int pop(int stack[]);
int top=-1;
int main(void)
{  
	int card[52],stack[52]={0};
	int i,j,k=0, ascVal;
	char suit[4][10]={"草花","方块","红桃","黑桃"};
	int style;
	srand((unsigned)time(NULL));
	for (i=0;i<52;i++)
		card[i]=i+1;
	cout<<"[洗牌中...请稍后!]"<<endl;
	while(k<30)
	{
		for(i=0;i<51;i++)
			for(j=i+1;j<52;j++)
				if(rand()%52==2)
					Swap(&card[i],&card[j]);//洗牌
		k++;
	}
	i=0;
	while(i!=52)
	{
		push(stack,52,card[i]);//将52张牌压入堆栈
		i++;
	}
	cout<<"[逆时针发牌]"<<endl;
	cout<<"[显示各家拿到的牌]"<<endl;
 	cout<<"\t\t东家\t 北家\t 西家\t 南家"<<endl;
	cout<<"========================================================="<<endl;
	while (top >=0)
	{  
		style = stack[top]/13;	//计算扑克牌的花色
		switch(style)			//扑克牌花色对应的图标
		{
			case 0:			//梅花
				ascVal=0;
				break;
			case 1:			//方块
				ascVal=1;
				break;
			case 2:			//红心
				ascVal=2;
				break;
			case 3:			//黑桃
				ascVal=3;
				break;
		}
		cout<<"["<<suit[ascVal]<<setw(3)<<stack[top]%13+1<<"]\t";
		if(top%4==0)
			cout<<endl;
		top--;
	}
	system("pause");      
    return 0;
}
void push(int stack[],int MAX,int val)
{
	if(top>=MAX-1)
		cout<<"[堆栈已经满了]"<<endl;
	else
	{
		top++;
		stack[top]=val;
	}
}
int pop(int stack[])
{
	if(top<0)
		cout<<"[堆栈已经空了]"<<endl;
	else
		top--;
	return stack[top];
}
void Swap(int* a,int* b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

//
// Ch04_03
//
#include <iostream>
#include <cstdlib>
#include <iomanip>

using namespace std;
class Node	//声明堆栈链表节点
{
   public:
   int data;	//声明存放堆栈数据的变量
   class Node *next;	//堆栈中用来指向下一个节点的指针
};
typedef class Node Stack_Node;		//定义堆栈中节点的新类型
typedef Stack_Node *Linked_Stack;	//定义链表堆栈的新类型
Linked_Stack top=NULL;				//指向堆栈顶端的指针

//判断是否为空堆栈
int isEmpty()
{
    if(top==NULL) return 1;
    else return 0;
}
//将指定的数据压入堆栈
void push(int data)
{
    Linked_Stack new_add_node;	//新加入节点的指针
    //分配内存给新节点
    new_add_node=new Stack_Node;
    new_add_node->data=data;		//将传入的值赋值给节点的数据变量
    new_add_node->next=top;		//将新节点指向堆栈的顶端
    top=new_add_node;			//新节点成为堆栈的顶端
}
//从堆栈弹出数据
int pop()
{
    Linked_Stack ptr;		//指向堆栈顶端的指针
    int temp;
    if(isEmpty())			//判断堆栈是否为空,如果是则返回-1
    {
       cout<<"===目前为空堆栈==="<<endl;
       return -1;
    }
    else
    {
        ptr=top;		//指向堆栈的顶端
        top=top->next;	//将堆栈顶端的指针指向下一个节点
        temp=ptr->data;	//取出堆栈的数据
        free(ptr);			//将节点占用的内存释放
        return temp;		//将从堆栈取出的数据返回给主程序
    }
}
//主程序
int main(void)
{
    int value;
    int i;
    cout<<"请按序输入10个数据:"<<endl;
    for(i=0;i<10;i++)
    {
       cin>>value;
       push(value);
    }
    cout<<"===================="<<endl;
    while(!isEmpty()) //将数据陆续从顶端弹出
       cout<<"堆栈弹出的顺序为:"<<setw(2)<<pop()<<endl; 
    cout<<"===================="<<endl;
    system("pause");      
    return 0; 
}

//
// Ch04_04
//
#include <iostream>
#include <cstdlib>
using namespace std;

template <class Type>	 // 定义链表中的节点
struct Node
{
  Type data;	// 记录数据
  Node* next;// 记录下一笔节点的地址
};
template <class Type>
class LinkedList	// 链表类型
{
  private:
   Node<Type>* first;	    // 指到第一个节点的指针
   public:
     LinkedList()			    // 构造函数
     {
       first = NULL;
     }
   void addNode(Type data);	// 加入节点
   void display();			    // 显示所有的节点
};
   template<class Type>
   void LinkedList<Type>::addNode(Type data)
   {
    Node<Type>* newNode = new Node<Type>;	// 新增一个节点
    newNode->data = data;			// 记录数据
    newNode->next = first;		// 指向前一个节点
    first = newNode;			// 指向新的节点
   }
   template<class Type>
   void LinkedList<Type>::display()
   {
     Node<Type>* currentNode = first;    // 从第一个节点开始显示
     while( currentNode != NULL )
     {
     cout << currentNode->data << " -> ";
	 currentNode = currentNode->next;
     }
  }

int main()
{
    LinkedList<double> dblList;	    // 建立一个存储double类型数据的链表
    double num;					// 记录输入的数据
    char ch;						// 记录用户的选择
    	do{
           cout << endl <<"请输入一个数字 : ";
           cin >> num;
           dblList.addNode( num );
           cout << "继续输入(y / n)?";
           cin >> ch;
         }while( ch != 'n' );
      cout << endl;
      dblList.display();				// 显示所有的数据
      cout << endl << endl;
      
      system("pause");
      return 0;
}

//
// Ch04_05
//
#include <iostream>
#include <cstdlib>
using namespace std;

// 设定类样版的类型参数Type的默认值为整数int,非类型参数的类型为整数int,默认值为5
template <class Type = int, int size = 5>		// 声明类样板
class Stack
{
      private:
        Type st[size];	// 声明一数组作为堆栈的存储空间
        int top;		// 堆栈数据顶端的索引
      public:
        Stack()
         {
          top = -1;
          }
       void push(Type data);	// 将数据压入堆栈
       Type pop();			// 将数据从堆栈中弹出
   };
   template < class Type, int size >
   void Stack< Type, size > :: push ( Type data )
   {
    st[ ++top ] = data;
  	}
   template < class Type, int size >
   Type Stack<Type, size> :: pop()
   {
        return st[ top-- ];
    }
   int main()
   {
    Stack<> stk_1;			// 声明一个堆栈对象, 并使用其默认值
    Stack<char*, 4> stk_2;	// 声明堆栈对象, 其类型为字符串, 大小为4
    stk_1.push( 11 );
    stk_1.push( 22 );
    stk_1.push( 33 );
    cout << "stack_1 [1] = " << stk_1.pop() << endl;
    cout << "stack_1 [2] = " << stk_1.pop() << endl;
    cout << "stack_1 [3] = " << stk_1.pop() << endl;
    cout << endl;
    stk_2.push( "第一名" );
    stk_2.push( "第二名" );
    stk_2.push( "第三名" );
    cout << "stack_2 [1] = " << stk_2.pop() << endl;
    cout << "stack_2 [2] = " << stk_2.pop() << endl;  
    cout << "stack_2 [3] = " << stk_2.pop() << endl;
    cout << endl;
    
    system("pause");
    return 0;
    	
    }

//
// Ch04_06
//
#include <iostream>
#define EAST  MAZE[x][y+1]	//定义东方的相对位置
#define WEST  MAZE[x][y-1]	//定义西方的相对位置
#define SOUTH MAZE[x+1][y]	//定义南方的相对位置
#define NORTH MAZE[x-1][y]	//定义北方的相对位置
using namespace std;
const int ExitX = 8;		//定义出口的X坐标在第8行
const int ExitY = 10;		//定义出口的Y坐标在第10列
struct list
{
	int x,y;
	struct list* next;
};
typedef struct list node;
typedef node* link;
int MAZE[10][12] = { 1,1,1,1,1,1,1,1,1,1,1,1,		//声明迷宫数组
		             1,0,0,0,1,1,1,1,1,1,1,1,
				     1,1,1,0,1,1,0,0,0,0,1,1,
				     1,1,1,0,1,1,0,1,1,0,1,1,
				     1,1,1,0,0,0,0,1,1,0,1,1,
				     1,1,1,0,1,1,0,1,1,0,1,1,
				     1,1,1,0,1,1,0,1,1,0,1,1,
				     1,1,1,1,1,1,0,1,1,0,1,1,
				     1,1,0,0,0,0,0,0,1,0,0,1,
				     1,1,1,1,1,1,1,1,1,1,1,1};
link push(link stack,int x,int y);
link pop(link stack,int* x,int* y);
int chkExit(int ,int ,int,int);
int main(void)
{
	int i,j;
	link path = NULL;
	int x=1;		//入口的X坐标
	int y=1;    	//入口的Y坐标
	cout<<"[迷宫的路径(0的部分)]"<<endl; //打印出迷宫的路径图
	for(i=0;i<10;i++)
	{
		for(j=0;j<12;j++)
			cout<<MAZE[i][j]<<" ";
		cout<<endl;
	}
	while(x<=ExitX&&y<=ExitY)
	{
		MAZE[x][y]=2;
		if(NORTH==0)
		{
			x -= 1;
			path=push(path,x,y);
		}
		else if(SOUTH==0)
		{
			x+=1;
			path=push(path,x,y);
		}
		else if(WEST==0)
		{
			y-=1;
			path=push(path,x,y);
		}
		else if(EAST==0)
		{
			y+=1;
			path=push(path,x,y);
		}
		else if(chkExit(x,y,ExitX,ExitY)==1)	//检查是否走到出口了
			break;
		else
		{
			MAZE[x][y]=2;
			path=pop(path,&x,&y);
		}
	}
	cout<<"[老鼠走过的路径(2的部分)]"<<endl; //打印出老鼠成功走出迷宫的路径图
	for(i=0;i<10;i++)
	{
		for(j=0;j<12;j++)
			cout<<MAZE[i][j]<<" ";
		cout<<endl;
	}
	system("pause");      
    return 0;
}
link push(link stack,int x,int y)
{
	link newnode;
	newnode = new node;
	if(!newnode)
	{
		cout<<"Error!内存分配失败!"<<endl;
		return NULL;
	}
	newnode->x=x;
	newnode->y=y;
	newnode->next=stack;
	stack=newnode;
    return stack;
}
link pop(link stack,int* x,int* y)
{
	link top;
	if(stack!=NULL)
	{
		top=stack;
		stack=stack->next;
		*x=top->x;
		*y=top->y;
		delete top;
		return stack;
	}
	else
		*x=-1;
	return stack;
}
int chkExit(int x,int y,int ex,int ey)
{
	if(x==ex&&y==ey)
	{
		if(NORTH==1||SOUTH==1||WEST==1||EAST==2)
			return 1;
		if(NORTH==1||SOUTH==1||WEST==2||EAST==1)
			return 1;
		if(NORTH==1||SOUTH==2||WEST==1||EAST==1)
			return 1;
		if(NORTH==2||SOUTH==1||WEST==1||EAST==1)
			return 1;
    }
	return 0;
}

//
// Ch04_07
//

#include <iostream>
#include <iomanip>
#include <cmath>
#define EIGHT 8	//定义堆栈的最大容量
#define TRUE 1
#define FALSE 0
using namespace std;
int queen[EIGHT];	//存放8个皇后的行位置
int number=0;		//计算总共有几组解
//决定皇后存放的位置
//输出所需要的结果
int attack(int ,int);
void print_table()
{
     int x=0,y=0;
     number+=1;
     cout<<endl;
     cout<<"八皇后问题的第"<<setw(2)<<number<<"组解"<<endl<<"\t";
     for(x=0;x<EIGHT;x++)
     {
        for(y=0;y<EIGHT;y++)
           if(x==queen[y])
              cout<<"<q>";
           else
              cout<<"<->";
        cout<<endl<<"\t";
     } 
     system("pause"); 
}
void decide_position(int value) 
{
   int i=0;
   while(i<EIGHT)
   {
   //是否受到攻击的判断语句
      if(attack(i,value)!=1)
      {
         queen[value]=i;
         if(value==7)
            print_table();
         else
            decide_position(value+1);
      }
      i++;
   }    
}
//测试在(row, col)上的皇后是否遭受攻击
//若遭受攻击则返回值为1,否则返回0
int attack(int row,int col)
{
    int i=0,atk=FALSE;
    int offset_row=0,offset_col=0;
    while((atk!=1)&&i<col)
    {
       offset_col=abs(i-col);
       offset_row=abs(queen[i]-row);
       //判断两皇后是否在同一行或在同一对角线
       if((queen[i]==row)||(offset_row==offset_col))
          atk=TRUE;
       i++;
    }
    return atk;
}
//主程序
int main(void)
{
    decide_position(0);      
    return 0; 
}

/*
// Ch04_08
[示范]:将数学表达式由中序表示法转为后序表示法 
*/
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
#define MAX 50
char infix_q[MAX]; //用来存放中序表示法的队列  
//运算符优先级的比较,若输入运算符的优先级小于堆栈中运算符的优先级,
//则返回值为1,否则为0                          
int compare(char stack_o, char infix_o)
{
//在中序表示法队列和暂存堆栈中,运算符的优先级表,
//其优先级值为INDEX/2                               
    char infix_priority[9] ; 
	char stack_priority[8] ;
	int index_s=0, index_i=0;
	infix_priority[0]='q';infix_priority[1]=')';
	infix_priority[2]='+';infix_priority[3]='-';
	infix_priority[4]='*';infix_priority[5]='/';
	infix_priority[6]='^';infix_priority[7]=' ';
	infix_priority[8]='(';      
	stack_priority[0]='q';stack_priority[1]='(';
	stack_priority[2]='+';stack_priority[3]='-';
	stack_priority[4]='*';stack_priority[5]='/';
	stack_priority[6]='^';stack_priority[7]=' ';
	while (stack_priority[index_s] != stack_o)
		index_s++;
	while (infix_priority[index_i] != infix_o)
		index_i++;
	return ((int)(index_s/2) >= (int)(index_i/2) ? 1 : 0);
}
//中序转前序的方法
void infix_to_postfix()
{
	int rear=0, top=0, flag=0,i=0;
	char stack_t[MAX];  
	for (i=0; i<MAX; i++)
			stack_t[i]='\0';
	    gets(infix_q);
	    i=0;
	    while(infix_q[i]!='\0') 
	    {
          i++;
          rear++;
        }
		infix_q[rear] = 'q';  //在队列加入q为结束符号
		cout<<"\t"<<"后序表示法 : ";
		stack_t[top]  = 'q';  //在堆栈加入q为结束符号
		for (flag = 0; flag <= rear; flag++)\
        {		
			switch (infix_q[flag]) 
            {
				//输入为)时,则输出堆栈内的运算符,直到堆栈内为(
				case ')':
					while(stack_t[top]!='(') 			      
						cout<<setw(1)<<stack_t[top--];				   
					top--;
					break;
				//输入为q,则将堆栈内还未输出的运算符输出
				case 'q':
					while(stack_t[top]!='q')
						cout<<setw(1)<<stack_t[top--];
					break;
				//输入为运算符,若其优先级小于TOP在堆栈中所指运算符的优先级,
                //则将堆栈所指运算符输出,若优先级大于等于TOP在堆栈中所指运算符
                //的优先级,则将输入的运算符压入堆栈。 
				case '(':
				case '^':
				case '*':
				case '/':
				case '+':
				case '-': 
					while (compare(stack_t[top], infix_q[flag])==1)                       
						cout<<setw(1)<<stack_t[top--];			
					stack_t[++top] = infix_q[flag];
					break;
				//输入为操作数,则直接输出
				default :
					cout<<setw(1)<<infix_q[flag];
					break;
			}
		}
}
//主函数声明
int main (void) 		
{ 
    int i=0;
    for (i=0; i<MAX; i++)
	infix_q[i]='\0';	
	cout<<"\t=========================================="<<endl;
	cout<<"\t本程序会将其转成后序法表达式"<<endl;
    cout<<"\t请输入中序法表达式"<<endl;
    cout<<"\t例如:(9+3)*8+7*6-8/4 "<<endl;
    cout<<"\t可以使用的运算符包括:^,*,+,-,/,(,)等 "<<endl;
    cout<<"\t=========================================="<<endl;
    cout<<"\t请开始输入中序法表达式: ";
    infix_to_postfix();
    cout<<endl;
    cout<<"\t=========================================="<<endl;
    system("pause");      
    return 0; 
}

/*
// Ch04_09
[示范]:实现队列数据的进队和出队
*/
#include <iostream>
using namespace std;
const int MAX=20;//定义队列的大小
int main(void)
{
	int front,rear,val,queue[MAX]={0};
	char ch;
	front=rear=-1;
	while(rear<MAX-1&&ch!='E')
	{  
		cout<<"[I]存入一个数值 [G]取出一个数值 [E]结束: ";
		cin>>ch;
		switch(ch)
		{
			case 'I':
				cout<<"[请输入数值]: ";
				cin>>val;
				rear++;
				queue[rear]=val;
				break;
			case 'G':
				if(rear>front)
				{  
					front++;
					cout<<"[取出数值为]: ["<<queue[front]<<"]";
					cout<<endl;
					queue[front]=0;
				}
				else
				{  
					cout<<"[队列已经空了]"<<endl;
					exit(0);
				}
				break;
			default:
				cout<<endl;
				break;
		}
	}
	if(rear==MAX-1) cout<<"[队列已经满了]"<<endl;
	cout<<"[目前队列中的数据]:";
	if (front>=rear)
	{
		cout<<"没有"<<endl;
		cout<<"[队列已经空了]"<<endl;
	}
	else
	{
		while (rear>front)
		{  
			front++;
			cout<<"["<<queue[front]<<"]\t";
		}
		cout<<endl;
	}
	system("pause");
	return 0;
}

/*
// Ch04_10
[示范]:以链表来实现队列
*/
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
class Node
{
   public:
   int data;
   class Node *next;
};
typedef class Node QueueNode;
typedef QueueNode *QueueByLinkedList;
QueueByLinkedList front=NULL;
QueueByLinkedList rear=NULL;
//方法enqueue:数据的加入队列
void enqueue(int value) {
   QueueByLinkedList node; //建立节点
   node=new QueueNode;
   node->data=value;
   node->next=NULL;
  //检查是否为空队列
   if (rear==NULL)
      front=node; //新建立的节点成为第1个节点
   else
      rear->next=node; //将节点加入到队列的末尾
   rear=node; //将队列的末尾指针指向新加入的节点
}
//方法dequeue:从队列取出数据
int dequeue() 
{
   int value;
//检查队列是否为空队列
   if (!(front==NULL)) 
   {
     if(front==rear) rear=NULL;
     value=front->data; //从队列取出数据
     front=front->next; //将队列的前端指针指向下一个
     return value;
   }
   else return -1;
}
int main(void)
{
   int temp;
   cout<<"         以链表来实现队列"<<endl;
   cout<<"===================================="<<endl;
   cout<<"在队列前端加入第1个数据,此数据值为1"<<endl;
   enqueue(1);
   cout<<"在队列前端加入第2个数据,此数据值为3"<<endl;
   enqueue(3);
   cout<<"在队列前端加入第3个数据,此数据值为5"<<endl;
   enqueue(5);
   cout<<"在队列前端加入第4个数据,此数据值为7"<<endl;
   enqueue(7);
   cout<<"在队列前端加入第5个数据,此数据值为9"<<endl;
   enqueue(9);
   cout<<"===================================="<<endl;
   while (1) 
   {
      if (!(front==NULL)) 
      {
         temp=dequeue();
         cout<<"从队列前端按序取出的元素数据值为:"<<setw(1)<<temp<<endl;
      }
      else
         break;
   }
   cout<<endl;
   system("pause");
   return 0;
}

/*
// Ch04_11
[示范]:实现环状队列数据的进队和出队
*/
#include <iostream>
using namespace std;
int main(void)
{  
	int front,rear,val=0,queue[5]={0};
	front=rear=-1;
	while(rear<5&&val!=-1)
	{  
	    cout<<"请输入一个值以存入队列,欲取出值请输入-2。(结束输入-1):";
		cin>>val;
		if(val==-2)
		{  
			if(front==rear)
			{  
				cout<<"[队列已经空了]"<<endl;
				break;
			}
			front++;
			if (front==5)
				front=0;
			cout<<"取出队列值 ["<<queue[front]<<"]"<<endl;
			queue[front]=0;
		}
		else if(val!=-1 && rear<5)
		{  
			if(rear+1==front || rear==4 && front<=0)
			{  
				cout<<"[队列已经满了]"<<endl;
				break;
			}
			rear++;
			if(rear==5)
				rear=0;
			queue[rear]=val;
		}
	}
	cout<<"\n队列剩余数据:"<<endl;
	if (front==rear)
		cout<<"队列已空!!"<<endl;
	else 
	{ 
		while(front!=rear)
		{  
			front++;
			if (front==5)
				front=0;
			cout<<"["<<queue[front]<<"]";
			queue[front]=0;
		}
	}
	cout<<endl;
	system("pause");
	return 0;
}

/*
// Ch04_12
[示范]:实现双向队列
*/
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
class Node
{
   public:
   int data;
   class Node *next;
};
typedef class Node QueueNode;
typedef QueueNode *QueueByLinkedList;
QueueByLinkedList front=NULL;
QueueByLinkedList rear=NULL;
//方法enqueue: 数据加入队列
void enqueue(int value) 
{
   QueueByLinkedList node; //建立节点
   node=new QueueNode;
   node->data=value;
   node->next=NULL;
   //检查是否为空队列
   if (rear==NULL)
      front=node;//新建立的节点成为第1个节点
   else
      rear->next=node;//将节点加入到队列的末尾
   rear=node;//将队列的队尾指针指向新加入的节点
}
//方法dequeue:从队列取出数据
int dequeue(int action)
{
   int value;
   QueueByLinkedList tempNode,startNode;
   //从队首取出数据
   if (!(front==NULL) && action==1) 
   {
     if(front==rear) rear=NULL;
     value=front->data;//将队列数据从队首取出
     front=front->next;//将队列的队首指针指向下一个
     return value;
   }
   //从队尾取出数据
   else if(!(rear==NULL) && action==2) 
   {
     startNode=front;//先记下队首的指标值
     value=rear->data;//取出当前队尾的数据
     //寻找最末尾节点的前一个节点
     tempNode=front;
     while (front->next!=rear && front->next!=NULL) 
     { 
           front=front->next;
           tempNode=front;
     }
     front=startNode;//记录从队尾取出数据后的队列队首指针
     rear=tempNode;//记录从队尾取出数据后的队列队尾指针
     //下一行程序是指当队列中仅剩下最后一个节点时,
     //取出数据后便将front和rear指向NULL
     if ((front->next==NULL) || (rear->next==NULL)) 
     { 
         front=NULL;
         rear=NULL;
     }
     return value; 
   }
   else return -1;
}
int main(void)
{
   int temp;
   cout<<"以链表来实现双向队列"<<endl;
   cout<<"===================================="<<endl;
   cout<<"在双向队列队首加入第1笔数据,此数据值为1"<<endl;
   enqueue(1);
   cout<<"在双向队列队首加入第2笔数据,此数据值为3"<<endl;
   enqueue(3);
   cout<<"在双向队列队首加入第3笔数据,此数据值为5"<<endl;
   enqueue(5);
   cout<<"在双向队列队首加入第4笔数据,此数据值为7"<<endl;
   enqueue(7);
   cout<<"在双向队列队首加入第5笔数据,此数据值为9"<<endl;
   enqueue(9);
   cout<<"===================================="<<endl;
   temp=dequeue(1);
   cout<<"从双向队列队首按序取出的元素数据值为:"<<setw(1)<<temp<<endl;
   temp=dequeue(2);
   cout<<"从双向队列队尾按序取出的元素数据值为:"<<setw(1)<<temp<<endl;
   temp=dequeue(1);
   cout<<"从双向队列队首按序取出的元素数据值为:"<<setw(1)<<temp<<endl;
   temp=dequeue(2);
   cout<<"从双向队列队尾按序取出的元素数据值为:"<<setw(1)<<temp<<endl;
   temp=dequeue(1);
   cout<<"从双向队列队首按序取出的元素数据值为:"<<setw(1)<<temp<<endl;
   cout<<endl;
   system("pause");
   return 0;
}

这篇关于图解数据结构:使用C++(第四章)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!