Elementary Data Structure–Stack and Queue OJ Questions

Table of Contents

  • foreword
  • valid brackets
    • Idea analysis
    • Code
  • Implementing a stack with a queue
    • Idea analysis
    • Code
  • Implementing a queue with a stack
    • Idea analysis
    • Code
  • design circular queue
    • Idea analysis
    • Code

Foreword

This article will explain some questions about the comprehensive application of stacks and queues in order to have a deeper understanding of stacks and queues.

Valid brackets

Let’s look at the question first

Thinking Analysis

The method we take here is Put the left parenthesis on the stack, and compare the right parenthesis with the parenthesis on the top of the stack. If there is no match, return false, and return true when all the parentheses match.< /strong>.
However, the last few test cases here set up various pitfalls.
1. Every time we take the top element of the stack, we must first judge it as empty, and return false if it is empty.
2. After matching all the left parentheses, it is necessary to judge the stack to be empty. If it is not empty, it means that there are still right parentheses that have not been matched, and then return false.
3. Don’t forget to delete (pop) the top element after taking it out.

Code Implementation

Since the code is a c language version, you must create a stack yourself, so the code may be a bit lengthy.

typedef int STDataType;
typedef struct Stack
{<!-- -->
STDataType* a;
int top;
int Capacity;
}st;


bool STEmpty(ST* pst)
{<!-- -->
assert(pst);
return pst->top == 0;
}
void STInit(ST* pst)
{<!-- -->
assert(pst);
pst->a = NULL;
pst->Capacity = 0;
pst->top = 0;
}
void STDestroy(ST* pst)
{<!-- -->
assert(pst);
free(pst->a);
pst->a = NULL;
pst->Capacity = 0;
pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{<!-- -->
assert(pst);
if (pst->Capacity == pst->top)
{<!-- -->
int newCapacity = pst->Capacity == 0 ? 4 : pst->Capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{<!-- -->
perror("realloc fail");
}
pst->a = tmp;
pst->Capacity = newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{<!-- -->
assert(pst);
assert(!STEmpty(pst));

pst->top--;
}
STDataType STTop(ST* pst)
{<!-- -->
assert(pst);
assert(!STEmpty(pst));

return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{<!-- -->
assert(pst);

return pst->top;
}


bool isValid(char * s){<!-- -->
    ST pst;
    STInit( &pst);
    int len=strlen(s);
    if(len%2==1)
    return false;
    for(int i=0;i<len;i++)
    {<!-- -->
        if(s[i]=='('||s[i]=='['||s[i]=='{')
        {<!-- -->
            STPush( &pst,s[i]);
        }
        else
        {<!-- -->
            if(s[i]==')')
            {<!-- -->
                if(!STEmpty( &pst))
                {<!-- -->
                    char ch = STTop( &pst);
                    STPop( &pst);
                    if(ch!='(')
                    return false;
                }
                else
                return false;
            }
            if(s[i]==']')
            {<!-- -->
                if(!STEmpty( &pst))
                {<!-- -->
                    char ch = STTop( &pst);
                    STPop( &pst);
                    if(ch!='[')
                    return false;
                }
                else
                return false;
            }
            if(s[i]=='}')
            {<!-- -->
                if(!STEmpty( &pst))
                {<!-- -->
                    char ch = STTop( &pst);
                    STPop( &pst);
                    if(ch!='{')
                    return false;
                }
                else
                return false;
            }
        }
    }
    if(!STEmpty( &pst))
    {<!-- -->
        return false;
    }
    return true;
}

Implement a stack with a queue

Let’s look at the question first

Thinking Analysis

The main idea of this question is to use two queues, queue1 and queue2. first store the elements in queue2, and then store the elements in queue2 out of the queue and store them in queue1 when the stack is to be unstacked, leaving one queue2 The element at the end of the queue can be used to pop the stack.
If it is not the first time to pop the stack, the elements in queue1 will be dequeued and stored in queue2, and the remaining element at the end of queue1 can be used for popping.

Code Implementation

typedef int QDataType;
typedef struct QueueNode
{<!-- -->
struct QueueNode* next;
QDataType data;
}QNode;

typedef struct Queue
{<!-- -->
QNode* phead;
QNode* ptail;
int size;
} Queue;

bool QueueEmpty(Queue* pq)
{<!-- -->
assert(pq);

return pq->size == 0;
}
void QueueInit(Queue* pq)
{<!-- -->
assert(pq);
pq->phead = pq->ptail = NULL;

pq->size = 0;
}
void QueueDestroy(Queue* pq)
{<!-- -->
assert(pq);
// delete the node first
QNode* cur = pq->phead;
while (cur)
{<!-- -->
QNode* next = cur->next;
free(cur);
cur = next;
}
//Remove head and tail pointer
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{<!-- -->
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{<!-- -->
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{<!-- -->
assert(pq->phead == NULL);

pq->phead = pq->ptail = newnode;
}
else
{<!-- -->
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size + + ;
}
void QueuePop(Queue* pq)
{<!-- -->
assert(pq);
assert(!QueueEmpty(pq));

if (pq->phead->next == NULL)
{<!-- -->
free(pq->phead);
pq->phead = pq->ptail = NULL;
}

else
{<!-- -->
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{<!-- -->
assert(pq);
    assert(!QueueEmpty(pq));

return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{<!-- -->
assert(pq);
assert(!QueueEmpty(pq));

return pq->ptail->data;
}
int QueueSize(Queue* pq)
{<!-- -->
assert(pq);

return pq->size;
}


typedef struct {<!-- -->
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {<!-- -->
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
    {<!-- -->
        perror("malloc fail\
");

    }
    QueueInit( & obj->q1);
    QueueInit( & obj->q2);

    return obj;
}

void myStackPush(MyStack* obj, int x) {<!-- -->
    if(!QueueEmpty( &obj->q1))
    QueuePush( &obj->q1,x);
    else
    QueuePush( &obj->q2,x);
}

int myStackPop(MyStack* obj) {<!-- -->
    Queue* EmptyQueue= &obj->q1;
    Queue* NonEmptyQueue= &obj->q2;
    if(!QueueEmpty( &obj->q1))
    {<!-- -->
        EmptyQueue= &obj->q2;
        NonEmptyQueue= &obj->q1;
    }
    while(QueueSize(NonEmptyQueue)>1)
    {<!-- -->
        QueuePush(EmptyQueue, QueueFront(NonEmptyQueue));
        QueuePop(NonEmptyQueue);
    }
    int top=QueueFront(NonEmptyQueue);
    QueuePop(NonEmptyQueue);

    return top;



}

int myStackTop(MyStack* obj) {<!-- -->
    if(QueueEmpty( & obj->q1))
    return QueueBack( & amp; obj->q2);
    else
    return QueueBack( & amp; obj->q1);


}

bool myStackEmpty(MyStack* obj) {<!-- -->
    return QueueEmpty( & obj->q1)
       & amp; & amp; QueueEmpty( & amp;obj->q2);

}

void myStackFree(MyStack* obj) {<!-- -->
    QueueDestroy( &obj->q1);
    QueueDestroy( & obj->q2);

    free(obj);

}

Using a stack to implement a queue

Look at the question first

Thinking Analysis

The main idea is to use one of the stacks for putting in, and the other for taking out. The order of the elements will be reversed every time the stack is popped, and the stack will just match the order of the queue once.

Note: When returning the element at the beginning of the queue, you should first judge whether the stack used for extraction is empty. If it is not empty, you can directly extract the top element of the stack. If it is empty , then put all the stack elements used for putting into the stack for taking out, and then return the top element of the stack.

Code Implementation

typedef int STDataType;
typedef struct Stack
{<!-- -->
STDataType* a;
int top;
int Capacity;
}st;

bool STEmpty(ST* pst)
{<!-- -->
assert(pst);
return pst->top == 0;
}
void STInit(ST* pst)
{<!-- -->
assert(pst);
pst->a = NULL;
pst->Capacity = 0;
pst->top = 0;
}
void STDestroy(ST* pst)
{<!-- -->
assert(pst);
free(pst->a);
pst->a = NULL;
pst->Capacity = 0;
pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{<!-- -->
assert(pst);
if (pst->Capacity == pst->top)
{<!-- -->
int newCapacity = pst->Capacity == 0 ? 4 : pst->Capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{<!-- -->
perror("realloc fail");
}
pst->a = tmp;
pst->Capacity = newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{<!-- -->
assert(pst);
assert(!STEmpty(pst));

pst->top--;
}
STDataType STTop(ST* pst)
{<!-- -->
assert(pst);
assert(!STEmpty(pst));

return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{<!-- -->
assert(pst);

return pst->top;
}


typedef struct {<!-- -->
    ST pushst;//put
    ST popst;//fetch
} MyQueue;


MyQueue* myQueueCreate() {<!-- -->
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {<!-- -->
        perror("malloc fail\
");
        return NULL;
    }
    STInit( & obj->pushst);
    STInit( & obj->popst);

    return obj;

}

void myQueuePush(MyQueue* obj, int x) {<!-- -->
    STPush( & obj->pushst,x);
}

int myQueuePop(MyQueue* obj) {<!-- -->
    int front=myQueuePeek(obj);
    STPop( & obj->popst);
    return front;
}

int myQueuePeek(MyQueue* obj) {<!-- -->
    if(STEmpty( &obj->popst))
    {<!-- -->
        while(!STEmpty( &obj->pushst))
        {<!-- -->
            STPush( & amp; obj->popst,STTop( & amp; obj->pushst));
            STPop( & obj->pushst);
        }
    }

    return STTop( &obj->popst);

}

bool myQueueEmpty(MyQueue* obj) {<!-- -->
    return STEmpty( & amp; obj->pushst) & amp; & amp; STEmpty( & amp; obj->popst);

}

void myQueueFree(MyQueue* obj) {<!-- -->
    STDestroy( & obj->pushst);
    STDestroy( &obj->popst);

    free(obj);

}

Design circular queue

Look at the question first

Thinking Analysis

We must first consider a question, How to distinguish between full and empty?
When the queue is full or empty, the subscripts of rear and front are same.

In order to solve this problem, we consider adding a space without storing any data, and if rear + 1 is equal to front, it will be full.
After solving this problem, let’s look at other operations,
Assuming that the circular queue stores 5 pieces of data, we first open up 6 spaces.

At this point rear==front is empty.

So how should we judge full at this time?
For example, when the front is 0 and the rear is 5, the queue is full at this time, or when the rear is 2 and the front is 3, it is full again at this time, it seems that as long as rear + 1=front is satisfied, but we think about it carefully One problem, the array cannot find the head directly from the end like a linked list, so if the subscript of the array exceeds the storage space, we take the moduloYou can let the subscript go back from the beginning,

How to insert data?
This is very simple, just put the value into the position where the subscript is rear, and then put rear ++. Note that if it exceeds the range, you need to take the modulus. Since it is less than the maximum range, the modulus is still equal to itself, we simply every time Both are modulo.

How do I delete data?
We only need to front ++, and we also need to modulo.

How to get the head element?
It’s very simple, just return the element whose subscript is front directly.

How to get the tail element?
The element at the end of the queue is the element corresponding to the subscript before the rear, but there are special cases. Suppose the rear points to 5 at this time, we should return 4, if it points to 0, we should return 5, but 5-1=4, 0-1 Obviously it is not equal to 5, so we still consider using the modulo method, here is the formula directly
(rear + k)%(k + 1).

Code Implementation

typedef struct {<!-- -->
    int front;
    int rear;
    int k;
    int* a;

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {<!-- -->
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k + 1));
    obj->front=obj->rear=0;
    obj->k=k;

    return obj;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {<!-- -->
    return obj->front==obj->rear;

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {<!-- -->
    return (obj->rear + 1)%(obj->k + 1)==obj->front;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {<!-- -->
    if(myCircularQueueIsFull(obj))
    return false;
    obj->a[obj->rear]=value;
    obj->rear ++ ;

    obj->rear%=(obj->k + 1);
    return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {<!-- -->
    if(myCircularQueueIsEmpty(obj))
    return false;

    obj->front + + ;
    obj->front%=(obj->k + 1);
    return true;

}

int myCircularQueueFront(MyCircularQueue* obj) {<!-- -->
    if(myCircularQueueIsEmpty(obj))
    return -1;

    return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj) {<!-- -->
    if(myCircularQueueIsEmpty(obj))
    return -1;

    return obj->a[(obj->rear + obj->k)%(obj->k + 1)];

}


void myCircularQueueFree(MyCircularQueue* obj) {<!-- -->
    free(obj->a);
    free(obj);

}

The above is the entire content of this article. If there is any discrepancy, please correct me.

syntaxbug.com © 2021 All Rights Reserved.