Three in One - Part One

Describe how you could use a single array to implement three stacks.

Hint 1. A stack is simply a data structure in which the most recently added elements are removed first. Can you simulate a single stack using an array? Remember there are many possible solutions, and there are tradeoffs of each.

Hint 2. We could simulate three stacks in an array by just allocating the first third of the array to the first stack, the second third to the second stack, and the final third to the third stack. One might actually be much bigger than the others though. Can we be more flexible with the divisions?

Initialize a size holder, an array of each head of the stacks, and a stack array.

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

int total_size;
int stack_point[3];
int* stacks = NULL;

Then we make the push and pop functions. Push here is alittle different in where it takes a stack number, specifying which stack it is to be pushed to. Pop also takes an extra argument specifying which stack to pop from.

void push(int* stacks, int s_num, int element){
  if (s_num > 3 || s_num < 1) {
    printf("ERROR. invalid stack number");
    return;
  }
  if (stack_point[s_num-1] >= total_size || 
      (stack_point[s_num-1] >= (total_size/3) * s_num && s_num != 3)){
    printf("ERROR. Stack %i full\n", s_num);
    return;
  }
  stacks[stack_point[s_num-1]] = element;
  stack_point[s_num-1] += 1;
}

void pop(int* stacks, int s_num){
if (s_num > 3 || s_num < 1) {
    printf("ERROR. invalid stack number");
    return;
  }
  
  if (stack_point[s_num-1] < (total_size/3) * s_num-1){
    printf("ERROR. Stack empty");
    return;
  }  

  stacks[stack_point[s_num-1] - 1] = -1;
  stack_point[s_num - 1] -= 1;
}

The a simple print function to print all the stack numbers. This way we can see if things aren't quite working.

void print_stacks(int* stacks){
  int i;

  for(i=0; i= total_size/3 && i < stack_point[1]) printf("%i, ", stacks[i]);
    else if (i >= (total_size/3) * 2 && i < stack_point[2]) printf("%i, ", stacks[i]);
  }
  printf("\n");
}

Assuming that size input is not going to be invalid, we create a stack here and give it some push/pop tests.

void main(int argc, char* argv[]){
  if (argc != 2){ printf("ERROR. Insufficient arguments.\n"); return;}
  total_size = atoi(argv[1]); 

  stacks = malloc(sizeof(int) * total_size);
  stack_point[0] = 0;
  stack_point[1] = total_size / 3;
  stack_point[2] = (total_size / 3) * 2;

  push(stacks, 1, 1);
  push(stacks, 1, 3);

  push(stacks, 2, 2);
  push(stacks, 2, 4);

  push(stacks, 3, 1);
  push(stacks, 3, 2);
  push(stacks, 3, 3);

  pop(stacks, 3);
  push(stacks, 3, 4);

  print_stacks(stacks);
}

Let me know if there's any mistakes! I'm contemplating if I should post a better version since it would be longer, so I will post other questions as I work on it.

Read More

Return Kth to Last

Implement an algorithm to find the kth to last element of a singly linked list.

If we knew the length of the linked list, then we could just subtract k and we would move a pointer length-k times.

Here, I think the best way would be to just iterate through the linked list with two pointers. The two nodes start on the head of the linked list. The first pointer would go ahead k steps, and then both would move ahead until the first point touches the last node. The next node that the second node stops at will be out kth to last node.

This would take O(n) time since we have to go through all the elements of the linked list, and O(1) space.

Here's what I have:

We first create the structures for a linked list

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

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

struct list{
  struct node* head;
};

Then we make some linked list making functions

struct node* create_node(int data){
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data;
  new_node->next = NULL;

  return new_node;
}

void add_node(struct list* llist,int data){
  struct node* new_node = create_node(data);
  new_node->next = llist->head;
  llist->head = new_node;
}

The star method of this question! Assuming a valid k and linked list, we get two pointers, move the first k times, and then move both pointers until the first pointer reaches the end of the linked list.

int kth_to_last(struct list* llist, int k){
  struct node* tmp1 = llist->head;
  struct node* tmp2 = llist->head;

  int i;
  for (i=0;i<k+1;i++){
    tmp2 = tmp2->next;
  }
  while(tmp2->next != NULL){
    tmp1 = tmp1->next;
    tmp2 = tmp2->next;
  }
  
  return tmp1->data;

}

Then we create a linked list for some testingggg

int main(int argc, char* argv[]){
  struct list* new_list = (struct list*)malloc(sizeof(struct list));
  new_list->head = NULL;

  int i;
  for (i=20;i>0;i--){
  add_node(new_list, i*2);
  }

  for(i=0;i<19;i++){
    printf("%ith item: %i\n", i+1, kth_to_last(new_list, i));
  }
}

Read More