Stack with operations on middle element

Question

希望有哪位大佬可以帮助我解决这道题！

需要实现的功能：

1） push（） 将元素添加到堆栈顶部。

2） pop（） 从堆栈顶部删除一个元素。

3） findMiddle（） 将返回堆栈的中间元素。

4）deleteMiddle（） 将删除堆栈的中间元素。

那么，用于实现此特殊堆栈的数据结构是什么？

使用**双链表**（DLL）。我们可以通过保持mid指针来在O（1）时间中找到中间元素。我们可以使用上一个和下一个指针在两个方向上移动中间指针。

不要修改源代码，并完成push（）、pop（）、 findMiddle（）、deleteMiddle（）四个元素

//-----Include required headers here-----
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//-----End of headers-----


//-----Add new functions here(if any)-----

//-----New functions end here-----

//-----A Doubly Linked List Node-----
// DO NOT MODIFY IT
struct DLLNode {
    struct DLLNode *prev;
    int data;
    struct DLLNode *next;
};

/* Representation of the stack data structure that supports findMiddle(),
   deleteMiddle() in O(1) time.  The Stack is implemented using Doubly 
   Linked List. It maintains pointer to head node, pointer to middle 
   node and count of nodes */
// DO NOT MODIFY IT
struct myStack {
    struct DLLNode *head;
    struct DLLNode *mid;
    int count;
};

//-----Function to create the stack data structure-----
// DO NOT uncomment the below function. It is for your reference purpose only.
// We will use this function to create the stack.
/*struct myStack *createMyStack() {
    struct myStack *ms = (struct myStack*) malloc(sizeof(struct myStack));
    ms->count = 0;
    ms->head = NULL;
    ms->mid = NULL;
    return ms;
}; */

//-----Function to push an element to the stack-----
void push(struct myStack *ms, int new_data) {
    /* allocate DLLNode and put in data */
    struct DLLNode* new_DLLNode = (struct DLLNode*) malloc(sizeof(struct DLLNode));
    new_DLLNode->data  = new_data;

    //-----Appropriately update new_DLLNode and ms to get the functionality-----


    //-----code ends here-----
}

//-----Function to pop an element from stack. Return the popped element-----
//-----Will not be called for empty stack-----
int pop(struct myStack *ms) {
    struct DLLNode *head = ms->head;
    int item = head->data;

    //-----Appropriately update ms to get the required functionality-----


    //-----code ends here-----

    free(head);

    return item;
}

//-----Function for finding middle of the stack-----
//-----Will not be called for empty stack-----
int findMiddle(struct myStack *ms) {
    //-----code begins here-----


    //-----code ends here-----
}

//-----Function for deleting middle of the stack-----
//-----Return the value deleted, will not be called for empty stack-----
int deleteMiddle(struct myStack *ms) {
    //-----code begins here-----


    //-----code ends here-----
}

Answer 1

https://blog.csdn.net/martin_liang/article/details/42436213