CODEWITHSUNDEEP
c
NinjaWarrrior
NinjaWarrrior

Reputation: 57

How do I check whether given two stacks are equal or not in C?

I have an assignment question where I have to check two stacks and see if they are equal (if they contain the same numbers in the same order).

My approach was to 

- Find the size of the stacks
 - If (size of stack 1 > size of stack 2 || size of stack 1 < size of stack 2)
 - Tell the user it doesn't equal
 - Set a to size of [n[ where en is the size of each stack, and pop all the elements of stack 1 to array1 and do the same for stack 2, but assign to stack2. 
 - then using a for loop check if a[I] = b[I]

We are just told that

You ​cannot make assumptions​ about how the stack is implemented. If you want to use any other function, you need to implement it.

typedef​ ​struct​ { 
... ​// not known
} stack_t;

// creates a new stack
   stack_t* stack_create();



// pushes a given item to the stack

void​ stack_push(stack_t* s, ​int​ item);

// pops the top element from the stack // 
int​ stack_pop(stack_t* s);

 // checks if the stack is empty
bool​ stack_is_empty(stack_t* s); 

// frees the stack
void​ stack_free(stack_t* s);

Upvotes: 2

Views: 3758

Answers (5)

Sandy
Sandy

Reputation: 903

A simple solution would be:

  1. Pop one element from each stack, if one of the stacks is empty, break.
  2. Compare the elements and if they are equal push them in a new stack, else break.

Repeat this until both the stacks are empty. If you need to restore the stack you can do so by popping new stack and pushing that value in both the stacks.

Upvotes: 2

D&#233;j&#224; vu
D&#233;j&#224; vu

Reputation: 28850

In O(n) without calculating the size of the stacks, taking care of the special case of a stack being empty and not the other one.

Something like (hint algorithm)

bool are_equal(stack1, stack2) {
    while ( 1 ) {
       bool e1 = is_empty(stack1);
       bool e2 = is_empty(stack2);
       if (e1 && e2) return true;                    // equal
       if (e1 || e2) return false;                   // not equal
       if (pop(stack1) != pop(stack2)) return false; // not equal
    }
}

Upvotes: 4

Akhilesh Pandey
Akhilesh Pandey

Reputation: 896

I think there are many ways to achieve your goal. However, the simplest one that I can think of as of now is building on the idea given by @ahota. I cannot write the complete code for you but I am explaining the methodology below. Write me if you want some more information.

Step1: check both the stacks are emoty or not using is_empty(). If both the stacks are empty then they are same else if any one of the stacks is empty then they are not same. Exit program.

Step2: if both stacks are not empty then pop elements from both the stacks like a= pop(stack1) b= pop(stack2).

Step3: compare a and b. If a and b are not same then stack1 and stack2 are not same. Exit the programhere . If a and b are same then repeat step 1-3.

Hope this helps you.

Upvotes: 1

asio_guy
asio_guy

Reputation: 3767

here is a loosely written pseudo code, assuming stack_is_empty returns true if given stack is empty

bool are_they_equal( stack_t *s1, stack_t *s2 )
  {
    /* if both are not empty keep popping from both until
       either one of them is empty or both empty */  
    while( !stack_is_empty(s1) && !stack_is_empty(s2) )
       {
         /** Problem with Ordering , return **/
         if( stack_pop(s1) != stack_pop(s2) ) {
            return false;
         }
       }

    /* if both empty they've popped equal number of elements ( equal ) 
       otherwise no*/
    return (stack_is_empty(s1) && stack_is_empty(s2)) ? true : false;
  }

Upvotes: 1

Shlok Nangia
Shlok Nangia

Reputation: 2377

You have 2 options.

  1. either you can run a loop and count all the elements in the each stack each time you want size of stack.
  2. create length variable for each stack and update them when each push/pop is performed and then you can return that variable whenever the length/size of stack is asked.

Upvotes: 1

Related Questions