Problem of the Day: 2 Stacks 1 Queue

Messing with stacks and queues again, this time using two stacks to mimic a queue. The plan is to create a stack structure, then initialize two of them; one to hold the queue as it fills up (using the push() method, using the pop() method to get to the the front of the queue (bottom of the stack), remove the first entry, and put all the removed items back.

|3 4 5 6 --> dequeue() --> |4 5 6

2 Stacks 1 Queue

Let’s try and take a different spin on yesterday’s problem. Today’s goal will be to implement a stack. Then using two instances of the stack you’ll want to mimic the functionality of a queue. Thus your queue will have an enqueue and dequeue method but those methods will only use the push and pop functionality of your stacks.

2 Stacks 1 Queue

Problem of the Day: Stacks & Queues (update)

Linked-lists always mess with me a bit so it’s good that I used one here. My solution is to use two classes: StacksQueues.java as the main program (calls the operations and prints the results) and Store.java as the data structure. Store.java includes two internal classes: Head and Node.

Head is just the placeholder that links to the first item in the list and is created upon calling new Store() from StacksQueues. It also handles the print() function that formats the double-linked-list as a string surrounding the comma-separated values with square-brackets. It was important to note that the head only links forward to the first node in the list, there is no previous call to get to the head since it’s not useful. Creating an iterator to move through the list calls head.next so the head isn’t considered part of the list.

Nodes are each node in the DLL; they contain a next link to the following node, a prev link to the preceding node, and a value of the node. The node constructor requires the internal value to store and each link has to be set based on where it is being added to the DLL.

Problem of the Day: Stacks & Queues

One data structure that can do both stack and queue functions. The underlying structure will be a double-linked-list because I haven’t used much of those lately.

Stacks && Queues

Glad you’re back for another great week!

Today’s problem is about combining two common data structures in to one. Your goal is to implement a data structure that can pop and push like a stack and also dequeue and enqueue like a queue. Here is an example of how your data structure should work.

store.push(5)
> [5]

store.enqueue(6)
> [5,6]

store.push(7)
> [7,5,6]

store.pop()
> 7

store.dequeue()
> 5

Note: pop and dequeue will essentially do the same thing since they always pull from the front of the line. As always, bonus points for efficiency!

Stacks & Queues

Problem of the Day: Pyramid Sort

Sorting is always tricky and heavily studied for speed and efficiency. My first through was using the idea of keeping the odd numbers on the left and the even on the right which works if the array is only sequential numbers; that assumption certainly makes an assumption out of you and me.

Scratch that idea right quick. Next plan, find the highest number in the array and put it in the middle (index n/2 of odd-numbered arrays or index n/2 + 1 of even numbers to keep the higher number on the right). Works, but then it has to work through both halves at that point. Easy with recursion but not as straight forward.

Last idea, and probably the one I’ll go with, is to focus on the lowest number instead of the high number. Don’t find the highest and put it where it might go instead find the lower number and put it where it will go. The lowest numbers always go on the ends, alternating from left to right where-as the highest number will go in the “middle” then split the array. Work from the outside to the inside instead of inside out. We’ll see where this takes me.

I really should start using something other than Java for variety and to work out the other languages I’m familiar with, C, JS, PHP, even AndroidOS using a nice GUI; but not today.

Anyway, here’s the problem description:

The pyramids of Egypt are some of the most fascinating structures in the world. To honor the great pyramids we’ll be introducing pyramid sort. Pyramid sort works so that the highest numbers are in the center of the array and the lowest are on the edges. When comparing 2 numbers the smaller number goes on the left. So if the array contains 1,2,3 then 1 goes on the left with 2 on the far right and 3 in the middle. Here are 2 more examples:

> psort([1,2,3,4,5])
[1,3,5,4,2]

> psort([1,3,5,7,9,11])
[1,5,9,11,7,3]

Problem of the Day: Smiley Face (update)

Straight forward implementation of my plan. Found two bugs that were my mistakes:

  1. Typo on when to decrement the counter, I used “)” instead of “(“
  2. When using the split() function I didn’t know I had to escape the “)” character because it is a reserved character. The more you know.

Otherwise it works well. I made sure to keep the functions that do the work, countPar() and print(), separate from main() which should make using a JUnit test to check it rather than calling it from main(). I should really learn how to use JUnit tests. Maybe tomorrow.

Problem of the Day: Smiley Face

Smiley Face

Goal is to verify whether there are matching parenthesisisisisis while crawling through text that can contain a smiley emoticon “:)” that doesn’t count.

Quick idea is to use Java’s built-in split() function to pull out the emoticon, put the string back together, and count the parenthesisisisisis with a simple +/- counter. If the end result is 0 then the parenthesisisisisisisisisisisisisis match!.

Otherwise it’d be parsing the string and not counting any “)” that has a “:” before it. More work than I want to do though.