我要评论【数据结构】初探数据结构面纱：栈和队列全面剖析
🔥个人主页：大白的编程日记
🔥专栏：数据结构
文章目录
前言
一.栈
1.1栈的概念及结构
栈是一种遵循后进先出的结构。类似生活中我们生活中的弹夹，羽毛球桶等等。
-
入栈
入栈就是往栈顶增添数据
-
出栈
出栈就是在栈顶删除元素
1.2栈的结构选择
- 数组
我们可以用数组实现栈用下标控制栈顶元素的入栈和出栈
- 单链表
单链表其实不好实现栈，因为出栈时会修改上一个节点的指针。但单链表无法找到上一个节点。
所以我们把栈顶放在左边，栈顶是头节点，这样入栈出栈都可以。不需要修改上一个节点。
- 双向链表
为了解决单链表找上一个节点的问题，我们可以用双向链表来解决。
1.3栈的实现
- 栈的定义
我们先定义一个栈结构体，里面放有栈数组的指针。top是栈顶元素的下标。capacity则是栈数组现在的空间大小。
typedef int stdatatype;
typedef struct stack
{
stdatatype* a;
int top;
int capacity;
}st;
- 栈的初始化
我们先断言一下。然后把空间大小和top都初始化为0。
top的初始化有两种方式
void stinit(st* pst)
{
assert(pst);
pst->a = null;
pst->capacity = pst->top = 0;//指向栈顶元素的下一个
}
一种是初始化为-1，代表top指向栈顶元素。为什么要给-1呢？
因为如果给0的话，当栈为空时，0既能表示栈为空也能代表栈有一个元素，下标为0。所以初始化要给-1。
第二种就是初始化给0，代表top指向栈顶元素的下一个位置。
- 栈的销毁
栈的销毁我们先free销毁数组，然后再给数组指针给空。
top和capacity都给0表示栈为空。
void stdestroy(st* pst)
{
assert(pst);
free(pst->a);
pst->a = null;
pst->capacity = pst->top = 0;
}
- 入栈
入栈我们需要先对栈判满，如果满了我们就扩容到原来的2倍。
如果没开空间就先开4个空间。当我们没开空间时,a是空指针，此时realloc相当与malloc。然后再更新a和capacity。赋值x，top++。
void stpush(st* pst, stdatatype x)
{
assert(pst);
if (pst->capacity == pst->top)//栈满了
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;//未开空间就给4个空间，否则就在原来的空间扩容两倍
stdatatype* tmp = (stdatatype*)realloc(pst->a,sizeof(stdatatype)*newcapacity);
if (tmp == null)
{
perror("realloc fail~");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top++] = x;//赋值 top++
}
- 出栈
出栈我们只需要控制top，让top–即可。
void stpop(st* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
- 获取栈顶元素
因为我们top是指向栈顶元素的下一个，所以我们返回下标为top-1的元素
stdatatype sttop(st* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top-1];
}
- 判空
top等于0时就是空。
bool stempty(st* pst)
{
assert(pst);
return 0 == pst->top;
}
- 栈的元素个数
因为我们的top指向栈顶元素的下一个，就相当于栈的元素个数size。
我们直接返回top即可。
int stsize(st* pst)
{
assert(pst);
return pst->top;
}
- 栈的遍历
栈在遍历的时候先获取栈顶元素，然后在出栈。直到栈为空。
int main()
{
st s;
stinit(&s);
stpush(&s, 1);
stpush(&s, 2);
stpush(&s, 3);
stpush(&s, 4);
while (!stempty(&s))
{
printf("%d ", sttop(&s));
stpop(&s);
}
stdestroy(&s);
return 0;
}
注意栈有可能边入边出，这时的输出结果顺序就不是与与输入顺序相反了
int main()
{
st s;
stinit(&s);
stpush(&s, 1);
stpush(&s, 2);
printf("%d ", sttop(&s));
stpop(&s);
stpush(&s, 3);
stpush(&s, 4);
while (!stempty(&s))
{
printf("%d ", sttop(&s));
stpop(&s);
}
stdestroy(&s);
return 0;
}
1.4栈oj
-题目
有效的括号
-
思路分析
让左括号入栈，右括号与左括号匹配。
-
代码实现
typedef char stdatatype;
typedef struct stack
{
stdatatype* a;
int top;
int capacity;
}st;
void stinit(st* pst)
{
assert(pst);
pst->a = null;
pst->capacity = pst->top = 0;
}
void stdestroy(st* pst)
{
assert(pst);
free(pst->a);
pst->a = null;
pst->capacity = pst->top = 0;
}
void stpush(st* pst, stdatatype x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
stdatatype* tmp = (stdatatype*)realloc(pst->a,sizeof(stdatatype)*newcapacity);
if (tmp == null)
{
perror("realloc fail~");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top++] = x;
}
void stpop(st* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
stdatatype sttop(st* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top-1];
}
bool stempty(st* pst)
{
assert(pst);
return 0 == pst->top;
}
int stsize(st* pst)
{
assert(pst);
return pst->top;
}
bool isvalid(char* s)
{
st t;
stinit(&t);
while(*s)
{
if(*s=='('||*s=='['||*s=='{')
{
stpush(&t,*s);//左括号入栈
}
else
{
if(stempty(&t))//没有左括号匹配
{
return false;
}
char tmp=sttop(&t);//获取栈顶元素匹配
stpop(&t);
if(*s==')'&&tmp!='('
||*s=='}'&&tmp!='{'
||*s==']'&&tmp!='[')//匹配
{
return false;
}
}
s++;
}
bool ret=stempty(&t);//判空
stdestroy(&t);
return ret;
}
- 题目
用栈实现队列
- 思路分析
因为栈导数据到另一个栈后，数据相反。由后进先出边先进先出。所以我们固定一个栈入数据，一个栈出数据即可。 - 代码实现
typedef int stdatatype;
typedef struct stack
{
stdatatype* a;
int top;
int capacity;
}st;
void stinit(st* pst)
{
assert(pst);
pst->a = null;
pst->capacity = pst->top = 0;
}
void stdestroy(st* pst)
{
assert(pst);
free(pst->a);
pst->a = null;
pst->capacity = pst->top = 0;
}
void stpush(st* pst, stdatatype x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
stdatatype* tmp = (stdatatype*)realloc(pst->a,sizeof(stdatatype)*newcapacity);
if (tmp == null)
{
perror("realloc fail~");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top++] = x;
}
void stpop(st* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
stdatatype sttop(st* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top-1];
}
bool stempty(st* pst)
{
assert(pst);
return 0 == pst->top;
}
int stsize(st* pst)
{
assert(pst);
return pst->top;
}
typedef struct {
st pushst;
st popst;
} myqueue;
myqueue* myqueuecreate() {
myqueue* pq=malloc(sizeof(myqueue));
stinit(&pq->pushst);
stinit(&pq->popst);
return pq;
}
void myqueuepush(myqueue* obj, int x) {
stpush(&obj->pushst,x);
}
int myqueuepeek(myqueue* obj) {
if(stempty(&obj->popst))
{
while(!stempty(&obj->pushst))
{
int top=sttop(&obj->pushst);
stpush(&obj->popst,top);
stpop(&obj->pushst);
}
}
int top=sttop(&obj->popst);
return top;
}
int myqueuepop(myqueue* obj) {
int ret=myqueuepeek(obj);
stpop(&obj->popst);
return ret;
}
bool myqueueempty(myqueue* obj) {
return stempty(&obj->pushst)&&stempty(&obj->popst);
}
void myqueuefree(myqueue* obj) {
stdestroy(&obj->pushst);
stdestroy(&obj->popst);
free(obj);
obj=null;
}
二. 队列
2.1队列的概念及结构
与栈相反，队列遵循先进先出的原则。只能在队尾入数据，队头出数据。
2.2队列的应用
- 抽号机
我们平时在日常生活中都会遇到取票排队。取票后我们就把票数尾插到抽号机里，要取票时我们就在队头出数据。这样就能保证先取票的先出号。
- 好友推荐
队列还可以做好友推荐。也就是广度优先遍历（dfs）。
2.3队列的选择
-
顺序表
顺序表不好实现队列。因为队列是队头出数据，顺序表头删需要挪动数据。 -
双向链表
双向链表其实实现啥都好。但是双向链表多开一个指针，浪费内存。还要多维护一个指针。 -
单链表
单链表实现队列非常合适。因为队列在队尾入数据，队头出数据。单链表头删和尾删都不需要上一个节点。
所以我们用单链表实现。
2.4队列的实现
- 队列结构体
我们先定义一个队列节点的结构体，然后在用一个头指针，一个尾指针，和一个size维护整个队列。
typedef struct queuenode
{
struct queuenode* next;
qdatatype val;
}qnode;
typedef struct queue
{
qnode* phead;
qnode* ptail;
int size;
}queue;
- 队列的初始化
我们把头指针和尾指针都初始化为空，size初始化为0.
void queueinit(queue* pq)
{
assert(pq);
pq->phead = pq->ptail = null;
pq->size = 0;
}
- 队列的销毁
我们创建一个cur指针指向头节点，然后遍历销毁即可。注意要先保存下一个节点在销毁当前节点，然后移动cur即可。最后让头指针尾指针指向空。size为0即可。
void queuedestroy(queue* pq)
{
assert(pq);
qnode* cur = pq->phead;
while (cur)
{
qnode* next = cur->next;
free(cur);
cur = next;
};
pq->phead = pq->ptail = null;
pq->size = 0;
}
- 队列的插入
我们malloc一个节点。因为是尾插，所以让节点指向空。赋值为x。如果没有节点，那头节点和尾节点都是指向新节点。否则尾插在尾节点后。新节点成为新的尾节点。最后size++。
void queuepush(queue* pq, qdatatype x)
{
assert(pq);
qnode* node = (qnode*)malloc(sizeof(qnode));
if (node == null)
{
perror("malloc fail");
return;
}
node->next = null;
node->val = x;
if (pq->phead == null)//没有节点
{
pq->phead = pq->ptail = node;
}
else//至少有一个节点
{
pq->ptail->next = node;
pq->ptail = node;
}
pq->size++;
}
-获取队头元素
我们先断言一下判断队列是否为空，然后返回队头节点元素的值。
qdatatype queuefron(queue* pq)
{
assert(pq);
assert(pq->size != 0);
return pq->phead->val;
}
- 获取队尾元素
我们先断言一下判断队列是否为空，然后返回队尾节点元素的值。
qdatatype queueback(queue* pq)
{
assert(pq);
assert(pq->size != 0);
return pq->ptail->val;
}
- 队头的删除
我们先断言一下判断队列是否为空，然后分两种情况
第一种情况，当队列只有一个节点时。
队头指针和队尾指针都指向空，size–。
第二种情况，当队列不是一个节点时。
保存队头节点的下一个节点，释放头节点，保存的节点成为新的头节点。size–。
void queuepop(queue* pq)
{
assert(pq);
assert(pq->size != 0);
if (pq->phead == pq->ptail)//只有一个节点
{
free(pq->phead);
pq->phead = pq->ptail = null;
pq->size--;
}
else
{
qnode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
pq->size--;
}
}
- 队列的判空
判断size是否为0即可
bool queueempty(queue* pq)
{
assert(pq);
return pq->size == 0;
}
- 队列的元素个数
因为我们前面用size记录了个数，直接返回size即可。
防止遍历找.实现o(1).
int queuesize(queue* pq)
{
assert(pq);
return pq->size;
}
- 队列的遍历
队列的遍历就是获取队头元素，然后删除队头元素直到队列为空。
int main()
{
queue q;
queueinit(&q);
queuepush(&q, 1);
queuepush(&q, 2);
queuepush(&q, 3);
queuepush(&q, 4);
while (q.size)
{
printf("%d ", queuefron(&q));
queuepop(&q);
}
queuedestroy(&q);
return 0;
}
注意不论是否边入边出。队列输出的顺序都与入队列顺序一致。
int main()
{
queue q;
queueinit(&q);
queuepush(&q, 1);
queuepush(&q, 2);
printf("%d ", queuefron(&q));
queuepop(&q);
printf("%d ", queuefron(&q));
queuepop(&q);
queuepush(&q, 3);
queuepush(&q, 4);
while (q.size)
{
printf("%d ", queuefron(&q));
queuepop(&q);
}
queuedestroy(&q);
return 0;
}
2.5队列oj
-
题目
用队列实现栈
-
思路分析
我们保持一个队列有数据，一个队列没数据。
出栈时，往空队列导入数据即可拿到栈顶元素。
-
代码实现
typedef int qdatatype;
typedef struct queuenode
{
struct queuenode* next;
qdatatype val;
}qnode;
typedef struct queue
{
qnode* phead;
qnode* ptail;
int size;
}queue;
void queueinit(queue* pq)
{
assert(pq);
pq->phead = pq->ptail = null;
pq->size = 0;
}
void queuedestroy(queue* pq)
{
assert(pq);
qnode* cur = pq->phead;
while (cur)
{
qnode* next = cur->next;
free(cur);
cur = next;
};
pq->phead = pq->ptail = null;
pq->size = 0;
}
void queuepush(queue* pq, qdatatype x)
{
assert(pq);
qnode* node = (qnode*)malloc(sizeof(qnode));
if (node == null)
{
perror("malloc fail");
return;
}
node->next = null;
node->val = x;
if (pq->phead == null)
{
pq->phead = pq->ptail = node;
}
else
{
pq->ptail->next = node;
pq->ptail = node;
}
pq->size++;
}
qdatatype queuefron(queue* pq)
{
assert(pq);
assert(pq->size != 0);
return pq->phead->val;
}
qdatatype queueback(queue* pq)
{
assert(pq);
assert(pq->size != 0);
return pq->ptail->val;
}
bool queueempty(queue* pq)
{
assert(pq);
return pq->size == 0;
}
void queuepop(queue* pq)
{
assert(pq);
assert(pq->size != 0);
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = null;
pq->size--;
}
else
{
qnode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
pq->size--;
}
}
//统计个数
int queuesize(queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct {
queue q1;
queue q2;
} mystack;
mystack* mystackcreate() {
mystack* q=(mystack*)malloc(sizeof(mystack));
queueinit(&(q ->q1));
queueinit(&(q->q2));
return q;
}
void mystackpush(mystack* obj, int x) {
if(!queueempty(&obj->q1))//往不为空的队列入数据
{
queuepush(&obj->q1,x);
}
else
{
queuepush(&obj->q2,x);
}
}
int mystackpop(mystack* obj) {
queue* empty=&obj->q1;
queue* noempty=&obj->q2;
if(!queueempty(&obj->q1))
{
noempty=&obj->q1;
empty=&obj->q2;
}//假设法
while(queuesize(noempty)>1)//数据入队列直到剩下一个数据
{
queuepush(empty,queuefron(noempty));
queuepop(noempty);
}
int top=queuefron(noempty);
queuepop(noempty);
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);//销毁队列1
queuedestroy(&obj->q2);//销毁队列2
free(obj);//销毁结构体
obj=null;
}
- 题目
- 思路分析
主要就是回绕的问题和假溢出的问题
- 队列结构体
这里我们用一个数组指针指向队列，一个head和tail控制队列的头和尾。在记录一个k表示循环队列长度。
typedef struct {
int* a;
int head;
int tail;
int k;
} mycircularqueue;
- 队列初始化
malloc一个队列结构体，在malloc一个队列。k+1多开一个空间解决假溢出问题。然后初始化head和tail为0。赋值k。
mycircularqueue* mycircularqueuecreate(int k) {
mycircularqueue* pq=(mycircularqueue*)malloc(sizeof(mycircularqueue));
pq->a=(int*)malloc(sizeof(int)*(k+1));
pq->head=0;
pq->tail=0;
pq->k=k;
return pq;
}
- 队列判空
当head==tail时队列为空
bool mycircularqueueisempty(mycircularqueue* obj) {
return obj->head==obj->tail;
}
- 队列判满
当(tail+1)%(k+1)==head时为满。
%(k+1)是为了解决回绕的问题。
bool mycircularqueueisfull(mycircularqueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->head;
}
- 队列的插入
先判断队列是否为满。如果不满就直接在tail的位置插入，然后tail+1继续%k+1解决回绕。
bool mycircularqueueenqueue(mycircularqueue* obj, int value) {
if (!mycircularqueueisfull(obj))
{
obj->a[obj->tail] = value;
obj->tail = (obj->tail + 1) % (obj->k + 1);
return true;
}
return false;
}
- 队列的删除
先判空。队列的删除直接让head+1%k+1解决回绕即可。
bool mycircularqueuedequeue(mycircularqueue* obj) {
if (!mycircularqueueisempty(obj))
{
obj->head = (obj->head + 1) % (obj->k + 1);
return true;
}
return false;
}
- 队列的队头元素
先判空。不为空直接返回下标为head的值
int mycircularqueuefront(mycircularqueue* obj) {
if(mycircularqueueisempty(obj))
{
return -1;
}
return obj->a[obj->head];
}
- 队列的队尾元素
int mycircularqueuerear(mycircularqueue* obj) {
if(mycircularqueueisempty(obj))
{
return -1;
}
return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];
}
正常情况我们可以直接返回下标为tail-1的值。可是会有越界的情况
- 队列的销毁
先把队列数组销毁，然后销毁队列结构体即可。
void mycircularqueuefree(mycircularqueue* obj) {
free(obj->a);
obj->a=null;
free(obj);
obj=null;
}
发表评论