速通数据结构与算法第五站栈队列

系列文章目录

速通数据结构与算法系列

1   速通数据结构与算法第一站复杂度          http://t.csdnimg.cn/sxEGF

2   速通数据结构与算法第二站顺序表         http://t.csdnimg.cn/WVyDb

3   速通数据结构与算法第三站单链表          http://t.csdnimg.cn/cDpcC

4   速通数据结构与算法第四站双链表          http://t.csdnimg.cn/LCO0A

感谢佬们支持！

系列文章目录

前言
一、栈
1 结构体
2 接口声明
3
二、队列
三、OJ题
1 有效的括号
2 栈实现队列
3 队列实现栈
4 设计循环队列
总结

前言

前几篇博客我们学习了顺序表和链表，这篇博客我们要学习的是栈和队列，按底层来说，他们并不算是一种真正的新的容器，而是以底层容器完成其所有工作，具有"修改某物接口，形成另一种风貌"之性质者，称为adapter(配接器) （以上摘自《STL源码剖析》），换言之，栈和队列的

底层是顺序表或链表等容器。（虽然但是，deque由于其O(1)的头插头删尾插尾删使得其在SGI版本中成为了栈和队列的默认底层容器）

一、栈

只允许在一端进行插入和删除操作的特殊的线性表。进行插入和删除的一端叫栈顶，另一端叫栈底。栈中的元素满足FILO（first in last out）模式

有趣的是，根据出栈顺序的不同，我们可以得到不同的序列

比如入栈顺序是1，2，3，4，5

1 我们可以得到出栈顺序为5，4，3，2，1 即一次全部入栈后再全部出栈

2 我们可以得到出栈顺序为1，2，3，4，5 即每个元素入栈后立刻出栈

3 ……剩下的序列大家可以自己试试~

显然，由于我们进栈出栈在一端，我们可以用数组的尾插尾删模拟

先给一个结构体

结构体

typedef int STDataType;

typedef struct stack
{
	STDataType* a;
	int capacity;
	int top;//栈顶的下一个位置

}ST;

此处的top指向的是栈顶的下一个位置，为什么呢？

如果我们开始top给0，而此时栈里是没有元素的此时我们就不能说0是栈顶元素所在位置了

接口声明

栈的接口就相对少了

//初始化
void STInit(ST* ps);

//销毁
void STDestroy(ST* ps);

//入栈
void STPush(ST* ps, STDataType x);

//出栈
void STPop(ST* ps);

//判空
bool STEmpty(ST* ps);

//栈的大小
int STSize(ST* ps);

//返回栈顶元素
STDataType STTop(ST* ps);

初始化

开始给4个空间即可

//初始化
void STInit(ST* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//刚开始给4个
	if (ps->a == NULL)
	{
		perror("malloc\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;//top给0表示他是栈顶元素的下一个位置
}

销毁

//销毁
void STDestroy(ST* ps)
{
	ps->capacity = ps->top = 0;

	free(ps->a);
	ps->a = NULL;
}

下来是入栈的工作了，我们直接用数组的尾插模拟即可

入栈

//入栈
void STPush(ST* ps, STDataType x)
{
	//考虑扩容
	if (ps->capacity == ps->top && (!STEmpty(ps)))
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * 2 * ps->capacity);
		if (tmp == NULL)
		{
			perror("reolloc\n");
			exit(-2);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top++] = x;
}

（考虑扩容即可）

出栈

//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));//空了就不能出栈了

	ps->top--;
}

判空

//判空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

size

由于我们的top是指向栈顶元素的下一个，所以占栈的大小我们直接返回top即可

//栈的大小
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

返回栈顶

由于我们的top是指向栈顶元素的下一个，所以返回时要减1

//返回栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

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

我们可以简单的做波测试

注意：由于栈不支持遍历，我们只能通过拿到栈顶再pop的做法遍历

ST ps;
	STInit(&ps);
	STPush(&ps, 1);
	STPush(&ps, 2);
	STPush(&ps, 3);
	STPush(&ps, 4);
	STPush(&ps, 8);


	while (!STEmpty(&ps))
	{
		int top = STTop(&ps);
		printf("%d ", top);
		STPop(&ps);
	}

（非常奈斯）

完整代码

stack.h

#pragma once 

#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>

typedef int STDataType;

typedef struct stack
{
	STDataType* a;
	int capacity;
	int top;//栈顶的下一个位置

}ST;

//初始化
void STInit(ST* ps);

//销毁
void STDestroy(ST* ps);

//入栈
void STPush(ST* ps, STDataType x);

//出栈
void STPop(ST* ps);

//判空
bool STEmpty(ST* ps);

//栈的大小
int STSize(ST* ps);

//返回栈顶元素
STDataType STTop(ST* ps);

stack.c

#include"stack.h"

//初始化
void STInit(ST* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//刚开始给4个
	if (ps->a == NULL)
	{
		perror("malloc\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;//top给0表示他是栈顶元素的下一个位置
}

//销毁
void STDestroy(ST* ps)
{
	ps->capacity = ps->top = 0;

	free(ps->a);
	ps->a = NULL;
}

//入栈
void STPush(ST* ps, STDataType x)
{
	//考虑扩容
	if (ps->capacity == ps->top && (!STEmpty(ps)))
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * 2 * ps->capacity);
		if (tmp == NULL)
		{
			perror("reolloc\n");
			exit(-2);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top++] = x;
}


//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));//空了就不能出栈了

	ps->top--;
}

//判空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}


//栈的大小
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

//返回栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

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

test.c

#include"stack.h"
int main()
{
	ST ps;
	STInit(&ps);
	STPush(&ps, 1);
	STPush(&ps, 2);
	STPush(&ps, 3);
	STPush(&ps, 4);
	STPush(&ps, 8);


	while (!STEmpty(&ps))
	{
		int top = STTop(&ps);
		printf("%d ", top);
		STPop(&ps);
	}

	return 0;
}

二、队列

只允许在一端插入，另一端删除的特殊线性结构，具有FIFO（first in first out）的性质
入队列的一端叫队头

出队列的一端叫队尾

与栈不同，栈在边入边出时顺序会有所变化，队列没有变化

由于顺序表的头插不那么方便，我们可以用单链表实现，为了方便找尾，我们可以增加一个尾指针作为成员，就像之前OJ题我们做的那样

队列的结构体

typedef struct Queue
{
	QNode* head;
	QNode* tail;//为了方便找尾定义的
	int size;
}Queue;

队列节点的结构体

队列的每个节点其实就是单链表的节点

typedef struct QueueNode
{
	QDatatype data;
	struct QueueNode* next;
}QNode;

接口声明

下来看看我们的接口

//初始化
void QueueInit(Queue* pq);

//销毁
void QueueDestroy(Queue* pq);

//入栈
void QueuePush(Queue* pq, QDatatype x);

//出栈
void QueuePop(Queue* pq);

//大小
int QueueSize(Queue* pq);

//判空
bool QueueEmpty(Queue* pq);

//返回队头
QDatatype QueueFront(Queue* pq);

//返回队尾
QDatatype QueueBack(Queue* pq);

初始化

// 初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

销毁

和链表的销毁一样，我们只需提前保存下一个，再销毁即可，最后给头尾置空即可

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

入队列

入队列实际上就是单链表的尾插，由于我们有尾指针，尾插其实还是很方便的

//入队列
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//第一次插入
	if (pq->head==NULL)
	{
		assert(pq->tail == NULL);//如果head==NULL但tail！=空说明出事了

		pq->head=pq->tail=newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

出队列

出队列是单链表的头删，我们只需额外考虑只有一个节点的时候即可

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	QNode* cur = pq->head;

	if (pq->head->next == NULL)//考虑还剩一个的情况
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

size

//大小
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

判空

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

返回队头

显然，当队列为空时我们不能返回队首，队尾

//返回队头
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

返回队尾

//返回队尾
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

我们再简单的做一波测试

Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	
	int back = QueueFront(&q);
	int front = QueueBack(&q);

	printf("%d ", back);
	QueueDestroy(&q);

完整代码

queue.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDatatype;

typedef struct QueueNode
{
	QDatatype data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;//为了方便找尾定义的
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);

//销毁
void QueueDestroy(Queue* pq);

//入栈
void QueuePush(Queue* pq, QDatatype x);

//出栈
void QueuePop(Queue* pq);

//大小
int QueueSize(Queue* pq);

//判空
bool QueueEmpty(Queue* pq);

//返回队头
QDatatype QueueFront(Queue* pq);

//返回队尾
QDatatype QueueBack(Queue* pq);

queue.c

#include"queue.h"

// 初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//入队列
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//第一次插入
	if (pq->head==NULL)
	{
		assert(pq->tail == NULL);//如果head==NULL但tail！=空说明出事了

		pq->head=pq->tail=newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	QNode* cur = pq->head;

	if (pq->head->next == NULL)//考虑还剩一个的情况
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

//大小
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

//返回队头
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

//返回队尾
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

test.c

#include"queue.h"

void test1()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	
	int back = QueueFront(&q);
	int front = QueueBack(&q);

	printf("front:%d back:%d", front,back);
	QueueDestroy(&q);
}

int main()
{
	test1();
}

三、OJ题

有关栈和队列的几道OJ题并不难，只是为了让大家巩固所学的性质

有效的括号

题目链接：. - 力扣（LeetCode）

这里有的同学可能想到了数括号个数的方式，但是这没法保证左括号能以正确的顺序闭合

最好的方式其实是用栈，如果是左括号，我们就入栈，如果是右括号，我们就出栈匹配有一个不匹配说明这个s寄了

力扣的用例是很恶心的，我们可能会碰到只有左括号或只有又括号的用例

所以最后我们判断的标准是栈是否为空，如果为空，说明是有效的

代码还是很简单的，首先把我们上面写好的栈拷一份过去，然后再操作

bool isValid(char* s)
{
	ST st;
	STInit(&st);
	while (*s)
	{
		//左括号入栈，右括号匹配
		if (*s == '(' || *s == '[' || *s == '{')
		{
			STPush(&st, *s);
		}
		else//右括号就出栈匹配
		{
			if (!(STEmpty(&st)))
			{
				char top = STTop(&st);
				STPop(&st);
				if (top == '(' && *s != ')'
					|| top == '[' && *s != ']'
					|| top == '{' && *s != '}')
				{
					STDestroy(&st);
					return false;
				}
			}
			else
			{
				return false;
			}
		}
		s++;
	}
	int ret = STEmpty(&st);
	STDestroy(&st);
	return (ret);//最后不为空就是false
}

最后在返回的时候注意销毁就好啦~

队列实现栈

题目链接： . - 力扣（LeetCode）

队列实现栈，我们可以先模拟一下，假设在队列1push了1，2，3，4；现在我们想pop，由于是栈的行为，所以我们要pop的是4；但是现在队列1只能pop1怎么办？

可以将1，2，3都导至队列2，此时就可以pop1啦~

-》

现在我要再pop3怎么办？将1，2导至另一个队列

那我要push7，8，往哪个队列里push？显然是往非空的队列里push

另外：如何判空？显然当两个队列都为空时，我们模拟的栈为空

模拟出来以后就好办了，我们就能上手写代码啦~（别忘了将我们写的队列拷过来）

typedef struct
{
	Queue q1, q2;//成员:两个队列
} MyStack;


MyStack* myStackCreate()
{
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));

	QueueInit(&pst->q1);
	QueueInit(&pst->q2);

	return pst;
}

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

int myStackPop(MyStack* obj)
{
	//杭の经典操作
	Queue* emptyq = &obj->q1;
	Queue* noemptyq = &obj->q2;
	if (QueueEmpty(&obj->q2))
	{
		emptyq = &obj->q2;
		noemptyq = &obj->q1;
	}

	//倒数据
	while (QueueSize(noemptyq) > 1)
	{
		int val = QueueFront(noemptyq);
		QueuePop(noemptyq);
		QueuePush(emptyq, val);
	}
	int ret = QueueFront(noemptyq);
	QueuePop(noemptyq);
	return ret;
}

int myStackTop(MyStack* obj)
{
	if (QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q2);
	}
	else
	{
		return QueueBack(&obj->q1);
	}
}

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

void myStackFree(MyStack* obj)
{
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);

	free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/

栈实现队列

题目链接：. - 力扣（LeetCode）

我们还是采用模拟的思路画图

push个1，2，3，4先，此时我们要pop1，所以我们还是老样子，把1，2，3，4拷过去

-》

此时我们再pop，就是pop2了，然后我们会发现，数据倒过来后我们pop2就不用再往过倒了

这确实挺不错的。

那再插往哪插呢？直接往已经空了的栈1插就行。

如果连续pop后，栈二空了，我们再从栈一倒就行。

最后我们发现：左边的栈纯纯用来push，而右边的纯纯用来pop，所以我们直接起名为popS和pushS

代码启动！

typedef struct
{
	ST pushS;
	ST popS;
} MyQueue;


MyQueue* myQueueCreate()
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));

	STInit(&obj->pushS);
	STInit(&obj->popS);

	return obj;
}

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

int myQueuePeek(MyQueue* obj)
{
	if (STEmpty(&obj->popS))//pop栈为空就往过导
	{
		while (!STEmpty(&obj->pushS))
		{
			STPush(&obj->popS, (STTop(&obj->pushS)));
			STPop(&obj->pushS);
		}
	}
	int ret = STTop(&obj->popS);
	return ret;
}

int myQueuePop(MyQueue* obj)
{
	int ret = myQueuePeek(obj);
	STPop(&obj->popS);
	return ret;
}



bool myQueueEmpty(MyQueue* obj)
{
	return STEmpty(&obj->pushS) && STEmpty(&obj->popS);
}

void myQueueFree(MyQueue* obj)
{
	STDestroy(&obj->pushS);
	STDestroy(&obj->popS);

	free(obj);
	obj = NULL;
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/

设计循环队列

题目链接： . - 力扣（LexetCode）

循环队列的核心是循环，也就是当他走到了尾，他会再回到头

如果不用循环链表，其实我们可以用数组+%capacity的做法实现循环。

由于要支持取队首和队尾，所以我们需要一个头指针front以及一个尾指针back

头指针指向首个元素而尾指针指向尾部元素的下一个

这个时候有意思的就来了

显然刚开始front和back均指向同一个位置0，但是如果队列满了，他们指向的还是同一个位置

就像下图这样~

空

满

此时我们有两个办法

1 我们增加一个成员size，让size来判断是否为满

//size法

class MyCircularQueue {
public:
    MyCircularQueue(int k) : capacity(k) { nums.resize(k); }

    bool enQueue(int value) {
        if (isFull())
            return false;

        nums[back] = value;
        back = (back + 1) % capacity;
        size++;
        return true;
    }

    bool deQueue() {
        if (isEmpty())
            return false;

        front = (front + 1) % capacity;
        size--;
        return true;
    }

    int Front() {
        if (isEmpty())
        {
            return -1;
        }
        return nums[front];

    }

    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return nums[(back + capacity - 1) % capacity];
    }

    bool isEmpty() { return size == 0; }

    bool isFull()
    {
        return size == capacity;
    }

    vector<int> nums;
    int capacity;
    int size = 0;//size
    int front = 0;
    int back = 0;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

2 我们可以浪费一个空间，即让nums多开一个不存数据的空间，这样front和back就错开了

而判满的核心逻辑就是（back+1）%capacity是否等于front，其他都一样

可以，我们直接上代码


//浪费空间法

class MyCircularQueue {
public:
    MyCircularQueue(int k)
        :capacity(k + 1)
    {
        nums.resize(capacity);
    }

    bool enQueue(int value)
    {
        if (isFull())
            return false;

        nums[back] = value;
        back = (back + 1) % capacity;
        return true;
    }

    bool deQueue()
    {
        if (isEmpty())
            return false;

        front = (front + 1) % capacity;

        return true;
    }

    int Front()
    {
        if (isEmpty())
            return -1;

        return nums[front];
    }

    int Rear()
    {
        if (isEmpty())
            return -1;

        return nums[(back - 1 + capacity) % capacity];
    }

    bool isEmpty()
    {
        return back == front;
    }

    bool isFull()
    {
        return ((back + 1) % capacity) == front;
    }
    int front = 0;
    int back = 0;
    int capacity;//多留一个位置！
    vector<int> nums;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */