popStack pops out data that I didn't push (stack adt)

96 views Asked by At

This is a code to push 0 and 1 and pop 1 and 0 again. However, it pops 2 and 2. I can't seem to figure out why.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "stackADT.h"

int main (void)
{
  STACK* stack;
  int data;

  stack = createStack ();

  int i;
  for (i = 0; i < 2; i++)
  {
    printf("insert %d\n", i);
    pushStack (stack, &i);
    //printf("count: %d\n", stackCount (stack));
    //data = *(int*) popStack (stack);
    //printf("%d popped\n", data);
  }


  while (!emptyStack (stack))
  {

    data = *(int*) popStack (stack);
    printf("%d popped\n", data);
  }
}

This is the output.

insert 0
insert 1
2 popped
2 popped

When I try with for (i = 0; i < 5; i++), this is what happens.

insert 0
insert 1
insert 2
insert 3
insert 4
5 popped
5 popped
5 popped
5 popped
5 popped

I'm attaching stackADT.h.(This code is from Data Structures: A Pseudocode Approach with C by Richard F. Gilbert & Behrouz A. Forouzan)

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

// Structure Declarations
typedef struct node
  {
  void* dataPtr;
  struct node* link;
  } STACK_NODE;

typedef struct
  {
  int count;
  STACK_NODE* top;
  } STACK;

// Prototype Declarations
STACK* createStack (void);
bool pushStack (STACK* stack, void* dataInPtr);
void* popStack (STACK* stack);
void* stackTop (STACK* stack);
bool emptyStack (STACK* stack);
bool fullStack (STACK* stack);
int stackCount (STACK* stack);
STACK* destroyStack (STACK* stack);


/* =============== createStack ==================
  Creates an empty stack
    Pre Nothing
    Post Returns pointer to a null stack
      -or- NULL if overflow
*/
STACK* createStack (void)
{
  // Local Declarations
  STACK* stack;

  // Statements
  stack = (STACK*) malloc(sizeof (STACK));
  if (stack)
    {
      stack->count = 0;
      stack->top = NULL;
    } // if

  return stack;
} // createStack


/* ================ pushStack =================
    Pre stack: STACK*
        dataInPtr: data* to be inserted

    Post data inserted into stack
    Return true if successful; flase if underflow

*/
bool pushStack (STACK* stack, void* dataInPtr)
{
  // Local Declarations
  STACK_NODE* newPtr;

  // Statements
  newPtr = (STACK_NODE*) malloc(sizeof(STACK_NODE));
  if (!newPtr)
    return false;

  newPtr->dataPtr = dataInPtr;
  newPtr->link = stack->top;
  stack->top = newPtr;

  (stack->count)++;
  return true;
} // pushStack


/* ================ popStack ====================

*/
void* popStack (STACK* stack)
{
  //Local Definitions
  void* dataOutPtr;
  STACK_NODE* temp;

  //Statements
  if (stack->count == 0)
    dataOutPtr = NULL;
  else
    {
      temp = stack->top;
      dataOutPtr = stack->top->dataPtr;
      stack->top = stack->top->link;
      free(temp);
      (stack->count)--;
    }
  return dataOutPtr;
}



/* ================ stackTop =========================

*/
void* stackTop (STACK* stack)
{
  //Local Definitions
  //Statements
  if (stack->count == 0)
    return NULL;
  else
    return stack->top->dataPtr;
} // stackTop

/* ================== emptyStack =====================
  returns: 1 if the stack is empty; 0 otherwise
*/
bool emptyStack (STACK* stack)
{
  // Statements
  return (stack->count == 0);
} // emptyStack


/* ================= fullStack =======================
  determines if a stack is full
  Full == heap full

  returns: true if heap full; false otherwise
*/
bool fullStack (STACK* stack)
{
  // local definitions
  STACK_NODE* temp;
  // statements
  if ((temp =
    (STACK_NODE*) malloc(sizeof(*(stack->top)))))
    {
      free(temp);
      return false;
    } //if
  // malloc failed
  return true;
} // fullStack




/* ============== stackCount ====================
  returns: int, stack count
*/
int stackCount (STACK* stack)
{
  return stack->count;
}


/* ============== destroyStack ===================
    release all nodes to the heap
  returns: null pointer
*/
STACK* destroyStack (STACK* stack)
{
  //local definitions
  STACK_NODE* temp;
  //statements
  if (stack)
    {
      //Delete all nodes in stack
      while (stack->top != NULL)
        {
          free(stack->top->dataPtr);

          temp = stack->top;
          stack->top = stack->top->link;
          free(temp);
        } // while
      // Stack now empty. Destroy stack head node.
      free(stack);
    }
  return NULL;
} // destoryStack

and my gcc version.

$ gcc --version
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix
1

There are 1 answers

1
Mohit Jain On BEST ANSWER
for (i = 0; i < 2; i++)
{
    ...
    pushStack (stack, &i);  // Push address of i
}

You are pushing (same) address of i twice. Which after loop end contains 2. When you pop back, you get the address which contains 2 and hence the output is 2 both times.

Stack:
+----+    &i
| &i |\  +----+
+----+ \ | 02 |
| &i | / +----+
+----+/

Some possible solutions are:

  • Instead of storing the address, create a new node and copy the contents of addresses to be pushed.
  • Store data instead of pointers.