首页 > 编程学习 > 栈和队列详解

栈和队列详解

发布时间:2022/11/7 6:46:46

栈和队列

  • 1.栈
    • 1.1栈的概念和结构
    • 1.2栈的实现
  • 2.队列
    • 2.1队列的概念及结构
    • 2.2队列的实现
      • 2.3扩展
  • 3.队列实现栈
  • 4.栈实现队列

1.栈

1.1栈的概念和结构

栈:特殊的线性表,只允许在固定的一端进行插入和删除数据。
进行数据插入和删除的一端称作栈顶,另一端称作栈底

压栈:栈的插入操作称作压栈,压入栈的数据在栈顶
出栈:栈的删除操作称作出栈,出栈的数据也在栈顶

栈中数据遵守后进先出原则

压栈
在这里插入图片描述

出栈
在这里插入图片描述

1.2栈的实现

栈的实现有两个选择数组链表
二者相比,数组实现栈更好些,根据栈的特点,在尾部插入数据的情况下,数组更方便。

数组实现栈
在这里插入图片描述

链表实现栈

在这里插入图片描述

这里采取数组的结构来实现栈

定义结构体和类型

typedef int SKdatatype;

typedef struct Stack
{
	SKdatatype* a;
	int top;//记录栈中元素的个数
	int capacity;//栈的容量
}SK;

初始化栈

//初始化栈
void SKinit(SK* ps);

void SKinit(SK* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

在这里插入图片描述

在这里插入图片描述

销毁栈

//销毁栈
void SKdestory(SK* ps);


void SKdestory(SK* ps)
{
	assert(ps);
	ps->capacity = ps->top = 0;
	free(ps->a);
	ps->a = NULL;
}

数据压栈

//压栈
void SKpush(SK* ps, SKdatatype x);

void SKpush(SK* ps, SKdatatype x)
{
	assert(ps);

	//检查容量
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SK* tmp = (SK*)realloc(ps->a, newcapacity * sizeof(SK));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

在这里插入图片描述

压入两个数据进栈,监视如下

在这里插入图片描述

栈顶ps->top此时是2,说明栈中已经有两个数据。

数据出栈

//出栈
void SKpop(SK* ps);

void SKpop(SK* ps)
{
	assert(ps);
	assert(!SKempty(ps));
	ps->top--;
}

在这里插入图片描述

数组中删除元素,不需要清除元素

将栈顶的数据出栈,监视如下

在这里插入图片描述

栈顶ps->top此时是1,从上面可知,栈顶的数据已经出栈,栈中还有一个数据。

获得栈顶元素

//获得栈顶元素
SKdatatype SKtop(SK* ps);

SKdatatype SKtop(SK* ps)
{
	assert(ps);

	assert(!SKempty(ps));

	return ps->a[ps->top - 1];
}

在这里插入图片描述

在这里插入图片描述

检查栈是否为空

//检查是否是空栈
bool SKempty(SK* ps);

bool SKempty(SK* ps)
{
	assert(ps);

	return ps->top == 0;
}

计算栈中的数据个数

//计算栈中数据的个数
int SKsize(SK* ps);


int SKsize(SK* ps)
{
	assert(ps);
	return ps->top;
}

2.队列

2.1队列的概念及结构

队列:只允许在一端进行插入数据操作,另一端进行删除数据操作的特殊线性表
队列遵守先进先出原则
队尾:进行插入数据操作的一端
队头:进行删除数据操作的一端

在这里插入图片描述

2.2队列的实现

队列的实现也同样有两种选择:数组链表。二者相比之下,链表更好些,因为链表的特点头删的效率很高。

数据入队,尾部插入

在这里插入图片描述

数据出队,头部删除

在这里插入图片描述

定义结构体和类型

为了方便数据的增删查改,这里定义队列的头尾指针

typedef int Queuedatatype;
typedef struct Queuenode
{
	struct Queuenode* next;
	Queuedatatype data;
}QEnode;


typedef struct Queue
{
	QEnode* head;//队首指针
	QEnode* tail;//队尾指针
	int size;//用于记录队列中数据个数
}QE;

队列的初始化

//初始化队列
void QEinit(QE* p);

void QEinit(QE* p)
{
	assert(p);
	p->size = 0;
	p->head = p->tail = NULL;
}

在这里插入图片描述

队列的销毁

//销毁队列
void QEdestory(QE* p);

void QEdestory(QE* p)
{
	assert(p);

	QEnode* cur = p->head;
	while (cur)
	{
		QEnode* del = cur;
		cur = cur->next;
		free(del);
	}
	p->head = p->tail = NULL;
	p->size = 0;
}

数据从队尾插入队列

//数据插入队列
void QEpush(QE* p,Queuedatatype x);


void QEpush(QE* p,Queuedatatype x)
{
	assert(p);
	QEnode* newnode = (QEnode*)malloc(sizeof(QEnode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}


	if (p->tail == NULL)
	{
		p->head = p->tail = newnode;
	}
	else
	{
		p->tail->next = newnode;
		p->tail = p->tail->next;
	}

	p->size++;
}

在这里插入图片描述

将三个数据从队尾插入队列中,监视如下,此时size==3,表示队列中已经插入三个数据

在这里插入图片描述

读取队首数据

//读取队首数据
Queuedatatype QEfront(QE* p);


Queuedatatype QEfront(QE* p)
{
	assert(p);
	assert(!QEempty(p));
	return p->head->data;
}

在这里插入图片描述

读取队尾数据

//读取队尾数据
Queuedatatype QEback(QE* p);

Queuedatatype QEback(QE* p)
{
	assert(p);
	assert(!QEempty(p));
	return p->tail->data;
}

在这里插入图片描述

检查队列是否为空

//检查队列是否为空
bool QEempty(QE* p);

bool QEempty(QE* p)
{
	assert(p);

	return p->head == NULL && p->tail == NULL;
}

数据从队首删除

//数据出队列
void QEpop(QE* p);


void QEpop(QE* p)
{
	assert(p);
	assert(!QEempty(p));
	if (p->head->next == NULL)
	{
		free(p->head);
		p->head = p->tail = NULL;
	}
	else
	{
		QEnode* del = p->head;
		p->head = p->head->next;
		free(del);
		del = NULL;
	}
	p->size--;
}

在这里插入图片描述

将一个数据从队首删去,此时队列中只剩余两个个数据,监视如下

在这里插入图片描述

计算队列中数据的个数

//计算队列中数据的个数
int QEsize(QE* p);

int QEsize(QE* p)
{
	assert(p);

	return p->size;
}

2.3扩展

特殊的一种队列:循环队列
同样的道理循环队列的实现也有两种方式:数组链表

在这里插入图片描述

空的环形队列

在这里插入图片描述

满的环形队列

在这里插入图片描述

既然说到环形队列,不如思考思考如何去实现?

首先实现方式有两种:数组队列

由于在读取队尾数据时,如果遇到如下情况,则不能进行读取数据
还需要定义一个位于 back 前一个位置的指针,比较麻烦。

所以采用数组实现环形队列

注意
采用数组实现环形队列,存在一个问题:队列空和队列满无法区分。
解放方法有两个:

  1. 创建结构体时,额外加一个用于记录数据个数的变量
  2. 额外增加一个空间,队列满时永远留一个空位置

在这里插入图片描述

定义结构体

typedef struct 
{
    int*a;//数组,用于存储数据
    int front;//队头指针
    int back;//队尾指针
    int n;//环形队列中数据的总数
} MyCircularQueue;

初始化环形队列

MyCircularQueue* myCircularQueueCreate(int k) 
{
    //环形队列开辟空间
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //数组开辟空间
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->back=0;
    //环形队列的长度
    obj->n=k+1;
    return obj;
}

环形队列初始化

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->back=0;
    obj->n=k+1;
    return obj;
}

front指向队头
back指向队尾的下一个位置

在这里插入图片描述

检查环形队列是否为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front==obj->back;
}

检查环形队列是否已满

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->back+1)%obj->n==obj->front;
}

数据入队

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    obj->a[obj->back]=value;
    obj->back++;
    
    //防止back指针指向数组的最后
    //再次++,导致数组越界
    obj->back%=obj->n;

    return true;
}

在这里插入图片描述

数据出队

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    obj->front%=obj->n;
    return true;
}

读取队头

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->front];
    }
}

读取队尾

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {   //避免back指针指向队头,向前一个位置访问读取数据时
        //导致数组越界
        return obj->a[(obj->back-1+obj->n)%(obj->n)];
    }
}

在这里插入图片描述

销毁环形队列

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);
    free(obj);
}

在这里插入图片描述

3.队列实现栈

使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)

首先思考队列的栈对于数据进出所遵循的原则,队列是先进先出而栈是先进后出。
既然这两种线性表所遵循的原则不相同,又该用什么方式去实现呢?

两个队列是关键点,接下来就思考两个队列如何去实现队列。

假设只有一个队列中有数据,另一个队列为空。

在这里插入图片描述

此时队列 q2 删除数据的话,只能从队头删除,这样就不符合栈先进后出的原则。

如果将队列 q2 只留下队尾的数据,其余的全部转移到队列 q1 中,这时删除 q2 中数据就符合后进先出的原则。

在这里插入图片描述

同样的道理如果再次删除数据,就将队列 q1 中除队尾以外的数据转移到队列 q2 中,再进行删除操作。

由此便得到思路:保持一个队列为空,删除数据时,将另一个不为空的队列的数据除队尾以外全部转移到空队列中。

定义两个队列

typedef struct {
    QE q1;
    QE q2;
} MyStack;

两个队列实现栈,并进行初始化

MyStack* myStackCreate()
{
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    QEinit(&obj->q1);
    QEinit(&obj->q2);
    return obj;
}

在这里插入图片描述

数据入栈

void myStackPush(MyStack* obj, int x) 
{
    if(!(QEempty(&obj->q1)))
    {
        QEpush(&obj->q1,x);
    }
    else
    {
        QEpush(&obj->q2,x);
    }
}

这里假设队列 q2 不为空

在这里插入图片描述

数据出栈

先判断队列 q1,q2 哪个为空,哪个不为空

假设队列 q2 不为空,将其 N-1 个数据转移到 队列 q1 中,接着将最后一个数据出栈

int myStackPop(MyStack* obj) 
{
    QE*empty=&obj->q1;
    QE*nonempty=&obj->q2;
    if(!QEempty(&obj->q1))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    //将队列中的N-1个数据,转移到空队列中
    while(QEsize(nonempty)>1)
    {
        QEpush(empty,QEfront(nonempty));
        QEpop(nonempty);
    }
    //取出栈顶数据(也就是不为空队列的最后一个数据)
    int top = QEfront(nonempty);
    //删除不为空队列最后一个数据
    QEpop(nonempty);
    //返回栈顶数据
    return top;
}

在这里插入图片描述

读取栈顶数据

先判断哪个队列不为空,读取不为空队列的队尾数据,即栈顶数据

int myStackTop(MyStack* obj) {
    if(!QEempty(&obj->q1))
    {
        return QEback(&obj->q1);
    }
    else
    {
        return QEback(&obj->q2);
    }
}

在这里插入图片描述

判断栈是否为空

必须队列 q1 ,q2 都为空,才能说明栈也为空

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QEempty(&obj->q1)&&QEempty(&obj->q2);
}

销毁栈

销毁栈,不可以直接释放栈开辟的空间,会造成内存泄漏

因为队列q1 q2 中也有开辟的空间,直接释放栈开辟的空间,会导致再也找不到队列开辟的空间,从而造成内存泄漏

所有先将队列销毁,最后再释放栈开辟的空间

void myStackFree(MyStack* obj) {
    QEdestory(&obj->q1);
    QEdestory(&obj->q2);
    free(obj);
}

在这里插入图片描述

4.栈实现队列

既然队列可以实现栈,那么栈是否可以实现队列呢?

答案是:当然可以

与上面类似,都是需要两个,也就是通过两个队列去实现栈

由于栈所遵守的原则是先进后出,所以不需要将其中一个栈一直保存空的状态

接下来开始慢慢分析

两个栈 其中 pushSK 是插入数据的栈,popSK 是删除数据的栈

在这里插入图片描述

如果此时删除数据,按照队列的原则需要将第一个插入的数据进行删除操作,也就是删除位于栈底的 1 。很简单只需要将 pushSK 中的所有数据全部转移到 popSK 中即可。然后在 popSK 中删除栈顶数据 1,就完成队列的数据删除

在这里插入图片描述

如果继续删除数据,便可直接在 popSK 中删除,直到栈 popSK 为空,再将栈 pushSK 中的数据全部转移到其中。

由此可得出思考:
插入数据到pushSK 中,然后将pushSK 中的数剧全部转移到 popSK 中,当 popSK为空,再重复此操作。
由于栈的特点,转移的数据再 popSK 中全部都是倒置的,因此符合队列的特点。

定义两个栈 pushSK,popSK

typedef struct 
{
    SK pushSK;//数据压入栈
    SK popSK;//数据压出栈
} MyQueue;

初始化两个栈

MyQueue* myQueueCreate() 
{
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    SKinit(&obj->pushSK);
    SKinit(&obj->popSK);

    return obj;
}

在这里插入图片描述

数据插入队列

void myQueuePush(MyQueue* obj, int x) 
{
    SKpush(&obj->pushSK,x);
}

在这里插入图片描述

数据出队列

在删除队头的数据时,需要判断 栈 popSK 是否为空。如果为空,则不能完成删除操作。

为了方便起见,将判断这一过程独立为函数,在之后还能用到

void pushSKtopopSK(MyQueue*obj)
{
    if(SKempty(&obj->popSK))
    {
        while(!SKempty(&obj->pushSK))
        {
            SKpush(&obj->popSK,SKtop(&obj->pushSK));
            SKpop(&obj->pushSK);
        }
    }
}

在这里插入图片描述

int myQueuePop(MyQueue* obj) 
{
    if(SKempty(&obj->popSK))
    {
        pushSKtopopSK(obj);
    }

    int top=SKtop(&obj->popSK);
    SKpop(&obj->popSK);

    return top;
}

在这里插入图片描述

读取队头数据

int myQueuePeek(MyQueue* obj) 
{
    if(SKempty(&obj->popSK))
    {
        pushSKtopopSK(obj);
    }
    return SKtop(&obj->popSK);
}

在这里插入图片描述

判断队列是否为空

栈 pushSK和 栈 popSK 必须都为空,队列才表示为空

bool myQueueEmpty(MyQueue* obj) 
{
    return SKempty(&obj->pushSK)&&SKempty(&obj->popSK);
}

销毁队列

与上面类似,不能直接释放队列所开辟的空间,否则同样会造成内存泄漏

void myQueueFree(MyQueue* obj) 
{
    SKdestory(&obj->pushSK);
    SKdestory(&obj->popSK);
    free(obj);
}

在这里插入图片描述

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式