# 栈与队列练习题

## 有效的括号

typedef char TackDataType;
typedef struct Stack
{
TackDataType * a;
int top; //栈顶元素
int capacity;
}Stack;
//初始化
void TackInit(Stack *pst)
{
assert(pst);
pst->a = NULL;
pst->top = -1;
pst->capacity = 0;
}
// 入栈
void TackPush(Stack *pst, TackDataType elemest)
{
assert(pst);
//判断是否满了
if ((pst->top) +1 == pst->capacity)
{
pst->capacity = (pst->capacity == 0? 4 : pst->capacity * 2);
TackDataType* tmp = (TackDataType*)realloc(pst->a,sizeof(Stack) * pst->capacity);
if (tmp == NULL)
{
perror("realloc");
return;
}
pst->a = tmp;

}
pst->a[++(pst->top)] = elemest;

}
//出栈
void TackPop(Stack *pst)
{
assert(pst);
if(pst->top != -1)
pst->top--;
}
//长度
int TackSize(Stack *pst)
{
assert(pst);
return (pst->top) + 1;
}
//是否为空
bool TackEmpty(Stack *pst)
{
assert(pst);
return pst->top == -1;
}
//栈顶元素
TackDataType TackTop(Stack *pst)
{
assert(pst);
return pst->a[pst->top];
}
//释放
void TackDestroy(Stack *pst)
{
free(pst->a);
pst->a = NULL;
pst->top = -1;
pst ->capacity = 0;
}

bool isValid(char* s)
{
Stack pst;
//初始化
TackInit(&pst);
while(*s)
{
if(*s == '{' || *s == '[' || *s == '(')
{
//入栈
TackPush(&pst, *s);

}
else
{
//是否为空
if (TackEmpty(&pst))
{
TackDestroy(&pst);
return false;
}

//栈顶元素
if ((*s == '}' &&  TackTop(&pst) == '{')
|| (*s == ']' &&  TackTop(&pst) == '[')
||(*s == ')' &&  TackTop(&pst) == '('))
{
//出栈
TackPop(&pst);
}
else
{
return false;
}

}
s++;
}
//是否为空
if (!TackEmpty(&pst))
{
TackDestroy(&pst);
return false;
}
TackDestroy(&pst);
return true;

}


## 用队列实现栈

typedef int QDataType;
//链表节点
typedef struct QNode
{
QDataType val;
struct QNode *next;
}QNode;
//队列结构
typedef struct Queue
{
QNode* tail; //队尾
int size;
}Queue;

//创建两个队列
typedef struct
{
Queue stack1;
Queue stack2;

} MyStack;

MyStack* myStackCreate()
{
//创建两个队列
MyStack * Queuetack = (MyStack*)malloc(sizeof(MyStack));
//创建哨兵位
Queuetack->stack1.size = 0;
//创建哨兵位
Queuetack->stack2.size = 0;
return Queuetack;

}

void myStackPush(MyStack* obj, int x)
{
assert(obj);
if (obj->stack2.size)
{
//创建节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->val = x;
newnode->next = NULL;
//插入
obj->stack2.tail->next = newnode;
obj->stack2.tail = newnode;
obj->stack2.size++;
}
else
{
//创建节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->val = x;
newnode->next = NULL;
//插入
obj->stack1.tail->next = newnode;
obj->stack1.tail = newnode;
obj->stack1.size++;
}
}

int myStackPop(MyStack* obj)
{
if (!obj->stack2.size && !obj->stack1.size)
return 0;
if (obj->stack2.size)
{
{
obj->stack1.tail->next = node;
obj->stack1.tail = node;

obj->stack1.size++;

}
obj->stack1.tail->next = NULL;
int a = obj->stack2.tail->val;
free(obj->stack2.tail);
obj->stack2.size = 0;
return a;
}
else
{

{
obj->stack2.tail->next = node;
obj->stack2.tail = node;

obj->stack2.size++;

}
obj->stack2.tail->next = NULL;
int a = obj->stack1.tail->val;
free(obj->stack1.tail);
obj->stack1.size = 0;
return a;
}

}

int myStackTop(MyStack* obj)
{

if (!obj->stack2.size && !obj->stack1.size)
return 0;
if (!obj->stack2.size)
{
return obj->stack1.tail->val;
}
else
{
return obj->stack2.tail->val;
}
}

bool myStackEmpty(MyStack* obj)
{
return obj->stack2.size== 0 && obj->stack1.size ==0;
}

void myStackFree(MyStack* obj)
{
while(cur)
{
QNode *cur1 = cur->next;
free(cur);
cur = cur1;
}
obj->stack1.size = 0;
obj->stack1.tail = NULL;

while(cur)
{
QNode *cur1 = cur->next;
free(cur);
cur = cur1;
}
obj->stack2.size = 0;
obj->stack2.tail = NULL;
free(obj);
}


## 用栈实现队列

typedef int StackDAtaType;
typedef struct Stack
{
StackDAtaType *data;
int top;//栈顶元素下一个
int capacity;

}Stack;

typedef struct
{
Stack stack1;
Stack stack2;
} MyQueue;

MyQueue* myQueueCreate()
{
//初始化
MyQueue *queue = (MyQueue*)malloc(sizeof(MyQueue));
//第一个栈
queue->stack1.data = NULL;
queue->stack1.top = 0;//栈顶元素的下一个
queue->stack1.capacity = 0;
//第二个栈
queue->stack2.data = NULL;
queue->stack2.top = 0;
queue->stack2.capacity = 0;
return queue;
}

void myQueuePush(MyQueue* obj, int x)
{
//第一个栈插入
//判断是否满栈
if(obj->stack1.top == obj->stack1.capacity)
{
obj->stack1.capacity = (obj->stack1.capacity == 0 ? 4 : obj->stack1.capacity * 2);
StackDAtaType *tmp =  (StackDAtaType*)realloc(obj->stack1.data, sizeof(StackDAtaType) * obj->stack1.capacity);
if (tmp == NULL)
{
perror("realloc");
return ;
}
obj->stack1.data = tmp;
}
obj->stack1.data[obj->stack1.top++] = x;

}

int myQueuePeek(MyQueue* obj)
{
if(!obj->stack2.top && !obj->stack1.top)
return 0;
if(obj->stack2.top)
{
return obj->stack2.data[obj->stack2.top -1];
}
else
{
//取出第一栈的元素 插入到第二栈
while (obj->stack1.top)
{
//判断是否满栈
if (obj->stack2.top == obj->stack2.capacity)
{
obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);
StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);
if (tmp == NULL)
{
perror("realloc");
return   0;
}
obj->stack2.data = tmp;
}

obj->stack2.data[obj->stack2.top++] = obj->stack1.data[--obj->stack1.top];
}

return obj->stack2.data[obj->stack2.top - 1];

}

}

int myQueuePeek(MyQueue* obj)
{
if(!obj->stack2.top && !obj->stack1.top)
return 0;
if(obj->stack2.top)
{
return obj->stack2.data[obj->stack2.top -1];
}
else
{
//取出第一栈的元素 插入到第二栈
while (obj->stack1.top)
{
//判断是否满栈
if (obj->stack2.top == obj->stack2.capacity)
{
obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);
StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);
if (tmp == NULL)
{
perror("realloc");
return 0;
}
obj->stack2.data = tmp;
}

obj->stack2.data[obj->stack2.top++] = obj->stack1.data[--obj->stack1.top];
}

return obj->stack2.data[obj->stack2.top - 1];

}

}

bool myQueueEmpty(MyQueue* obj)
{
return obj->stack1.top == 0 && obj->stack2.top == 0;
}

void myQueueFree(MyQueue* obj)
{
free(obj->stack1.data);
obj->stack1.data = NULL;
obj->stack1.top = 0;
obj->stack1.capacity = 0;

free(obj->stack2.data);
obj->stack2.data = NULL;
obj->stack2.top = 0;
obj->stack2.capacity = 0;
free(obj);

}


## 循环队列

typedef struct
{
int *list;
int front;
int back;
int k;

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue * obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
obj->list = (int*)malloc(sizeof(int) * (k + 1)); //多开创一个空间
obj->front = 0;
obj->back = 0; //指向尾的下一个
obj->k = k + 1;
return obj;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if ((obj->back + 1) % (obj->k) != obj->front)
{
obj->list[obj->back] = value;
obj->back = (obj->back + 1 + obj->k) % (obj->k);
return true;
}
return false;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if (obj->back == obj->front)
return false;
obj->front = (obj->front + 1 + obj->k) % (obj->k);
return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
if(obj->back == obj->front)
return -1;
return obj->list[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj)
{
if(obj->back == obj->front)
return -1;
return obj->list[(obj->back-1 + obj->k) %(obj->k)];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->back == obj->front;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->back + 1) % (obj->k) == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->list);
free(obj);
}



typedef int DataType;
typedef struct ListNode1
{
DataType val;
struct ListNode1 *next;
} ListNode;
typedef struct
{
ListNode* back;
ListNode* tail;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k)
{
//创建一个循环队列
MyCircularQueue *obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->back = NULL;
obj->tail =NULL;
int i= 0;
for (i = 0; i < k+1; i++)
{
//创建节点
ListNode *newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->next = NULL;
if(obj->tail == NULL)
{
obj->back = newnode;
obj->tail = newnode;
}
else
{
obj->tail->next = newnode;
obj->tail = obj->tail->next;
}
}
obj->tail = obj->back;
return obj;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{

{
obj->back->val = value;
obj->tail = obj->back;
obj->back = obj->back->next;
return true;

}
return false;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
//为空返回false
{
return false;
}
return true;

}

int myCircularQueueFront(MyCircularQueue* obj)
{
{
return -1;
}

}

int myCircularQueueRear(MyCircularQueue* obj)
{
{
return -1;
}
return obj->tail->val;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
if(myCircularQueueRear(obj) == -1)
return true;
return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
{
return false;
}
return true;
}

void myCircularQueueFree(MyCircularQueue* obj)
{
ListNode *p = obj->tail->next;
while(obj->back != p)
{
ListNode *pnode = obj->back->next;
free(obj->back);
obj->back = pnode;
free(obj);
}

}


## 总结

|
4天前
|

【数据结构】栈和队列

10 1
|
4天前
【数据结构OJ题】用栈实现队列

10 0
|
4天前
【数据结构OJ题】用队列实现栈

15 0
|
22天前
|

26 2
|
18天前
|
API

15 0
|
18天前
|
JavaScript

19 0
|
21天前
|

22 0
|
22天前
|

15 0
|
28天前
|

【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
33 0
|
28天前
|

【数据结构】操作受限的线性表，栈的具体实现
【数据结构】操作受限的线性表，栈的具体实现
30 5