1. 栈
1.1 栈的概念及其结构
🐶 栈的定义:
一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
🐱 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
🐭 出栈:栈的删除操作叫做出栈。出数据也在栈顶。
1.2 栈的实现
💖 栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小
Stack.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stak {
STDataType* a;
int top;
int capacity;
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//元素入栈
void StackPush(ST* ps, STDataType x);
//元素出栈
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//栈的判空操作
bool StackEmpty(ST* ps);
//返回栈中的元素个数
int StackSize(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ST* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
if (!tmp){
perror("malloc fail::");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = 4;
ps->top = 0;
}
}
//销毁栈
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
//元素入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//考虑是否需要扩容
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity * 2;
ST* tmp = realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
if (!tmp){
perror("relloc fail::");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
//元素出栈
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
//取栈顶元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
//栈的判空操作
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//返回栈中的元素个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void StackTest1()
{
ST st;
StackInit(&st);
printf("入栈:1 2 3 4 5");
for (int i = 0; i < 5; i++) {
StackPush(&st, i+1);//压栈
}
printf("\n出栈:");
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));//取栈顶元素
StackPop(&st);
}
StackDestroy(&st);
}
int main()
{
StackTest1();
return 0;
}
2. 队列
2.1 队列的概念及其结构
🐶 队列的定义:
只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有 先进先出FIFO(First In First Out) 的性质。
🐱 性质:入队列:进行插入操作的一端称为队尾。出队列:进行删除操作的一端称为队头
2.2 队列的实现
💖 队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.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);
//返回队头元素
QDataType QueueFront(Queue* pq);
//返回队尾元素
QDataType QueueBack(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列中元素个数
int QueueSize(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* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (NULL == newnode)
{
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
//出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
//返回队头元素
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;
}
//判断队空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
//队列元素个数
int QueueSize(Queue* pq)
{
return pq->size;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePush(&q, 6);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
printf("队列中元素个数:%d\n", QueueSize(&q));
printf("队头元素:%d\n", QueueFront(&q));
printf("队尾元素:%d\n", QueueBack(&q));
//打印队列中的元素
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n队列是否为空:");
int ret = QueueEmpty(&q);
printf("%d\n", ret);
QueueDestroy(&q);
}
int main()
{
TestQueue();
return 0;
}
3. 栈和队列面试题
3.1 括号匹配问题
有效的括号
💖 思路:
这道题目是一个典型的用栈解决的问题,题目的意思是让我们实现左右括号匹配的问题,我们知道栈的特性是先进后出,大致思路是这样的:
(1)题目给了我们一个字符串,我们需要遍历这个字符串,当遇到的字符是左括号时,我们就将它入栈,当遇到右括号时,我们先看栈是否为空栈,若为空栈,说明没有与之匹配的左括号。直接销毁栈并且返回false。
(2)若栈不为空,在进行匹配,如果匹配成功,先s++,并弹出栈顶的元素,然后在进行下一次入栈或者匹配操作;如果匹配失败,则说明整个字符串的括号是不匹配的,直接返回false即可。
💕 代码实现
这里我们需要注意的是,由于C语言中没有栈相关的库函数,所以我们需要先把上面实现的栈先拷贝一份拿来用。
typedef char STDataType;
typedef struct Stak {
STDataType* a;
int top;
int capacity;
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//元素入栈
void StackPush(ST* ps, STDataType x);
//元素出栈
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//栈的判空操作
bool StackEmpty(ST* ps);
//返回栈中的元素个数
int StackSize(ST* ps);
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ST* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
if (!tmp){
perror("malloc fail::");
exit(-1);
}
else {
ps->a = tmp;
ps->capacity = 4;
ps->top = 0;
}
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//考虑是否需要扩容
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity * 2;
ST* tmp = realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
if (!tmp){
perror("relloc fail::");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool isValid(char * s){
ST st;
StackInit(&st);
while(*s)
{
if(*s=='('||*s=='['||*s=='{'){
StackPush(&st,*s);
++s;
}
else
{
if(StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
char tmp=StackTop(&st);
if((*s==')'&&tmp=='(')
||(*s==']'&&tmp=='[')
||(*s=='}'&&tmp=='{')){
s++;
StackPop(&st);
}
else
{
StackDestroy(&st);
return false;
}
}
}
if(StackEmpty(&st))
return true;
return false;
}
3.2 用队列实现栈
用队列实现栈
💖 思路:
我们知道队列的性质是先进先出,而栈的性质却是后进先出,那么如何用两个队列来实现栈后进先出的功能呢?这就需要我们利用两个队列来相互导数据了。具体思路如下:
(1)先定义两个队列并初始化为空队列,始终往一个空队列中入数据,第一次入数据时,由于两个队列都为空,随便选一个入数据即可。
(2)myStackPop——弹出栈顶元素,定义两个指针empty和nonEmpty分别指向空队列和非空队列,将非空队列中的数据一一导入空队列,直到非空队列中剩下一个数据为止。这时非空队列中的那一个元素就相当于栈顶元素,将其返回则可以实现取栈顶元素,将此队列出队则为出栈操作。
(3)由于出栈时,其中一个队列已经置为了空队列,所以下次入栈时直接往另一个不为空的队列中入数据即可;取栈顶的元素即为非空队列中队尾的元素,直接将其返回即可。栈的判空操作即判断两个队列是否全部为空即可。
💕 代码实现:
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);
QDataType QueueFront(Queue*pq);
QDataType QueueBack(Queue*pq);
bool QueueEmpty(Queue*pq);
QDataType QueueSize(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*del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue*pq,QDataType x)
{
assert(pq);
QNode*newnode = (QNode*)malloc(sizeof(QNode));
if(NULL == newnode)
{
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if(pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue*pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if(pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode*del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
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;
}
bool QueueEmpty(Queue*pq)
{
assert(pq);
return pq->head == NULL&&pq->tail == NULL;
}
QDataType QueueSize(Queue*pq)
{
return pq->size;
}
//定义了两个队列,一个为q1和q2
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
if(NULL == obj)
{
exit(-1);
}
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
//看哪个是否为空
if(!QueueEmpty(&obj->q1))
{
//队列不为空就插入数据
QueuePush(&obj->q1,x);
}
//q2可能为空或不为空
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
//删除栈顶的元素
Queue*empty = &obj->q1;
Queue*nonEmpty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
nonEmpty = &obj->q1;
}
while(QueueSize(nonEmpty)>1)
{
//取队头数据存放到空的队列,最后剩下一个,这个就是栈顶的元素
QueuePush(empty,QueueFront(nonEmpty));
QueuePop(nonEmpty);
}
int top = QueueFront(nonEmpty);
QueuePop(nonEmpty);
return top;
}
int myStackTop(MyStack* obj) {
//取栈的头相当于非空的队列的队尾
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
}
3.3 用栈实现队列
用栈实现队列
💖 思路:
栈的性质是后进先出,队列的性质是先进先出,我们要使用两个栈来实现队列先进先出的性质,如果将一个栈中的元素导入另一个栈中,是不是另一个栈中的元素出栈时是不是就变成了队列的出队顺序呢?好了,具体思路如下:
(1)先定义两个空栈,一个栈用来入数据为push栈,另一个栈用来出数据为pop栈。第一次入数据时,将数据全部往push栈中入。
(2)myQueuePop——返回并移除队头元素,先判断pop栈是否为空,如果不为空,先将pop栈中的栈顶元素保存,然后在移除栈顶元素,最后返回此元素即可;如果pop栈为空,我们需要先将push栈中的元素导入pop栈中,然后在进行刚刚的操作即可。
(3)myQueuePeek——返回队头元素,要返回队头元素,如果pop栈为空,就必须先将push栈中的元素导入pop栈中,然后直接返回pop栈中的栈顶元素即可。否则只需要直接返回栈顶元素即可。
💖 代码实现:
typedef int STDataType;
typedef struct Stak {
STDataType* a;
int top;
int capacity;
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//元素入栈
void StackPush(ST* ps, STDataType x);
//元素出栈
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//栈的判空操作
bool StackEmpty(ST* ps);
//返回栈中的元素个数
int StackSize(ST* ps);
void StackInit(ST* ps)
{
assert(ps);
ST* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
if (!tmp){
perror("malloc fail::");
exit(-1);
}
else {
ps->a = tmp;
ps->capacity = 4;
ps->top = 0;
}
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//考虑是否需要扩容
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity * 2;
ST* tmp = realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
if (!tmp){
perror("relloc fail::");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
typedef struct {
ST pushST;
ST popST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->pushST);
StackInit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->pushST,x);
}
int myQueuePop(MyQueue* obj) {
if(StackEmpty(&obj->popST)){
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST,StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
int tmp=StackTop(&obj->popST);
StackPop(&obj->popST);
return tmp;
}
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->popST)){
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST,StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->popST)&&StackEmpty(&obj->pushST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->popST);
StackDestroy(&obj->pushST);
free(obj);
}
3.4 设计循环队列
这里我们先来介绍一下循环队列:循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
设计循环队列OJ链接
💖 思路:
循环队列相对普通队列新增了一个队首的指针front,队尾的指针为tail,即初始化时队列的队首和队尾指向同一个位置。在入队时,队尾的指针不再是向后加一位,而是在向后加一位的基础上还要对队列的长度取余运算。因为当队尾的指针在最后一位时,如果此时队列未满,即表明队列前方还有空余的空间,所以此时队尾需要对队列长度取余回到队列头部空余的位置。
💕 代码实现:
typedef struct {
int *a;
int front;
int rear;
int k;
} MyCircularQueue;
//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->rear=0;
obj->k=k;
return obj;
}
//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->front==obj->rear;
}
//判断队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
return (obj->rear+1)%(obj->k+1)==obj->front;
}
//循环队列入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear++]=value;
obj->rear=(obj->rear)%(obj->k+1);
return true;
}
//循环队列出数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front=obj->front%(obj->k+1);
return true;
}
//返回队头数据
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
//返回队尾数据
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->rear==0?obj->a[obj->k]:obj->a[obj->rear-1];
}
//释放队列
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}