?? ?? 博客:小怡同學(xué)
?? ?? 個人簡介:編程小萌新
?? ?? 如果博客對大家有用的話，請點贊關(guān)注再收藏 ??
力扣習(xí)題
- 括號匹配問題。
- 用隊列實現(xiàn)棧。
- 用棧實現(xiàn)隊列。
- 設(shè)計循環(huán)隊列。
- 有效的括號
//用棧來實現(xiàn)
//左括號進(jìn)棧 右括號出棧并銷毀如果不匹配則return
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
typedef char SDatetype;
typedef struct Stack
{
SDatetype* a;
int top;
int capacity;
}Stack;
void StackInit(Stack* pq);
void StackDestory(Stack* pq);
void StackPush(Stack* pq, SDatetype x);
void StackPop(Stack* pq);
bool StackEmpty(Stack* pq);
SDatetype StackTop(Stack* pq);
int StackSize(Stack* pq);
bool StackEmpty(Stack* pq)
{
assert(pq);
return pq->top == 0;
}
void StackInit(Stack* pq)
{
assert(pq);
pq->a = NULL;
pq->capacity = 0;
pq->top = 0;
}
void StackDestory(Stack* pq)
{
assert(pq);
pq->capacity = 0;
pq->top = 0;
free(pq->a);
pq->a =NULL;
}
void StackPush(Stack* pq, SDatetype x)
{
assert(pq);
if (pq->top == pq->capacity)
{
int newcapacity = (pq->top == 0 ? 4 : (pq->capacity) * 2);
pq->a = (SDatetype*)realloc(pq->a,sizeof(SDatetype) * newcapacity);
if (pq->a == NULL)
{
perror("malloc fail");
exit(-1);
}
pq->capacity = newcapacity;
}
pq->a[pq->top++] = x;
}
void StackPop(Stack* pq)
{
assert(pq);
assert(!StackEmpty(pq));
pq->top--;
}
SDatetype StackTop(Stack* pq)
{
assert(pq);
assert(!StackEmpty(pq));
return pq->a[pq->top-1];
}
int StackSize(Stack* pq)
{
assert(pq);
return pq->top;
}
bool isValid(char * s){
Stack pq;
StackInit(&pq);
while(*s)
{
if(*s== '(' || *s == '[' || *s == '{')
{
StackPush(&pq, *s);//進(jìn)棧
}
else
{
if(StackEmpty(&pq))//如果只有一個左括號 無法匹配則return
{
StackDestory(&pq);
return false;
}
char tmp = StackTop(&pq);
StackPop(&pq);
if( (tmp != '(' && *s == ')' )||
(tmp != '[' && *s == ']' )||
(tmp != '{' && *s == '}'))//如果有一對不匹配則return
{
StackDestory(&pq);//return之前需要銷毀棧 以免內(nèi)存泄漏
return false;
}
}
s++;
}
bool tmp = StackEmpty(&pq);//當(dāng)棧里還有元素時則匹配失敗
StackDestory(&pq);
return tmp;
}
225. 用隊列實現(xiàn)棧（力扣）
//設(shè)置兩個隊列，入棧向有元素的隊列加入， 出棧（因為棧上后進(jìn)先出）所以需要把有元素的隊列依次移入另一個隊列 再刪除
typedef int QDatetype;
typedef struct Qnode
{
int* next;
QDatetype x;
}Qnode;
typedef struct Queue
{
Qnode* head;
Qnode* tail;
}Queue;
typedef struct {
Queue Qtwo;
Queue Qone;
} MyStack;
void QueueInit(Queue* pq)
{
assert(pq);
pq->tail = pq->head = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
while (pq->head)
{
Qnode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
void QueuePush(Queue* pq, QDatetype q)
{
assert(pq);
Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
newnode->next = NULL;
newnode->x = q;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if(pq->head == pq->tail)
{
free(pq->head);
pq->head = pq->tail= NULL;
}
else
{
Qnode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
QDatetype QueueTop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->x;
}
int QueueSize(Queue* pq)
{
assert(pq);
Qnode* head = pq->head;
int size = 0;
while (head)
{
size++;
head = head->next;
}
return size;
}
QDatetype QueueTail(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->x;
}
//創(chuàng)造一個由隊列創(chuàng)建的棧
MyStack* myStackCreate() {
MyStack* pq = (MyStack*)malloc(sizeof(MyStack));
//向堆申請空間不會隨棧的銷毀而銷毀
QueueInit(&pq->Qtwo);
QueueInit(&pq->Qone);
return pq;
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->Qone) && QueueEmpty(&obj->Qtwo);
}
void myStackPush(MyStack* obj, int x) {
Queue* one = &obj-> Qone;
Queue* two = &obj-> Qtwo;
if(!QueueEmpty(one))
{
QueuePush(one, x);
}
else
{
QueuePush(two,x);
}
}
int myStackPop(MyStack* obj) {
Queue* noempty = &obj-> Qone;
Queue* empty = &obj-> Qtwo;
if(!QueueEmpty(empty) )
{
empty = &obj->Qone;
noempty = &obj->Qtwo;
}
while(QueueSize(noempty) >1)
{
QueuePush(empty, QueueTop(noempty));
QueuePop(noempty);
}
int x = QueueTop(noempty);
QueuePop(noempty);
return x;
}
int myStackTop(MyStack* obj) {
Queue* one = &obj-> Qone;
Queue* two = &obj-> Qtwo;
if(!QueueEmpty(one))
{
return QueueTail(one);
}
else
{
return QueueTail(two);
}
}
void myStackFree(MyStack* obj) {
QueueDestory(&obj->Qone);
QueueDestory(&obj->Qtwo);
free(obj);
}
myStackPop函數(shù)的功能實現(xiàn)圖
232. 用棧實現(xiàn)隊列（力扣）
//與用隊列實現(xiàn)棧的思想不同， 這里的棧分別是push棧 和pop棧 （專門用來插入數(shù)據(jù)和刪除數(shù)據(jù)）
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
typedef int SDatetype;
typedef struct Stack
{
int* a;
int top;
int capacity;
}Stack;
bool StackEmpty(Stack* pq)
{
return pq->top == 0;
}
int StackSize(Stack* pq)
{
return pq->top;
}
void StackInit(Stack* pq)
{
assert(pq);
pq->a = NULL;
pq->capacity = 0;
pq->top = 0;
}
void StackDestory(Stack* pq)
{
assert(pq);
pq->capacity = 0;
pq->top = 0;
free(pq->a);
}
void StackPush(Stack* pq, SDatetype x)
{
assert(pq);
if (pq->top == pq->capacity)
{
int newcapacity = (pq->top == 0 ? 4 : (pq->capacity) * 2);
pq->a = (SDatetype*)realloc(pq->a,sizeof(SDatetype) * newcapacity);
if (pq->a == NULL)
{
perror("malloc fail");
return;
}
pq->capacity = newcapacity;
}
pq->a[pq->top++] = x;
}
void StackPop(Stack* pq)
{
assert(pq);
assert(!StackEmpty(pq));
pq->a[pq->top--];
}
SDatetype StackTop(Stack* pq)
{
assert(pq);
assert(!StackEmpty(pq));
return pq->a[pq->top-1];
}
typedef struct {
Stack push;
Stack pop;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* pq =(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&pq->push);
StackInit(&pq->pop);
return pq;
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->push, x);
}
//這個函數(shù)主要功能實現(xiàn)的是 出隊的元素是誰
//有兩種情況：
//1.pop棧中有元素，直接出隊
//2.pop棧中無元素, 需要把push棧中移入到pop棧里
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->pop))
{
while(!StackEmpty(&obj->push))
{
StackPush(&obj->pop ,StackTop(&obj->push));
StackPop(&obj->push);
}
}
return StackTop(&obj->pop);
}
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
StackPop(&obj->pop);
return front;
}
void myQueueFree(MyQueue* obj) {
StackDestory(&obj->push);
StackDestory(&obj->pop);
free(obj);
}
myQueuePop主要功能圖
622. 設(shè)計循環(huán)隊列
//主要是用順序表存儲數(shù)據(jù)
//不用鏈表實現(xiàn)是因為1.找尾不容易找到，2，鏈表是否存滿不好判斷文章來源：http://www.zghlxwxcb.cn/news/detail-514664.html
typedef struct {
int front;
int rear ;
int k;
int* a;
} MyCircularQueue;
//公開辟（k+1）個空間 判斷是否判空
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* pq = ( MyCircularQueue*)malloc(sizeof( MyCircularQueue));
pq->front = pq->rear= 0;
pq->k = k;
pq->a = (int*)malloc(sizeof(int)*(k+1));
return pq;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->rear == obj->front ;
}
//rear+1 = front則鏈表滿了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear +1) % (obj->k+1) == (obj->front);
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (!myCircularQueueIsFull(obj))
{
obj->a[obj->rear] = value;
obj->rear = (++obj->rear % (obj->k+1));//rear++之后下標(biāo)不能大于k+1，所以%（k+1）
return true;
}
return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
++obj->front;
obj->front = obj->front%(obj->k+1);
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(!myCircularQueueIsEmpty(obj))
{
return obj->a[obj->front];
}
else
{
return -1;
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(!myCircularQueueIsEmpty(obj))
{
return obj->a[(obj->rear-1 + obj->k+1)%(obj->k+1)] ;
//rear--之后下標(biāo)不能小于0
}
else
{
return -1;
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a = NULL;
free(obj);
obj = NULL;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-514664.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法系列之習(xí)題練習(xí)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
