今天是高木同学哦~
栈
栈的基本概念
栈:栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端被称为栈底。栈中的数据元素遵守后进先出(LIFO)的原则。
压栈:栈的插入操作叫做压栈
出栈:栈的删除操作叫做出栈
栈的实现
栈的实现一般可以使用数组或者链表实现,相对于来说,栈的实现使用数组更优。
头文件定义
实现动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//栈顶
int capacity;//最大容量
}ST;
//栈的初始化
void StackInit(ST* ps);
//栈的销毁
void StackDestory(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
//求栈顶
STDataType StackTop(ST* ps);
//栈的大小
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps)
接口实现
栈初始化
void StackInit(ST* ps)
{
assert(ps);
ps->a=(STDataType*)malloc(sizeof(STDataType)*4);
if(ps->a==NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity=4;
ps->top=0;
}
栈的销毁
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a=NULL;
ps->top=ps->capacity=0;
}
压栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if(ps->top==ps->capacity)
{
STDataType*tmp=(STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
if(tmp==NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a=tmp;
ps->capacity*=2;
}
}
出栈
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top >0);
ps->top--;
}
栈顶
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
求栈的大小
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
判断栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
用python实现栈
class Stack:
def __init__(self):
self.items=[]
def isEmpty(self):
return self.items==[]
def push(self,item)
self.items.appead(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
题目链接
class Solution:
def isValid(self, s: str) -> bool:
dic = {')':'(',']':'[','}':'{'}
stack = []
for i in s:
if stack and i in dic:
if stack[-1] == dic[i]: stack.pop()
else: return False
else: stack.append(i)
return not stack
队列
队列的基本概念
队列:只允许在一端进行插入数据操作,另一端进行删除数据操作的特殊线性表,队列具有先进先出(FIFO)入队列:进行插入操作的一端称为队尾,进行删除操作的一端称为对头
队列的实现
头文件定义
使用链表实现队列
typedef int QDataType
typedef struct QListNode
{
QListNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}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);
接口定义
队列初始化
void QueueInit(Queue* pq)
{
assert(pq);
ps->head=ps->tail=NULL;
}
队列的销毁
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur=pq->head;
while(cur)
{
QNode* next=cur->next;
free(cur);
cur=next;
}
pq->head=pq->tail=NULL;
}
入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode=(QNode*)malloc(sizeof(QNode));
if(pq==NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data=x;
newnode->next=NULL;
//当原队列为空时
if(pq->tail==NULL)
{
pq->tail=pq->head=newnode;
}
else
{
//原队列的tai指针是链表的最后一个指针
pq->tail->next=newnode;
pq->tail=newnode;
}
}
出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);
//队列中只有一个元素
if(pq->head->next)
{
free(pq->head);
pq->head=pq->tail=NULL;
}
else
{
QNode* newnode=pq->head->next;
free(pq->head);
pq->head=newnode;
}
}
调用队列头
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
调用队尾
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->tail->data;
}
调用队列大小
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QNode* cur = pq->head;
while (cur)
{
++size;
cur = cur->next;
}
return size;
}
判断为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
python实现队列
class Queue:
def __init__(self):
self.items=[]
def isEmpty(self):
return self.items==[]
def enqueue(self):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)