【本节目标】
- 1.栈
- 2.队列
- 3.栈和队列面试题
1.栈
1.1栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。
栈中的数据元素遵守后进先出
LIFO
(
Last In First Out
)的原则。
压栈:栈的插入操作叫做进栈
/
压栈
/
入栈,
入数据在栈顶
。
出栈:栈的删除操作叫做出栈。
出数据也在栈顶
。
1.2栈的实现
栈的实现一般可以使用数组或者链表实现
,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 栈顶
}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
*1.2.1具体代码
stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDatatype;
struct stack
{
STDatatype* arr;
int top;
int capacity;
};
typedef struct stack ST;
void STInit(ST* ps);//初始化
void STDestory(ST* ps);//销毁
void STPush(ST* ps, STDatatype x);//压栈
void STPop(ST* ps);//出栈;
STDatatype STTop(ST* ps);//栈顶的数
int STSize(ST* ps);//栈的大小
bool STEmpty(ST* ps);
stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
void STDestory(ST* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
void STPush(ST* ps, STDatatype x)
{
assert(ps);
//满了扩容
if (ps->top == ps->capacity)
{
int newcapacity;
if (ps->capacity == 0)
{
newcapacity = 4;
}
else
{
newcapacity = 2 * ps->capacity;
}
STDatatype* temp = (STDatatype*)realloc(ps->arr, newcapacity * sizeof(STDatatype));
if (temp == NULL)
{
perror("realloc fail!");
return;
}
ps->arr = temp;
ps->capacity = newcapacity;
}
ps->arr[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)
{
assert(ps);
ps->top--;
}
STDatatype STTop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
return ps->arr[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
int main()
{
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
STPush(&s, 5);
while (!STEmpty(&s))
{
int top = STTop(&s);
printf("%d ", top);
STPop(&s);
}
}
这个就是 后进先出的意思
但是也不是绝对的
2.队列
2.1队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为
队尾
出队列:进行删除操作的一端称为
队头
2.2队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数 组头上出数据,效率会比较低。
// 链式结构:表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
*2.2.1队列具体代码的实现
queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QueueData;
struct QueueNode
{
QueueData val;
struct QueueNode* next;
};
typedef struct QueueNode QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Que;
void QueueInit(Que* pq);//队列初始化
void QueueDestroy(Que* pq);//队列销毁
void QueuePush(Que* pq,QueueData x);//入队列
void QueuePop(Que* pq);//出队列
QueueData QueueBack(Que* pq);
QueueData QueueFront(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);
queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
void QueueInit(Que* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Que* pq)
{
QNode* pcur = pq->phead;
while (pcur)
{
QNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
void QueuePush(Que* pq,QueueData x)
{
assert(pq);
QNode* newnode = (Que*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail)
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
else
{
pq->phead = pq->ptail = newnode;
}
pq->size++;
}
void QueuePop(Que* pq)
{
assert(pq->phead != NULL);
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead =pq->ptail= NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QueueData QueueFront(Que* pq)
{
assert(pq!=NULL);
assert(pq->phead != NULL);
return pq->phead->val;
}
QueueData QueueBack(Que* pq)
{
assert(pq!=NULL);
assert(pq->ptail != NULL);
return pq->ptail->val;
}
bool QueueEmpty(Que* pq)
{
return pq->phead == NULL;
}
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
注意看栈和队列是相对的
3.栈和队列面试题
1. 括号匹配问题。
20. 有效的括号 - 力扣(LeetCode)
2. 用队列实现栈。
225. 用队列实现栈 - 力扣(LeetCode)
3. 用栈实现队列。
232. 用栈实现队列 - 力扣(LeetCode)
4. 设计循环队列。
622. 设计循环队列 - 力扣(LeetCode)
4.概念选择题
选择题
1. 一个栈的初始次出栈,则元素出栈的顺序是(A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA2. 若进栈序列为A 1,4,3,2B 2,3,4,1C 3,1,4,2D 3,4,2,13. 循环队列的存储空间为 Q(1:100) ,初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后, front=rear=99 ,则循环队列中的元素个数为( )A 1B 2C 99D 0 或者 1004. 以下 ( ) 不是队列的基本运算?A 从队尾插入一个新元素B 从队列中删除第 i 个元素C 判断一个队列是否为空D 读取队头元素的值5. 现有一循环队列,其队头指针为 front ,队尾指针为 rear ;循环队列长度为 N 。其队内有效长度为? ( 假设队头不存放数据 )A (rear - front + N) % N + 1B (rear - front + N) % NC ear - front) % (N + 1)D (rear - front + N) % (N - 1)
答案
1.B2.C3.D4.B5.B