栈
1.栈的表示和实现
1.1栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵循后进先出LIFO(Last In First Out)的原则
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。入数据也在栈顶。
栈有两种实现方式:数组、链表
- 数组:相当于之前顺序表的尾插,尾插用尾去做了栈顶,非常合适。唯一缺陷就是:空间不够需要增容
链表
- 单链表:使用单链表就优点不合适了,除非将链表的链尾当作栈底、链头当栈顶。栈顶插入就等于链表头插入O(1)
- 双链表:如果用尾做栈顶,那么就要用双向链表更好。效率O(1)
**但一般栈的实现都会使用数组来实现**(数组的cpu缓存命中要略高一些(**预加载**))
声名:
#define _CRT_SECURE_NO_WARNINGS 1
#ifndef _TEST_H
#define _TEST_H
//栈的链式存储结构;
typedef struct Node //创建一种类型的节点;
{
int data;
struct Node * pnext;
}NODE, *PNODE;
typedef struct Stack //创建一个栈类型,里面含有两个指针,一个指向栈顶,一个指向栈底
{
PNODE ptop;
PNODE pBottom;
}STACK, *PSTACK;
void init(PSTACK ps);//初始化栈
void push(PSTACK ps, int val);//压栈
void traverse(PSTACK ps);//遍历栈
bool empty(PSTACK ps);//判断栈是否为空
bool pop(PSTACK ps, int * pval);//出栈
void clear(PSTACK ps);//清空栈
#endif //_TEST_H
具体实现:
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>
#include "test.h"
int main()
{
//int val;//保存出栈的元素
STACK S;//定义一个栈变量
init(&S);//初始化这个栈
push(&S, 1);//压栈
push(&S, 2);
push(&S, 3);
push(&S, 4);
push(&S, 5);
push(&S, 6);
traverse(&S);//遍历
/*if (pop(&S, &val))//出栈
{
printf("出栈成功!出栈元素为%d \n", val);
printf("-------------------------------------------------------\n");
}
else
{
printf("出栈失败!\n");
}*/
//traverse(&S);
clear(&S);//清空
printf("-------------------------------------------------------\n");
printf("清空后栈中元素为:");
printf("栈中元素为:\n");
traverse(&S);
//free(S);//销毁栈
system("pause");
return 0;
}
void init(PSTACK ps)
{
ps->ptop = (PNODE)malloc(sizeof(NODE));//创建一个空栈
if (NULL == ps->ptop)
{
printf("success\n");
exit(-1);
}
else
{
ps->pBottom = ps->ptop;//栈底指针跟栈顶指针都指向这个新建的空节点
ps->ptop->pnext = NULL;
}
}
void push(PSTACK ps, int val)//压栈
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));//新建一个节点
pNew->data = val;//新节点数据域等于val
pNew->pnext = ps->ptop;//新节点指针域指向栈顶指针所指向的节点,就是前面栈底跟栈顶同时指向的空节点,这样就实现压栈了
ps->ptop = pNew;//然后栈顶元素上移,始终指向就是最后入栈的节点
}
void traverse(PSTACK ps)//遍历
{
PNODE p = ps->ptop;//遍历是从栈顶依次输出,所以创建一个指针,指向栈顶指针所指向的节点
while (p!=ps->pBottom)//当p所指向的节点不是栈底指针指向的节点时
{
printf("%d\n", p->data);//输出p所指向的节点的数据域的值
p = p->pnext;//然后指针p重新指向下一个节点
}
}
//bool pop(PSTACK ps, int * pval)//出栈一个元素
//{
// if (empty(ps))//先判断栈是否为空
// {
// return false;
// }
// else//不为空时
// {
// PNODE r = ps->ptop;//创建一个新的指针r,指向栈顶指针所指向的节点
// *pval = r->data;//将该节点的数据域赋值给val
// ps->ptop = r->pnext;//栈顶指针重新指向r所指向的下一个节点,
// free(r);//释放r所指向的节点,就是刚才的栈顶节点
// r = NULL;//清空
// return true;
// }
//}
bool empty(PSTACK ps)//判断栈是否为空
{
if (ps->ptop == ps->pBottom)
return true;
else
return false;
}
void clear(PSTACK ps)//清空栈内元素
{
if (empty(ps))
{
return ;
}
else
{
PNODE p = ps->ptop;//创建一个指针,指向当前栈顶指针指向的节点
PNODE q = NULL;//创建一个中间指针
while (p!=ps->pBottom)//当p所指向的节点不是栈底指针所指向的节点时
{
q = p->pnext;//先将p所指向的下一个节点赋给q
free(p);//然后删除该节点
p = q;//然后将q指向的节点赋给p,也就是p重新指向了p的下一个节点
}
ps->ptop = ps->pBottom;//循环完了之后,栈底指针跟栈底指针指向同一个节点
}
}
2.队列
2.1队列的概率及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First in First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
2.2队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数据的结构,出队列在数组头上出数据,效率会比较低。
记住两个公式:队列中,队列满的条件是:(rear+1)%QueueSize=front;
队列长度公式是:(rear-front+QueueSize)%QueueSize。
#pragma once #include <stdio.h> #include <stdbool.h> #include<assert.h> #include<stdlib.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { //这样的好处就是消除二级指针 QNode* tail; QNode* head; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); //规定:队尾入 void QueuePush(Queue* pq, QDataType x); //队头出 void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq);
3.栈和队列OJ题
1.括号匹配问题。(力扣搜索)
2.用队列实现栈。
3.用栈实现队列。