0

it is a python code..whether implementing using linked list .... is efficient in this way...........

data = []            # data storage for stacks represented as linked lists
stack = [-1, -1, -1] # pointers to each of three stacks (-1 is the "null" pointer)
free = -1            # pointer to list of free stack nodes to be reused

def allocate(value):
    ''' allocate a new node and return a pointer to it '''
    global free
    global data
    if free == -1:
        # free list is empty, need to expand data list
        data += [value,-1]
        return len(data)-2
    else:
        # pop a node off the free list and reuse it
        temp = free
        free = data[temp+1]
        data[temp] = value
        data[temp+1] = -1
        return temp

def release(ptr):
    ''' put node on the free list '''
    global free
    temp = free
    free = ptr
    data[free+1] = temp

def push(n, value):
    ''' push value onto stack n '''
    global free
    global data
    temp = stack[n]
    stack[n] = allocate(value)
    data[stack[n]+1] = temp

def pop(n):
    ''' pop a value off of stack n '''
    value = data[stack[n]]
    temp = stack[n]
    stack[n] = data[stack[n]+1]
    release(temp)
    return value

def list(ptr):
    ''' list contents of a stack '''
    while ptr != -1:
        print data[ptr],
        ptr = data[ptr+1]
    print

def list_all():
    ''' list contents of all the stacks and the free list '''
    print stack,free,data
    for i in range(3):
        print i,":",
        list(stack[i])
    print "free:",
    list(free)

push(0,"hello")
push(1,"foo")
push(0,"goodbye")
push(1,"bar")
list_all()
pop(0)
pop(0)
push(2,"abc")
list_all()
pop(1)
pop(2)
pop(1)
list_all()

r there is any way to do this efficiently other than this??implement in this way in c /c++ would be eficient???

Improve this question
9
  • 4
    OMG, turns out all these years I hadn't known what C and C++ is!!! Commented Jun 18, 2011 at 16:29
  • 3
    The question is tagged C and C++, yet the code looks like Python (granted, it looks like Python code some C/C++ guys would write, but still). Commented Jun 18, 2011 at 16:30
  • @Armen Tsirunyan it is not a c/c++ code . it is a python code.... Commented Jun 18, 2011 at 16:31
  • Then why did you tag it C and C++? Commented Jun 18, 2011 at 16:31
  • 2
    @learn Oh, really? That's a relief. For a second I thought it was "C/C++" code... And might I humbly inquire why your question is tagged with C and C++ then ? ;) Commented Jun 18, 2011 at 16:32

4 Answers 4

Reset to default
6

In python, a list is a stack:

>>> l = [1, 2, 3, 4, 5]
>>> l.pop()
5
>>> l.pop()
4
>>> l.append(9)
>>> l
[1, 2, 3, 9]
>>> l.pop()
9
>>> l.pop()
3
>>> l.append(12)
>>> l
[1, 2, 12]

Although it may be an... entertaining exercise to implement a c-style linked list in python, it is unnecessary, and likely to be very slow. Just use a list instead.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

ya. i am going to write c code . whether it is possible to implement 3 stack in a single array without use of linked list??
any other way of implementing 3 stack in single array without linked list in c??
@learn, if you're trying to implement something in c, I'd suggest posting c code instead of python code.
1

A far better solution could be using list instead of stack to implement linked list. The code given is stack implementation of linked list, which I believe is a norm in python but in C/C++ you can use list for efficient implementation.

A sample code in C would be as follows :-

#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *next;
};

struct node* add(struct node *head, int data){
    struct node *tmp;

    if(head == NULL){
        head=(struct node *)malloc(sizeof(struct node));
        if(head == NULL){
            printf("Error! memory is not available\n");
            exit(0);
        }
        head-> data = data;
        head-> next = head;
    }else{
        tmp = head;

        while (tmp-> next != head)
            tmp = tmp-> next;
        tmp-> next = (struct node *)malloc(sizeof(struct node));
        if(tmp -> next == NULL)
        {
            printf("Error! memory is not available\n");
            exit(0);
        }
        tmp = tmp-> next;
        tmp-> data = data;
        tmp-> next = head;
    }
    return head;
}

void printlist(struct node *head)
{
    struct node *current;
    current = head;
    if(current!= NULL)
    {
        do
        {
            printf("%d\t",current->data);
            current = current->next;
        } while (current!= head);
        printf("\n");
    }
    else
        printf("The list is empty\n");

}

void destroy(struct node *head)
{
    struct node *current, *tmp;

    current = head->next;
    head->next = NULL;
    while(current != NULL) {
        tmp = current->next;
        free(current);
        current = tmp;
    }
}
void main()
{
    struct node *head = NULL;
    head = add(head,1); /* 1 */
    printlist(head);

    head = add(head,20);/* 20 */
    printlist(head);

    head = add(head,10);/* 1 20 10 */
    printlist(head);

    head = add(head,5); /* 1 20 10 5*/
    printlist(head);

    destroy(head);
    getchar();
}

In the above example if you create an array of pointers with size 3, each of the pointer pointing to head, you can create three linked lists. This would handle the space with maximum efficiency and there is no need to check for free nodes too.

Improve this answer

9 Comments

@satck programmer is there any way to implement 3 stack in a array without linked list???
Make an array of pointers of size 3, where each pointer of the array points to the top of one stack
@stack programmer three pointers will point to top of 3 stack right.. how to handle the space efficiently?? how to find is there any free space available in array r array is full??? how to store 3 arrays???
hopefully the changed post answers your query
@stack programmer what u have done is correct. if i implement three pointers and point to top of stack.. what is that top of stack means??consider an a[100].. array of size 100. first pointer points to a[0] then what second and third pointer points too???
|
0 
def finding_element(a,k):
    print a
    i = 0
    while k < a[i]:
        i = i-1
        print k,a[i]
        if k > a[i]:
            i = i+1
            print k,a[i]
            if k == a[i]:
                print k,a[i]
    else:
        print "not found"

a = [ 1,3,5,7,8,9]
k = 5
finding_element(a,k)
Improve this answer

1 Comment

this program is not iterating. i would like to know whats is wrong with this . thank you
0

You really don't have to go to all that trouble when Python does all of that out of the box. Sure you can wrap it in functions if you have some complex object to manipulate but don't overthink it and let Python worry about memory allocation (nobody does that manually anymore).

Here is the equivalent of all your function calls in very basic Python:

stacks = [ [] for _ in range(3) ]

stacks[0].append("hello")   # push(0,"hello")
stacks[1].append("foo")     # push(1,"foo")
stacks[0].append("goodbye") # push(0,"goodbye")
stacks[1].append("bar")     # push(1,"bar")
print(stacks)               # list_all()
stacks[0].pop()             # pop(0)
stacks[0].pop()             # pop(0)
stacks[2].append("abc")     # push(2,"abc")
print(stacks)               # list_all()
stacks[1].pop()             # pop(1)
stacks[2].pop()             # pop(2)
stacks[1].pop()             # pop(1)
print(stacks)               # list_all()
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.