Scribd Logo
Upload

Welcome to Scribd!

  • 38 views

    Compare Array Based Vs Linked List Stack Implementations

    Uploaded by

    Abdurroo
    A stack can be implemented using either a linked list or an array. When using a linked list, each new node is dynamically allocated so overflow is not possible. Pushing and popping items happens at the head of the list. An array implementation uses a top variable to point to the top element, with push increasing top and pop decreasing it. The main advantage of a linked list is flexibility in size, while an array has fixed capacity which could lead to overflow.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Compare Array Based Vs Linked List Stack Implementations

    Uploaded by

    Abdurroo
    38 views2 pages
    A stack can be implemented using either a linked list or an array. When using a linked list, each new node is dynamically allocated so overflow is not possible. Pushing and popping items happens at the head of the list. An array implementation uses a top variable to point to the top element, with push increasing top and pop decreasing it. The main advantage of a linked list is flexibility in size, while an array has fixed capacity which could lead to overflow.

    Original Title

    2

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    A stack can be implemented using either a linked list or an array. When using a linked list, each new node is dynamically allocated so overflow is not possible. Pushing and popping items happens at the head of the list. An array implementation uses a top variable to point to the top element, with push increasing top and pop decreasing it. The main advantage of a linked list is flexibility in size, while an array has fixed capacity which could lead to overflow.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    38 views2 pages

    Compare Array Based Vs Linked List Stack Implementations

    Uploaded by

    Abdurroo
    A stack can be implemented using either a linked list or an array. When using a linked list, each new node is dynamically allocated so overflow is not possible. Pushing and popping items happens at the head of the list. An array implementation uses a top variable to point to the top element, with push increasing top and pop decreasing it. The main advantage of a linked list is flexibility in size, while an array has fixed capacity which could lead to overflow.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 2

    2.

    Compare Array based vs Linked List stack implementations

     Implement a stack using singly linked list


    To implement a stack using singly linked list concept , all the singly linked list operations are performed based on Stack operations LIFO(last in first out) and
    with the help of that knowledge we are going to implement a stack using single linked list. Using singly linked lists , we implement stack by storing the
    information in the form of nodes and we need to follow the stack rules and implement using singly linked list nodes . So we need to follow a simple rule in
    the implementation of a stack which is last in first out and all the operations can be performed with the help of a top variable .Let us learn how to
    perform Pop , Push , Peek ,Display operations in the following article . 
     

    A stack can be easily implemented using the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing
    and popping items happens at the head of the list. First node have null in link field and second node link have first node address in link field and so on and
    last node address in “top” pointer.
    The main advantage of using linked list over an arrays is that it is possible to implement a stack that can shrink or grow as much as needed. In using array
    will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is
    not possible.
    Stack Operations: 

    push() : Insert a new element into stack i.e just inserting a new element at the beginning of the linked list.

    pop() : Return top element of the Stack i.e simply deleting the first element from the linked list.
    peek(): Return the top element.

    display(): Print all elements in Stack.

     Array-based stack implementation


    Here we present the idea of stack implementation, based on arrays. We assume in current article, that stack's capacity is limited to a certain value and
    overfilling the stack will cause an error. Though, using the ideas from dynamic arrays implementation, this limitation can be easily avoided.

    In spite of capacity limitation, array-based implementation is widely applied in practice. In a number of cases, required stack capacity is known in
    advance and allocated space exactly satisfies the requirements of a particular task. In other cases, stack's capacity is just intended to be "big enough".
    Striking example of the last concept is an application stack. It's capacity is quite large, but too deep recursion still may result in stack overflow.

    Implementation

    Implementation of array-based stack is very simple. It uses top variable to point to the topmost stack's element in the array.

    1. Initially top = -1;
    2. push operation increases top by one and writes pushed element to storage[top];
    3. pop operation checks that top is not equal to -1 and decreases top variable by 1;
    4. peek operation checks that top is not equal to -1 and returns storage[top];
    5. is Empty returns Boolean (top == -1).

    You might also like