Implementing stacks with queues < difficulty factor ⭐>

“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

📝 description: You can implement a LIFO stack with only two queues and support all four operations (push, top, POP, and Empty) of a normal stack.

Implement MyStack class:

1️ void push(int x) pressure element X into the top of stack.

2️ int POP () remove and return top element of stack.

3️ int TOP () return top element of stack.

4️ discount () Return true if the stack is empty; Otherwise, return false

⚠ note

1️ you can only use the basic operations of queues — namely push to back, peek/pop from front, size and is empty.

2️ one your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.

💨 example:

Input: [” MyStack “, “push” and “push”, “top”, “pop”, “empty”] – calling function interfaces referred to as “[[], [1], [2], [], [], []] – parameters

Output: [null, NULL, NULL, 2, 2, false]

MyStack MyStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // Return 2 mystack.pop (); // Return 2 mystack.empty (); / / returns False

🍳 prompt

1️ 1 <= x <= 9

2️ call 100 push, POP, top and Empty at most

3️ each call of POP and TOP ensures that the stack is not empty

⚜ further Can you implement a stack with O(1) amortized time for each operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take longer than the others. You can use more than two queues.

🧷 Platform: Visual Studio 2017 && Windows

🔑 core idea: the data of the queue can not be sent out from the end of the queue, but only from the head of the queue. What is to be realized here is the queue implementation stack, so it can only follow the characteristics of the stack — last in, first out. Here another queue is required, as follows:

1, a queue has data, a queue has no data

2. Input data to the non-empty input

3. Copy the first size-1 of the non-empty queue to another queue, and Pop off the remaining data

Leetcode the original

/ / declare
    / / structure
typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next; // point to the next node
    QDataType data; // Store integer data
}QueueNode;

typedef struct Queue
{
    QueueNode* phead;/ / the head pointer
    QueueNode* ptail;/ / the tail pointer
}Queue;

    / / function
void QueueInit(Queue* pq); 
void QueuePush(Queue* pq, QDataType x);	
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq);
QDataType QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueDestory(Queue* pq);
// Function implementation
void QueueInit(Queue* pq)
{
    assert(pq);
    // set two Pointers to null
    pq->phead = pq->ptail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    // Create a BuyQueueNode for malloc space
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL)
    {
	printf("malloc fail\n");
	exit(- 1);
    }
    newnode->data = x;
    newnode->next = NULL;
    // First insertion
    if (pq->phead == NULL)
    {
	pq->phead = pq->ptail = newnode;
    }
    // Non-first insertion
    else{ pq->ptail->next = newnode; pq->ptail = newnode; }}bool QueueEmpty(Queue* pq)
{
    assert(pq);
    // Empty lists return true, non-empty lists return false
    return pq->phead == NULL;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    // The linked list cannot be deleted when it is emptyassert(! QueueEmpty(pq));// There is only one node
    if (pq->phead->next == NULL)
    {
	free(pq->phead);
	pq->phead = pq->ptail = NULL;
    }
    // Multiple nodes
    else
    {
	QueueNode* next = pq->phead->next;
	free(pq->phead) ; pq->phead = next; }}QDataType QueueSize(Queue* pq)
{
    assert(pq);
    // If you need to call QueueSize frequently, you can add a member to the Queue structure for the length of the record
    int sz = 0;
    QueueNode* cur = pq->phead;
    while (cur)
    {
	sz++;
	cur = cur->next;
    }
    return sz;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    // If the list is empty, the header cannot be fetchedassert(! QueueEmpty(pq));return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    // If the list is empty, no tail can be fetchedassert(! QueueEmpty(pq));return pq->ptail->data;
}
void QueueDestory(Queue* pq)
{
    assert(pq);
	
    QueueNode* cur = pq->phead;
    // Iterate over the list
    while (cur)
    {
	QueueNode* next = cur->next;
	free(cur);
	cur = next;
    }
    pq->phead = pq->ptail = NULL;
}

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;

/** Initialize your data structure here. */

MyStack* myStackCreate(a) 
{
    / / malloc space
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    //Init two queues
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) 
{
    assert(obj);
    //QueueEmpty returns true if it is empty and false if it is not
        / / insert the data in the queue isn't empty (q1 isn't empty insert into q1, q2 isn't empty insert into q2)
    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) 
{
    assert(obj);
    Q1 is null, q2 is not null
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    //q1 is not null, reassign
    if(! QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; nonemptyQ = &obj->q1; }// copy - copies the size-1 data of the non-empty queue
    while(QueueSize(nonemptyQ) > 1)
    {
        // Copy a non-empty queue to an empty queue
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        // Delete the iteration
        QueuePop(nonemptyQ);
    }
    //top Records the remaining value of the non-empty queue
    int top = QueueFront(nonemptyQ);
    // Remove the remaining data from the non-empty queue, which is the data at the top of the stack
    QueuePop(nonemptyQ);
    / / return
    return top;
}

/** Get the top element. */
int myStackTop(MyStack* obj) 
{
    assert(obj);
    //q1 is not empty
    if(! QueueEmpty(&obj->q1)) {return QueueBack(&obj->q1);
    }
    //q2 is not empty
    else
    {
        returnQueueBack(&obj->q2); }}/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) 
{
    assert(obj);
    // One of q1 and Q2 must be empty
    Q1 returns true, q2 returns true, mystackEmpty returns true;
    //q1 returns true for empty, q2 returns false for non-empty, myStackEmpty returns false for non-empty
    Q1 returns false if it is not empty, q2 returns true if it is empty, myStackEmpty returns false if it is not empty
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
    assert(obj);
    // With the above code analysis, we need to reclaim the space of the two queues and malloc in myStackcreate
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);

    free(obj);
}

/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); * /
Copy the code