有關設計堆棧

-1

我要設計一個堆棧，使得與常規操作以及諸如pop，push，isempty，isfull，它還支持功能get_min()它返回minimum元素堆棧中的混亂。所有操作必須在O(1)。有關設計堆棧

我使用了一個linked list作爲堆棧。並且在鏈接列表的每個節點中，我添加了一個特殊字段min以將最小值存儲在堆棧中。下面是我的代碼：

#include <iostream> 
#include <stdlib.h> 
#include <string.h> 
#include <ctype.h> 
#include <limits.h> 

using namespace std; 

typedef struct node 
{ 
    int data, min; 
    struct node *next; 
}node; 

bool isempty(node *head) 
{ 
    return !head; 
} 

void display(node *head) 
{ 
    while(head) 
    { 
     cout<<head->data<<"-->"; 
     head=head->next; 
    } 
    cout<<"\n"; 
} 

int get_min(node *head) 
{ 
    return head->min; 
} 

int peek(node *head) 
{ 
    if(isempty(head)) 
     return INT_MIN; 

    return head->data; 
} 

void push(node **head_ref, int data) 
{ 
    node *new_node; 
    new_node=(node*)malloc(sizeof(node)); 

    new_node->data=data; 
    if((*head_ref)==NULL || data <= get_min((*head_ref))) 
    { 
     new_node->min=data; 
    } 
    else 
    { 
     new_node->min=(*head_ref)->min; 
    } 

    new_node->next=(*head_ref); 
    (*head_ref)=new_node; 
} 



int pop(node **head_ref) 
{ 
    if(isempty((*head_ref))) 
     return INT_MIN; 

    int c=(*head_ref)->data; 
    node *temp=(*head_ref); 

    (*head_ref)=(*head_ref)->next; 
    free(temp); 
    return c; 
} 




int main() 
{ 
    node *head=NULL; 
    push(&head, 3); 
    push(&head, 0); 
    push(&head, 1); 

    display(head); 

    cout<<get_min(head); 
    return 0; 
}

我想問如果我用上面的方法違反任何堆棧性能，還是設計一個堆棧以正確的方式？

來源

2016-08-19 shiva

那麼，在C++中，你已經可以用'的std ::基於'的std :: list' stack'。此外，如果你想改善工作代碼，你最好在[SE代碼評論]（http://codereview.stackexchange.com/） –

@AmTavory上提問，這是完全可能的。 O（1）用於推動，彈出和分鐘。 – serhiyb

@πάνταῥεῖ我不想使用STL，我也不想改進它。我只想知道它是否設計堆棧的正確方法。 – shiva

它只是正確的，但我的建議是，而不是存儲每個條目的最小元素只是創建另一個堆棧&存儲最小元素。

現在，在PUSH操作過程中，只需比較新元素與最小數組中的頂部元素，如果它是最小值或相等，只需將其插入到新堆棧中即可。

在執行POP操作時，只需檢查彈出的元素是否與最小堆棧中的頂層元素相同。如果是，則POP從最小堆棧中的元素也與原始堆棧一起。

這將有助於節省我們的記憶。

這個問題已經被問到我的實習生面試CarWaly

來源

2016-08-19 22:40:06

有關設計堆棧

回答

相關問題