[数据结构]栈和队列的几个简单OJ（括号匹配问题,用队列实现栈,用栈实现队列,设计循环队列)

本文主要是介绍[数据结构]栈和队列的几个简单OJ（括号匹配问题,用队列实现栈,用栈实现队列,设计循环队列)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文主要是几个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);

}

这篇关于[数据结构]栈和队列的几个简单OJ（括号匹配问题,用队列实现栈,用栈实现队列,设计循环队列)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！