本文主要是几个OJ题的思路和代码（C实现）
包括：括号匹配问题,用队列实现栈,用栈实现队列,设计循环队列
1.括号匹配问题
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
思路：在栈中存放左括号，遇到右括号，则出栈顶元素，判断栈顶元素是否和当前括号匹配，如果不匹配，则说明不匹配。遍历完所有字符，如果栈为空，则表示完全匹配。
源码：(包括了栈的创建以及操作接口)
typedef char Stackdata;
struct Stack
{
Stackdata* a; //内容
int top; //顶
int capacity; //容量
};
typedef struct Stack Stack;
void StackInit(Stack* ps) // 初始化栈
{
assert(ps);
ps->a = (Stack*)malloc(sizeof(Stack) * 2); //给一个初始的空间方便后续翻倍
ps->capacity = 2; //容量
ps->top = 0; //栈顶
}
void StackDestroy(Stack* ps) // 销毁栈
{
assert(ps);
free(ps->a);
ps->top = ps->capacity = 0;
ps->a = NULL;
}
bool StackEmpty(Stack* ps) // 检测栈是否为空
{
assert(ps);
int a = ps->top;
if(a != 0)
{
return true;
}
else
{
return false;
}
}
void StackPush(Stack* ps, Stackdata data) // 入栈
{
assert(ps);
if (ps->top == ps->capacity)
{
ps->capacity *= 2;
Stack* tmp = (Stack*)realloc(ps->a, sizeof(Stack) * ps->capacity); //用中间变量更安全
if (tmp == NULL)
{
exit(-1);
}
ps->a = tmp;
}
ps->a[ps->top] = data;
ps->top++;
}
void StackPop(Stack* ps) // 出栈
{
assert(ps);
ps->top--;
}
Stackdata StackTop(Stack* ps) // 获取栈顶元素
{
assert(ps);
return ps->a[ps->top - 1]; //-1才是栈顶
}
int StackSize(Stack* ps) // 获取栈中有效元素个数
{
return ps->top == 0;
}
bool isValid(char * s)
{
Stack z;
StackInit(&z);
while(*s)
{
if(*s == '(' || *s == '{' || *s == '[')
{
StackPush(&z, *s);
++s;
}
else
{
if(StackEmpty(&z))
{
char* b = StackTop(&z);
if(b == '('&& *s != ')')
{
StackDestroy(&z);
return false;
}
else if(b == '['&& *s != ']')
{
StackDestroy(&z);
return false;
}
else if(b == '{'&& *s != '}')
{
StackDestroy(&z);
return false;
}
else
{
StackPop(&z);
++s; //访问下一个
}
}
else
{
return false;
}
}
}
int t = z.top;
StackDestroy(&z);
if(t == 0)
return true;
else
return false;
}
2.用队列实现栈
题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。实现 MyStack 类：void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
思路：用两个队列去实现一个栈，每次始终保持一个队列为空，入栈操作相当于给非空队列进行入队操作。出栈操作相当于非空队列的队尾元素出队，此时需要把非空队列除最后一个元素之外的其余元素入队到空队列，然后出队最后一个队尾元素。
源码：(包括了队列的创建以及操作接口)
typedef int QueueData;
struct QueueNode //链式结构：表示队列 (被操作的)
{
struct QueueNode* next;
QueueData val;
};
typedef struct QueueNode QueueN;
struct Queue // 队列的结构(头尾指针）
{
struct QueueNode* front; //要指向节点，所以结构是struct QueueNode*
struct QueueNode* back;
};
typedef struct Queue Queue;
QueueN* BuyQueueNode(QueueData x) //创建节点
{
QueueN* ret = (Queue*)malloc(sizeof(QueueN));
if (ret == NULL)
{
exit(-1);
}
ret->val = x;
ret->next = NULL;
return ret;
}
void QueueInit(Queue* q) // 初始化队列
{
assert(q);
q->back = NULL;
q->front = NULL;
}
void QueueDestroy(Queue* q) // 销毁队列
{
assert(q);
Queue* cur = q;
while (cur->front) //需要判断cur->front，cur永远不会为空
{
Queue* Next = cur->front->next;
free(cur->front);
cur->front = Next;
}
q->back = q->front = NULL;
}
void QueuePush(Queue* q, QueueData data) // 队尾入队列
{
assert(q);
QueueN* cur = BuyQueueNode(data);
if (q->front == NULL)
{
q->back = q->front = cur;
}
else //队尾进，对首出
{
q->back->next = cur;
q->back = cur;
}
}
void QueuePop(Queue* q) // 队头出队列
{
assert(q);
if (q->front == NULL)
{
return;
}
QueueN* Next = q->front->next;
free(q->front);
q->front = Next;
}
QueueData QueueFront(Queue* q) // 获取队列头部元素
{
assert(q);
if (q->front == NULL) //不用判断，为空时，返回空
return;
return q->front->val;
}
QueueData QueueBack(Queue* q) // 获取队列队尾元素
{
assert(q);
if (q->back == NULL)
return;
return q->back->val;
}
int QueueSize(Queue* q) // 获取队列中有效元素个数
{
assert(q);
int count = 0;
QueueN* cur = q->front;
while (cur)
{
cur = cur->next;
count++;
}
return count;
}
bool QueueEmpty(Queue* q) // 检测队列是否为空
{
return q->front == NULL;
}
typedef struct { //栈是由两个队列组成，在此定义
Queue q1;
Queue q2;
} MyStack;
/** Initialize your data structure here. */
MyStack* myStackCreate() {
MyStack* ret = (MyStack*)malloc(sizeof(MyStack)); //不能用MyStack ret 因为这样定义的是局部变量，要开辟空间。
QueueInit(&ret->q1); //初始化队列
QueueInit(&ret->q2);
return ret;
}
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) { //压入不是空的那个队列
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
Queue* pEmpty = &obj->q1, *pNonEmpty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
pEmpty = &obj->q2;
pNonEmpty = &obj->q1;
}
while(QueueSize(pNonEmpty) > 1)
{
QueuePush(pEmpty, QueueFront(pNonEmpty));
QueuePop(pNonEmpty);
}
// printf("%d\n",QueueBack(pNonEmpty));
int top = QueueFront(pNonEmpty);
//队尾元素出队
QueuePop(pNonEmpty);
return top;
}
/** Get the top element. */
int myStackTop(MyStack* obj) { //直接返回栈顶
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); //直接返回
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
3.用栈实现队列
题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：void push(int x) 将元素 x 推到队列的末尾，int pop() 从队列的开头移除并返回元素，int peek() 返回队列开头的元素，boolean empty() 如果队列为空，返回 true ；否则，返回 false。
思路：一个栈进行入队操作，另一个栈进行出队操作。出队操作： 当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作。
源码：(包括了栈的创建以及操作接口)
#define DEFSTACKSIZE 100
typedef int STDataType;
struct Stack
{
STDataType* array; //内容
int size; //顶
int capacity; //容量
};
typedef struct Stack Stack;
void CheckCapacity(Stack* ps)
{
if (ps->size >= ps->capacity)
{
ps->capacity *= 2;
ps->array = (STDataType *)realloc(ps->array, ps->capacity * sizeof(STDataType));
}
}
void StackInit(Stack* ps)
{
ps->array = (STDataType *)calloc(DEFSTACKSIZE, sizeof(STDataType));
ps->capacity = DEFSTACKSIZE;
ps->size = 0;
}
void StackPush(Stack* ps, STDataType x)
{
CheckCapacity(ps);
ps->array[ps->size] = x;
ps->size++;
}
void StackPop(Stack* ps)
{
if (ps->size == 0)
{
return;
}
ps->size--;
}
STDataType StackTop(Stack* ps)
{
if (ps->size == 0)
{
return (STDataType)0;
}
return ps->array[ps->size - 1];
}
int StackEmpty(Stack* ps)
{
return ps->size == 0;
}
int StackSize(Stack* ps)
{
return ps->size;
}
void StackDestory(Stack* ps)
{
if (ps->array)
{
free(ps->array);
ps->array = NULL;
ps->size = 0;
ps->capacity = 0;
}
}
typedef struct {
Stack PushS;
Stack PopS;
} MyQueue;
/** Initialize your data structure here. */
MyQueue* myQueueCreate() {
MyQueue* ret = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&ret->PushS);
StackInit(&ret->PopS);
return ret;
}
/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushS, x);
}
/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
if(StackEmpty(&obj->PopS))
{
while(!StackEmpty(&obj->PushS))
{
StackPush(&obj->PopS, StackTop(&obj->PushS));
StackPop(&obj->PushS);
}
}
int top = StackTop(&obj->PopS);
StackPop(&obj->PopS);
return top;
}
/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->PopS))
{
while(!StackEmpty(&obj->PushS))
{
StackPush(&obj->PopS, StackTop(&obj->PushS));
StackPop(&obj->PushS);
}
}
return StackTop(&obj->PopS);
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PushS)&&StackEmpty(&obj->PopS);
}
void myQueueFree(MyQueue* obj) {
StackDestory(&obj->PushS);
StackDestory(&obj->PopS);
free(obj);
}
4.设计循环队列
题目：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。你的实现应该支持如下操作：MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
思路：通过一个定长数组实现循环队列。入队：首先要判断队列是否已满，再进行入队的操作，入队操作需要考虑索引循环的问题，当索引越界，需要让它变成最小值。出队：首先要判断队列是否为空，再进行出队操作，出队也需要考虑索引循环的问题。判空： 队头 == 队尾。判满： 队尾 + 1 == 队头
源码：
typedef struct {
int*a;
int k; //存数据的量
int front; //头
int tail; //尾
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue * obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int)*(k+1)); //开辟数组空间
obj->k = k;
obj->front = 0;
obj->tail = 0;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
int tailnext = obj->tail + 1;
if(tailnext == obj->k + 1) //obj->tail + 1 == obj->k + 1,指向最后一个空间时为满。
{
tailnext = 0; //跳到头
}
return tailnext == obj->front; //等于头则满
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
int tailnext = obj->tail + 1;
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
obj->tail++;
if(obj->tail == obj->k + 1) //存在边界情况，front=tail,然后压入，然后tail=k+1，此时队列没有满，tail需要指向头，形成闭环。
obj->tail = 0; //指向头
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
obj->front++;
if(obj->front == obj->k + 1) //转圈
obj->front = 0;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
int ret = obj->a[obj->front];
return ret;
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
int tailpre = obj->tail - 1;
if(tailpre == -1)
tailpre = obj->k;
return obj->a[tailpre];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}