博客

链式存储结构实现队列的入队和出队操作以及 栈的出栈和入栈操作其实本质上就是用含头结点的单链表来模拟队列的入队和出队，以及栈的入栈和出栈

换句话来形容，用单链表来实现队列和栈        队列的入队和栈的入栈用单链表示都是单链表的尾插法实现的。需要有个初始化队列和栈的函数

其实是就是建立一个单链表的头结点。

对于队列：队列是先进先出的数据结构只允许在队头删除元素，在队尾插入元素

存储结构

typedef struct QueueNode//队列结点
{
     int data;
	 QueueNode *next;
}QueueNode;
typedef struct Queue
{
     QueueNode *front;//队头指针始终指向单链表的头结点
	 QueueNode *rear;//队尾指针始终指向单链表的尾结点
}Queue;//队列的存储结构为两个指向队头，和队尾的 队列结点指针

入队操作：就是单链表的尾插法，插入一个结点

出队操作： 就是在含有头结点的单链表中删除第一个结点 Queue.front->next=Queue.front->next->next; 并释放第一个结点的内存

队列空满足条件　Queue.front==Queue.rear

对于栈：栈是后进先出的数据结构，只允许在栈顶插入和删除数据，栈底是不动的可以用来判断 栈是否为空

存储结构：

typedef struct StackNode//栈结点
{
     int data;
	 StackNode *next;
}StackNode;
typedef struct Stack
{
     StackNode *base;//栈底指针 始终不动指向单链表的头结点
	 StackNode *top;//栈顶指针 指向单链表的尾结点
}Stack;

入栈操作：
就是单链表的尾插法，插入一个结点

出栈操作：其实就是删除含头结点的单链表的尾结点，需要从头遍历单链表找到尾结点的前驱结点

栈空满足条件： Stack.base==Stack.top

以下为程序参考：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef struct QueueNode//队列结点
{
     int data;
	 QueueNode *next;
}QueueNode;
typedef struct Queue
{
     QueueNode *front;//队头指针始终指向单链表的头结点
	 QueueNode *rear;//队尾指针始终指向单链表的尾结点
}Queue;//队列的存储结构为两个指向队头，和队尾的 队列结点指针

void InitQueue(Queue*q)//初始状态为队空  队空满足条件Queue.front==Queue.rear
{
   q->front=q->rear=new QueueNode;//初始化队列起始就是建立一个头结点
   q->front->next=NULL;
}
void InQueue(Queue *pQueue,int value)//入队其实就是单链表的尾插法，Queue.front 始终指向头结点，而Queue.rear指向队尾元素
{
     QueueNode* pNew=new QueueNode;
	 pNew->data=value;
	 pNew->next=NULL;
	 pQueue->rear->next=pNew;
	 pQueue->rear=pNew;
}
void DeQueue(Queue *pQueue)//出队其实就是在含有头结点的单链表中删除第一个结点很简单    需注意：出队操时先要判断队列是否为空 
{
	if(pQueue->front==pQueue->rear)//判断队列是否为空
	{
	    return;
	}
    QueueNode * pToBeDeleted=pQueue->front->next;//指向第一个数据结点
	if(pQueue->front->next==pQueue->rear)//考虑删除只有一个结点时 删除后链表为空需要将pQueue->rear 指向头结点
	{
	     pQueue->rear=pQueue->front;
	}
	pQueue->front->next=pToBeDeleted->next;
	delete pToBeDeleted;
}
int TopElementOfQueue(Queue *pQueue)//取队头元素，方便测试
{
   if(pQueue->front!=pQueue->rear)//若队列不为空
	{
	    return pQueue->front->next->data;
	}
}
//以下结构为链式存储结构实现栈的入栈和出栈操作
typedef struct StackNode//栈结点
{
     int data;
	 StackNode *next;
}StackNode;
typedef struct Stack
{
     StackNode *base;//栈底指针 始终不动指向单链表的头结点
	 StackNode *top;//栈顶指针 指向单链表的尾结点
}Stack;
void InitStack(Stack *pStack)//
{
    pStack->base=pStack->top=new StackNode;
	pStack->base->next=NULL;
}
void Push(Stack*pStack,int value)//入栈其实就是单链表的尾插法
{
     StackNode *pNew=new StackNode;
	 pNew->data=value;
	 pNew->next=NULL;
	 pStack->top->next=pNew;
	 pStack->top=pNew;//  pStack->top  始终指向栈顶元素 也就是单链表的尾结点数据
}
void Pop(Stack *pStack)//出栈其实就是删除单链表的尾结点，需要从头遍历单链表找到尾结点的前驱结点
{
	if(pStack->base==pStack->top)//首先要判断栈是否为空
	{
	   return;
	}
    StackNode *pNode=pStack->base;//pNode 指向头结点 注意头结点的下一个结点才为第一个结点
	while(pNode->next!=pStack->top)//寻找尾结点的前驱结点;
	{
	     pNode=pNode->next;
	}
	delete pStack->top;//释放尾结点
	pStack->top=pNode;//新的尾结点为原来尾结点的前驱结点
    pNode->next=NULL;
}
int Top(Stack *pStack)
{
     if(pStack->base!=pStack->top)//栈不为空才能取栈顶元素
	{
		return pStack->top->data;
	}
}
int main()
{
   cout<<"链式存储结构实现队列的入队和出队"<<endl;
   Queue myQueue;
   InitQueue(&myQueue);
   for(int i=0;i<10;i++)
   {
       InQueue(&myQueue,i);
   }
   cout<<TopElementOfQueue(&myQueue)<<endl;
   DeQueue(&myQueue);
   cout<<TopElementOfQueue(&myQueue)<<endl;
    cout<<"链式存储结构实现栈的入栈和出栈"<<endl;
	Stack myStack;
	InitStack(&myStack);
	for(int i=0;i<10;i++)
   {
       Push(&myStack,i);
   }
   cout<<Top(&myStack)<<endl;
   Pop(&myStack);
   cout<<Top(&myStack)<<endl;
   return 0;
}